summaryrefslogtreecommitdiff
path: root/80-89/87.hs
diff options
context:
space:
mode:
Diffstat (limited to '80-89/87.hs')
-rw-r--r--80-89/87.hs18
1 files changed, 18 insertions, 0 deletions
diff --git a/80-89/87.hs b/80-89/87.hs
new file mode 100644
index 0000000..0c119e3
--- /dev/null
+++ b/80-89/87.hs
@@ -0,0 +1,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