Inductive Graphs (Functional Graph Library)
Tikhon Jelvis (tikhon@jelv.is)
Press → key to advance.
Zoom in/out: Ctrl or Command + +/-
1 Graphs
- graphs are tricky in functional programming
- but what's easy?
- lists
- trees
2 Pattern Matching
- why?
- we can pattern match on trees and lists!
foo [] = [] foo (x:xs) = bar x : foo xs
- computation follows the "shape" of the type
3 Inductive Data Types
- lists have exactly one decomposition at any given point
- reverse of how they are constructed
- "inductive data types":
data [a] = [] -- base case | a : [a] -- recursive case
4 Inductive Graphs?
- can we do the same for graphs?
- no
- a graph does not have a canonical decomposition
- multiple ways to construct the same graph
5 Inductive Graphs!
- we can give up on canonicity
- view graphs inductively
- multiple possible views
- graphs aren't actually built this way
- library: fgl
6 Type
- decompose graph into:
- a node
- its edges
- the rest of the graph
data Graph = Empty | (Context [Edge] Node [Edge]) :& Graph
- ignoring node/edge labels
7 Demo
8 Demo
9 Demo
10 Demo
11 DFS
- a depth-first search, producing a list of nodes:
dfs (x:xs) (match x -> (Just ctx, g)) = x : dfs (neighbors' ctx ++ xs) g dfs (_:xs) graph = dfs xs graph
- base cases: empty stack or empty graph
12 DFS
-stack: [1]
13 DFS
-stack: [5, 4, 6]
14 DFS
-stack: [2, 8, 9, 4, 6]
15 DFS
-stack: [7, 6, 8, 9, 4, 6]
16 DFS
-stack: [4, 3, 6, 8, 9, 4, 6]
17 DFS
-stack: [10, 4, 3, 6, 8, 9, 4, 6]
18 DFS
-stack: [8, 9, 4, 3, 6, 8, 9, 4, 6]
19 DFS
-stack: [3, 9, 4, 3, 6, 8, 9, 4, 6]
20 DFS
-stack: [6, 9, 4, 3, 6, 8, 9, 4, 6]
21 DFS
-stack: [9, 9, 4, 3, 6, 8, 9, 4, 6]
22 DFS
-stack: [9, 4, 3, 6, 8, 9, 4, 6]