Walking a maze breadth first

Chapter11.hs

module Chapter11 where

import Data.List (find, transpose)

data Maze = Maze String [Maze]

unsafeFind :: (a -> Bool) -> [a] -> a
unsafeFind p xs = let Just x = find p xs
                  in x

shortestPath :: Maze -> Maze -> [String]
shortestPath m (Maze s2 _) = unsafeFind ((== s2) . last) (paths m)

-- | all possible paths, breadth first (1steppers, 2steppers, 3steppers, .. infitiny ..)
paths :: Maze -> [[String]]
paths (Maze name mazes) = map (name:) -- all paths go through here
                        . ([] :)      -- one path ends here (0 steps)
                        . concat      -- flatten them
                        . transpose   -- combine maze-steps per level, since they are all infinite
                        . map paths   -- recurse down
                        $ mazes


-- a = Maze "a" [b, c]
-- b = Maze "b" [a, d]
-- c = Maze "c" [a, d]
-- d = Maze "d" [b, c]

-- *Chapter11> shortestPath a b
-- ["a","b"]
-- *Chapter11> shortestPath a d
-- ["a","b","d"]
-- *Chapter11> shortestPath b d
-- ["b","d"]
-- *Chapter11> shortestPath b c
-- ["b","a","c"]