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")