Graph algorithms and data structures:

**too imperative**

- lists

- trees

- algebraic data types

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:

- a node

- its edges

- the rest of the graph

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

- matches a
**specific**node `Nothing`

if not in graph- directed graph traversal

dfs :: [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]`

- see graphs as
**inductive** - use
**directed**pattern matching - write normal functional code

`fgl`

library- labels
- directed edges
- slightly different API

- higher-order graph functions

- Generating Mazes with Inductive Graphs
- on jelv.is/blog

- “Inductive Graphs and Functional Graph Algorithms”
- Martin Erwig.
*Journal of Functional Programming, Vol. 11*,No. 5, 467-492, 2001

- Martin Erwig.

Created by Tikhon Jelvis.