## Sunday, 30 November 2008

### Calculating Journeys

`-- WARNING: contains recursive programming-- For example data, pick some imaginary flight network:data Node = Paris | London | Shanghai | NewYork | Tokyo deriving (Eq, Show)flights Paris = [London]flights London = [Paris,Shanghai,NewYork]flights Shanghai = [Tokyo,NewYork]flights NewYork = [London]flights Tokyo = [Paris,London,Shanghai]-- and a convenient data representation of the transitive closuredata Graph a = {- DeadEnd | -} a :-->: [Graph a] deriving ShowtransitiveClosure location = location :-->: map transitiveClosure (flights location){-- define the truncation of any cyclical journeysfinite visited DeadEnd = DeadEndfinite visited (location :-->: destinations) | already visited location = DeadEnd |         otherwise        = location :-->: map (finite (location : visited)) destinationsalready = flip elem-}{-- remove any 'DeadEnd's left oversimplify DeadEnd = DeadEndsimplify (location :-->: destinations) = location :-->: purge (map simplify destinations)purge = foldr cons [] where cons DeadEnd ys = ys       cons x       ys = x : ys-}-- holidays = simplify . finite [] . transitiveClosure-- but fusing the truncation and simplification into one allows the 'DeadEnd' construtor to be erased!simplifyFinite visited (location :-->: destinations) = location :-->: filter (not . already visited) (map (simplifyFinite (location : visited)) destinations)already visited (location :-->: _) = elem location visitedholidays = simplifyFinite [] . transitiveClosure-- > holidays Paris-- Paris :-->: [London :-->: [Shanghai :-->: [Tokyo :-->: [],--                                            NewYork :-->: []],--                            NewYork :-->: []]]-- > holidays London -- London :-->: [Paris :-->: [],--               Shanghai :-->: [Tokyo :-->: [Paris :-->: []],--                               NewYork :-->: []],--               NewYork :-->: []]`