HTDP 28.1 translated into Haskell

htdp_28_1_haskell.hs

-- translating http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-35.html#node_chap_28 to Haskell, 
-- making use of Maybe, pattern matching, and type aliases


-- 28.1 Finding routes in a cycle-free directed graph

type Node = Char
type Graph = [(Node,[Node])]
type Route = [Node]

findRoute :: Graph -> Node -> Node -> Maybe Route
findRoute g orig dest
    | orig == dest = Just [dest]
    | otherwise = 
        let possibleRoute = findRouteList g (neighbours g orig) dest
        in case possibleRoute of
                Nothing -> Nothing
                Just route -> Just (orig : route)

findRouteList :: Graph -> [Node] -> Node -> Maybe Route
findRouteList _ [] _ = Nothing
findRouteList g (orig : restOrig) dest =
    let possibleRoute = findRoute g orig dest
    in case possibleRoute of
            Nothing -> findRouteList g restOrig dest
            Just route -> Just route

neighbours :: Graph -> Node -> [Node]
neighbours graph orig = head [neigh | (node, neigh) <- graph, node == orig]

graph :: Graph
graph = [('A',['B','E']),
         ('B',['E','F']),
         ('C',['D']),
         ('D',[]),
         ('E',['C','F']),
         ('F',['D','G']),
         ('G',[])]

t1 = findRoute graph 'A' 'D' == Just "ABECD"
t2 = findRoute graph 'B' 'C' == Just "BEC"
t3 = findRoute graph 'G' 'A' == Nothing

allNodes :: Graph -> [Node]
allNodes g = [n | (n, _) <- g]

testAllNodes :: Graph -> [(Node, Node, Maybe Route)]
testAllNodes g =
    let nodes = allNodes g
    in [(x, y, findRoute g x y) | x <- nodes, y <- nodes, x /= y]