80-89/87.hs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import Data.List (partition, foldl')

data Graph a = Graph [a] [(a, a)] deriving (Show, Eq)

depthFirst :: Eq a => Graph a -> a -> [a]

depthFirst (Graph v e) s = fst $ dfs s []
    where adjust u (a, b)
              | a == u = [b]
              | b == u = [a]
              | otherwise = []
          dfs u vis
              | u `elem` vis = ([], vis)
              | otherwise = let vs = (e >>= (adjust u)) in
                                foldl' (\(s, vis') v ->
                                        let (s', vis'') = dfs v vis' in
                                            (s ++ s', vis''))
                                       ([u], u:vis) vs