Graph algorithms and data structures:
too imperative
Algebraic data types are inductive:
there is exactly one way to construct them
Consider lists:
data List a = Nil | Cons a (List a)
one way to construct
Nil Cons 1 (Cons 2 Nil)
one way to deconstruct
case list of Nil -> ... Cons x xs -> ...
Graph construction — implementation detail
nodes are not ordered
View graphs as inductive
Decompose into:
data Context = Context [Node] Node [Node] data View = Context :& Graph
(ignoring node and edge labels)
([4, 5, 6], 1, []) :& graph
the rest of the graph
match
recurse
([5, 6, 7], 2, []) :& graph
matchAny :: Graph -> View
foo :: Graph -> ... foo graph | isEmpty graph = ... foo (matchAny -> ctx :& rest) = ...
match :: Node -> Graph -> Maybe View
Nothing
if not in graphdfs :: [Node] -> Graph -> [Node] dfs [] _ = [] dfs (x:xs) (match x -> Just (ctx :& g)) = x : dfs (neighbors ctx ++ xs) g dfs (_:xs) graph = dfs xs graph
stack: []
result: []
stack: [4, 5, 6]
result: [1]
stack: [7, 5, 6]
result: [1, 4]
stack: [2, 3, 5, 6]
result: [1, 4, 7]
stack: [5, 6, 5, 6]
result: [1, 4, 7, 2]
stack: [6, 5, 6]
result: [1, 4, 7, 2, 5]
stack: [3, 5, 6]
result: [1, 4, 7, 2, 5, 6]
stack: [5, 6]
result: [1, 4, 7, 2, 5, 6, 3]
fgl
library
Journal of Functional Programming, Vol. 11,
No. 5, 467-492, 2001
Created by Tikhon Jelvis.