Nondeterminism

Tikhon Jelvis (tikhon@jelv.is)

Press key to advance.
Zoom in/out: Ctrl or Command + +/-

1 Function Composition

2 Monads

3 Lists

  • consider m as []
  • a → [b], b → [c], a → [c]
  • different shape: tree!
  • a → [b]
    • nondeterministic function from a to b

4 List Composition

  • f <=< g
f      ⇒ [b]
x      ⇒ a
map g  ⇒ [[c]]
concat ⇒ [c]
  • so for lists, join = concat

5 A Lazy Tree

img/tree.png

  • result: [c, c, c, c, c]
    • lazy

6 Map Coloring

img/Blank_US_Map.svg

7 Map Coloring

img/out.svg

8 Step

step :: Coloring -> Vertex -> [Coloring]
step graph vertex =
  map (color vertex) possible
  where possible = 
          colors \\ neighbors vertex coloring
  • try every available color
  • if none: returns []
    • branch terminated

9 foldM

listToMaybe $ foldM step emptyColoring nodes
  • foldM encapsulates backtracking logic
    • like nested loops
    • listToMaybesafeHead
  • all works thanks to laziness