Finding Shortest Path

Question

Working on Functionally Solving Problems from Learn You a Haskell, I worked on the "Heahtrow to London" shortest path problem.

I'm working on a reduced set of this problem in order to solve a simple problem first.

It's a shortest path problem for the following map:

The rule is: you start a A or B, and then choose across the bridge or up/down. When you reach E or F (doesn't matter), you're done.

I used a Node data structure (compliments of LYAH's previous chapter) to recurse through the shorter left or right sides. Ultimately, I return a tuple of (collective cost, list of nodes traversed).

Please critique my implementation:

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

shortestPath2 :: Tree (Int, Char) -> (Int, [Char])
shortestPath2 EmptyTree = (0, [])
shortestPath2 (Node (c, pt) EmptyTree EmptyTree) = (c + fst (shortestPath2 EmptyTree), pt : snd (shortestPath2 EmptyTree))
shortestPath2 (Node (c, pt) EmptyTree right)     = (c + fst (shortestPath2 right), pt : snd (shortestPath2 right))
shortestPath2 (Node (c, pt) left EmptyTree)      = (c + fst (shortestPath2 left), pt : snd (shortestPath2 left))
shortestPath2 (Node (c, pt) left@(Node (lcost, _) _ _) right@(Node (rcost, _) _ _)) = 
                                 (c + fst (shortestPath2 next), pt : snd (shortestPath2 next))
                                       where next = if lcost < rcost then left else right


test3 :: (Int, String)
test3 = result 
        where path1 = (Node (50, 'A') (Node (30, 'C') (Node (90, 'D') (Node (0, 'E') EmptyTree EmptyTree) EmptyTree) EmptyTree)
                                     (Node (5, 'C') (Node (0, 'E') EmptyTree EmptyTree) EmptyTree)) 

              path2 = (Node (10, 'B') (Node (30, 'D') (Node (5, 'C') (Node (0, 'E') EmptyTree EmptyTree) EmptyTree) EmptyTree)
                                      (Node (90, 'D') (Node (0, 'F') EmptyTree EmptyTree) EmptyTree))

              sp1 = shortestPath2 path1
              sp2 = shortestPath2 path2
              compare first@(cost1, _) second@(cost2, _) = if cost1 < cost2 then first else second
              result = compare sp1 sp2

Output

ghci> test3
(45,"BDCE")

Answer 1

Data representation

My critique starts here:

data Tree a = EmptyTree | Node a (Tree a) (Tree a)

Why is a node forced to have 2 sub-trees? Given a graph like this:

    B1 - C1
     |    |
A - B2 - C2
     |    |
    B3 - C3

you cannot represent B2 properly. I'd use

data Tree a = EmptyTree | Node a [Tree a]

for an arbitrary number of subtrees. Even the EmptyTree constructor might turn out to be unnecessary.

Try to rewrite your code with that, and see that the code duplication in the shortestPath2 definitions is reduced.

Use let and pattern matching

In an expression like

(c + fst (shortestPath2 right), pt : snd (shortestPath2 right))

you calculate shortestPath2 right twice and calls to fst and snd can often be avoided with pattern matching.

let (cs,pts) = shortestPath2 right in (c + cs, pt : pts)

Layout

path1 = (Node (50, 'A') (Node (30, 'C') (Node (90, 'D') (Node (0, 'E') EmptyTree EmptyTree) EmptyTree) EmptyTree)
                                       (Node (5, 'C') (Node (0, 'E') EmptyTree EmptyTree) EmptyTree))

is very hard to scan this by the eye. Only whitespace change, and it looks like this:

    where path1 = (Node (50, 'A') 
                      (Node (30, 'C')
                          (Node (90, 'D')
                              (Node ( 0, 'E') EmptyTree EmptyTree)
                               EmptyTree)
                           EmptyTree)
                      (Node (5, 'C') -- should be 'D'
                              (Node (0, 'E') EmptyTree EmptyTree) 
                               EmptyTree)) 

You actually have 'C' twice as successor to 'A'. Change path1 to a top-level definition to access it in ghci. Then type let (Node _ a b) = path1 and then a and b into ghci. The latter should be 'D', just a typo. The data representation is confusing me! The data is a graph, and graphs distinguish between edges and nodes. A,... are nodes, the numbers in between are edges. I would not group them like (50, 'A'). I hope someone else can give you a good pointer here.

BTW path1 is a misnomer. It is not a path. "BDCE" might be a path. path1 is a graph rolled out to a tree (without loops)?

Algorithmic

I used a Node data structure (compliments of LYAH's previous chapter) to recurse through the shorter left or right sides.

You are technically right. It only scans then next section of the path and uses the shorter one. Your algorithm is greedy and does not find the global optimum. Change the 90 into 31, the shortest path should be "BDF", but your output of test3 does not change.

In General

At first I was confused, because I'd expect a function like

`shortestPath from to path1`

where from and to are origin and destination nodes. In your code, the destination is not coded at all. The problem states get from A or B to E or F, but single nodes are enough:

You can insert a virtual node

`london = Node ('V',0) path1 path2`

and you test function looks like

test4 = shortestPath2 london where
        --path1 = -- see above
        --path2 = -- see above
        london = Node (0,'V') path1 path2

Which looks better than test3.

Conclusion

I will address the biggest problem - that you algorithm does not find the optimum - in a later edit (or leave it for someone else to answer).