+ - 0:00:00
Notes for current slide
Notes for next slide

An introduction to recursion schemes

Nicolas Rinaudo • @NicolasRinaudo • Besedo

1 / 866

Recursive Data Types

2 / 866

Linked list

Linked List

3 / 866

Linked list

Linked List - Cons

4 / 866

Linked list

Linked List - Nil

5 / 866

Linked list

Linked List - Cons

6 / 866

Linked list

Linked List - head

7 / 866

Linked list

Linked List - tail

8 / 866

Linked list

Linked list - rest

9 / 866

Linked list

Linked List - Nil

10 / 866

Linked list

sealed trait List
case class Cons(
  head: Int,
  tail: List
) extends List
case object Nil extends List
11 / 866

Linked list

sealed trait List
case class Cons(
  head: Int,
  tail: List
) extends List
case object Nil extends List
12 / 866

Linked list

sealed trait List
case class Cons(
  head: Int,
  tail: List
) extends List
case object Nil extends List
13 / 866

Linked list

sealed trait List
case class Cons(
  head: Int,
  tail: List
) extends List
case object Nil extends List
14 / 866

Linked list

sealed trait List
case class Cons(
  head: Int,
  tail: List
) extends List
case object Nil extends List
15 / 866

Linked list

sealed trait List
case class Cons(
  head: Int,
  tail: List
) extends List
case object Nil extends List
16 / 866

Linked list

sealed trait List
case class Cons(
  head: Int,
  tail: List
) extends List
case object Nil extends List
17 / 866

Linked list

val ints: List =
  Cons(3, Cons(2, Cons(1, Nil)))
18 / 866

Linked list

val ints: List =
  Cons(3, Cons(2, Cons(1, Nil)))
19 / 866

Structural Recursion

20 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints) = ???

List product

21 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints) = ???

List product

22 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints) = ???

List product

23 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints) = ???

List product: 1

24 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints) = 3 * ???

List product: 1

25 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints) = 3 * ???

List product: 1

26 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints) = 3 * ???

List product

27 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints) = 3 * ???

List product

28 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints) = 3 * 2 * ???

List product

29 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints) = 3 * 2 * ???

List product

30 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints) = 3 * 2 * ???

List product

31 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints) = 3 * 2 * ???

List product

32 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints) = 3 * 2 * 1 * ???

List product

33 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints) = 3 * 2 * 1 * ???

List product

34 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints) = 3 * 2 * 1 * ???

List product

35 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints) = 3 * 2 * 1 * ???

List product

36 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints) = 3 * 2 * 1 * 1

List product

37 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints) = 3 * 2 * 1 * 1

List product

38 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints)
// res0: Int = 6
39 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints)
40 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints)
41 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints)
42 / 866

Product

def product(
  values: List
): Int =
  values match {
    case Cons(head, tail) => head * product(tail)
    case Nil              => 1
  }
product(ints)
43 / 866

String representation

def mkString(
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + mkString(tail)
    case Nil              => "nil"
  }
44 / 866

String representation

def mkString(
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + mkString(tail)
    case Nil              => "nil"
  }
45 / 866

String representation

def mkString(
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + mkString(tail)
    case Nil              => "nil"
  }
46 / 866

String representation

def mkString(
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + mkString(tail)
    case Nil              => "nil"
  }
47 / 866

String representation

def mkString(
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + mkString(tail)
    case Nil              => "nil"
  }
48 / 866

String representation

def mkString(
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + mkString(tail)
    case Nil              => "nil"
  }
49 / 866

String representation

def mkString(
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + mkString(tail)
    case Nil              => "nil"
  }
50 / 866

String representation

def mkString(
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + mkString(tail)
    case Nil              => "nil"
  }
51 / 866

String representation

def mkString(
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + mkString(tail)
    case Nil              => "nil"
  }
52 / 866

String representation

def mkString(
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + mkString(tail)
    case Nil              => "nil"
  }
mkString(ints)
// res1: String = 3 :: 2 :: 1 :: nil
53 / 866

Key takeaways

Structural recursion works by:

54 / 866

Key takeaways

Structural recursion works by:

  • providing a solution to the smallest problem.
55 / 866

Key takeaways

Structural recursion works by:

  • providing a solution to the smallest problem.

  • for larger problems: relying on the solution to smaller problems.

56 / 866

Key takeaways

Structural recursion works by:

  • providing a solution to the smallest problem.

  • for larger problems: relying on the solution to smaller problems.

  • if this makes you think of proof by induction, well done.

57 / 866

Generalised structural recursion

58 / 866

Generalising mkString

def mkString(
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + mkString(tail)
    case Nil              => "nil"
  }
59 / 866

Generalising mkString

def mkString(
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + mkString(tail)
    case Nil              => "nil"
  }
60 / 866

Generalising mkString

def recurse(
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + recurse(tail)
    case Nil              => "nil"
  }
61 / 866

Generalising mkString

def recurse(
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + recurse(tail)
    case Nil              => "nil"
  }
recurse(ints)
// res2: String = 3 :: 2 :: 1 :: nil
62 / 866

Generalising mkString

fold - step 1

63 / 866

Generalising mkString

fold - overview

64 / 866

Generalising mkString

fold - overview

65 / 866

Generalising mkString

fold - overview

66 / 866

Generalising mkString

fold - overview

67 / 866

Generalising mkString

fold - overview

68 / 866

Generalising mkString

fold - overview

69 / 866

Generalising mkString

fold - overview

70 / 866

Generalising the base case

fold - base case

71 / 866

Generalising the base case

def recurse(
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + recurse(tail)
    case Nil              => "nil"
  }
72 / 866

Generalising the base case

def recurse(
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + recurse(tail)
    case Nil              => "nil"
  }
​val base = "nil"
73 / 866

Generalising the base case

def recurse(
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + recurse(tail)
    case Nil              => "nil"
  }
val base = "nil"
74 / 866

Generalising the base case

def recurse(
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + recurse(tail)
    case Nil              => base
  }
val base = "nil"
75 / 866

Generalising the base case

def recurse(
  base  : String,
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + recurse(tail)
    case Nil              => base
  }
76 / 866

Generalising the base case

def recurse(
  base  : String,
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + recurse(base, tail)
    case Nil              => base
  }
77 / 866

Generalising the base case

def recurse(
  base  : String,
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + recurse(base, tail)
    case Nil              => base
  }
recurse(base, ints)
// res3: String = 3 :: 2 :: 1 :: nil
78 / 866

Generalising the base case

fold - base case

79 / 866

Generalising the base case

fold - base case

80 / 866

Generalising the step

fold - step case

81 / 866

Generalising the step

def recurse(
  base  : String,
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + recurse(base, tail)
    case Nil              => base
  }
82 / 866

Generalising the step

def recurse(
  base  : String,
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + recurse(base, tail)
    case Nil              => base
  }
83 / 866

Generalising the step

def recurse(
  base  : String,
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + recurse(base, tail)
    case Nil              => base
  }
84 / 866

Generalising the step

def recurse(
  base  : String,
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + recurse(base, tail)
    case Nil              => base
  }
def step(head: Int, tailResult: String) =
  head + " :: " + tailResult
85 / 866

Generalising the step

def recurse(
  base  : String,
  values: List
): String =
  values match {
    case Cons(head, tail) => head + " :: " + recurse(base, tail)
    case Nil              => base
  }
def step(head: Int, tailResult: String) =
  head + " :: " + tailResult
86 / 866

Generalising the step

def recurse(
  base  : String,
  values: List
): String =
  values match {
    case Cons(head, tail) => step(head, recurse(base, tail))
    case Nil              => base
  }
def step(head: Int, tailResult: String) =
  head + " :: " + tailResult
87 / 866

Generalising the step

def recurse(
  base  : String,
  step  : (Int, String) => String,
  values: List
): String =
  values match {
    case Cons(head, tail) => step(head, recurse(base, tail))
    case Nil              => base
  }
88 / 866

Generalising the step

def recurse(
  base  : String,
  step  : (Int, String) => String,
  values: List
): String =
  values match {
    case Cons(head, tail) => step(head, recurse(base, step, tail))
    case Nil              => base
  }
89 / 866

Generalising the step

def recurse(
  base  : String,
  step  : (Int, String) => String,
  values: List
): String =
  values match {
    case Cons(head, tail) => step(head, recurse(base, step, tail))
    case Nil              => base
  }
recurse(base, step, ints)
// res4: String = 3 :: 2 :: 1 :: nil
90 / 866

Generalising the step

fold - step case

91 / 866

Generalising the step

fold - step case

92 / 866

Generalising the return type

fold - return type

93 / 866

Generalising the return type

def recurse(
  base  : String,
  step  : (Int, String) => String,
  values: List
): String =
  values match {
    case Cons(head, tail) => step(head, recurse(base, step, tail))
    case Nil              => base
  }
94 / 866

Generalising the return type

def recurse[A](
  base  : String,
  step  : (Int, String) => String,
  values: List
): String =
  values match {
    case Cons(head, tail) => step(head, recurse(base, step, tail))
    case Nil              => base
  }
95 / 866

Generalising the return type

def recurse[A](
  base  : String,
  step  : (Int, String) => String,
  values: List
): String =
  values match {
    case Cons(head, tail) => step(head, recurse(base, step, tail))
    case Nil              => base
  }
96 / 866

Generalising the return type

def recurse[A](
  base  : A,
  step  : (Int, A) => A,
  values: List
): A =
  values match {
    case Cons(head, tail) => step(head, recurse(base, step, tail))
    case Nil              => base
  }
97 / 866

Generalising the return type

def recurse[A](
  base  : A,
  step  : (Int, A) => A,
  values: List
): A =
  values match {
    case Cons(head, tail) => step(head, recurse(base, step, tail))
    case Nil              => base
  }
recurse(base, step, ints)
// res5: String = 3 :: 2 :: 1 :: nil
98 / 866

Generalising the return type

fold - return type

99 / 866

Generalising the return type

fold - return type

100 / 866

Generalising the return type

fold - return type

101 / 866

Simplifying the step

def recurse[A](
  base  : A,
  step  : (Int, A) => A,
  values: List
): A =
  values match {
    case Cons(head, tail) => step(head, recurse(base, step, tail))
    case Nil              => base
  }
102 / 866

Simplifying the step

def recurse[A](
  base  : A,
  step  : (Int, A) => A,
  values: List
): A =
  values match {
    case Cons(head, tail) => step(head, recurse(base, step, tail))
    case Nil              => base
  }
103 / 866

Simplifying the step

def recurse[A](
  base  : A,
  step  : (Int, A) => A,
  values: List
): A =
  values match {
    case Cons(head, tail) => step(head, recurse(base, step, tail))
    case Nil              => base
  }
104 / 866

Simplifying the step

def recurse[A](
  base  : A,
  step  : (Int, A) => A,
  values: List
): A =
  values match {
    case Cons(head, tail) => step(head, recurse(base, step, tail))
    case Nil              => base
  }
105 / 866

Simplifying the step

def recurse[A](
  base  : A,
  step  : (Int, A) => A,
  values: List
): A =
  values match {
    case Cons(head, tail) => step(head, recurse(base, step, tail))
    case Nil              => base
  }
106 / 866

Simplifying the step

def recurse[A](
  base  : A,
  step  : (Int, A) => A,
  values: List
): A = {
  def loop(state: List): A =
    state match {
      case Cons(head, tail) => step(head, loop(tail))
      case Nil              => base
    }
  loop(values)
}
107 / 866

Simplifying the step

def recurse[A](
  base  : A,
  step  : (Int, A) => A,
  values: List
): A = {
  def loop(state: List): A =
    state match {
      case Cons(head, tail) => step(head, loop(tail))
      case Nil              => base
    }
  loop(values)
}
108 / 866

Simplifying the step

def recurse[A](
  base  : A,
  step  : (Int, A) => A,
  values: List
): A = {
  def loop(state: List): A =
    state match {
      case Cons(head, tail) => step(head, loop(tail))
      case Nil              => base
    }
  loop(values)
}
109 / 866

Simplifying the step

def recurse[A](
  base  : A,
  step  : (Int, A) => A,
  values: List
): A = {
  def loop(state: List): A =
    state match {
      case Cons(head, tail) => step(head, loop(tail))
      case Nil              => base
    }
  loop(values)
}
110 / 866

Simplifying the step

def recurse[A](
  base  : A,
  step  : (Int, A) => A,
  values: List
): A = {
  def loop(state: List): A =
    state match {
      case Cons(head, tail) => step(head, loop(tail))
      case Nil              => base
    }
  loop(values)
}
111 / 866

Simplifying the step

def recurse[A](
  base  : A,
  step  : (Int, A) => A,
  values: List
): A = {
  def loop(state: List): A =
    state match {
      case Cons(head, tail) => step(head, loop(tail))
      case Nil              => base
    }
  loop(values)
}
recurse(base, step, ints)
// res6: String = 3 :: 2 :: 1 :: nil
112 / 866

Simplifying the step

fold - recurse to loop

113 / 866

Simplifying the step

fold - recurse to loop

114 / 866

Simplifying the step

fold - recurse to loop

115 / 866

Dropping parameters

def recurse[A](
  base  : A,
  step  : (Int, A) => A,
  values: List
): A = {
  def loop(state: List): A =
    state match {
      case Cons(head, tail) => step(head, loop(tail))
      case Nil              => base
    }
  loop(values)
}
116 / 866

Dropping parameters

def recurse[A](
  base: A,
  step: (Int, A) => A
): A = {
  def loop(state: List): A =
    state match {
      case Cons(head, tail) => step(head, loop(tail))
      case Nil              => base
    }
  loop
}
117 / 866

Dropping parameters

def recurse[A](
  base: A,
  step: (Int, A) => A
): A = {
  def loop(state: List): A =
    state match {
      case Cons(head, tail) => step(head, loop(tail))
      case Nil              => base
    }
  loop
}
118 / 866

Dropping parameters

def recurse[A](
  base: A,
  step: (Int, A) => A
): List => A = {
  def loop(state: List): A =
    state match {
      case Cons(head, tail) => step(head, loop(tail))
      case Nil              => base
    }
  loop
}
119 / 866

Dropping parameters

def recurse[A](
  base: A,
  step: (Int, A) => A
): List => A = {
  def loop(state: List): A =
    state match {
      case Cons(head, tail) => step(head, loop(tail))
      case Nil              => base
    }
  loop
}
recurse(base, step)(ints)
// res7: String = 3 :: 2 :: 1 :: nil
120 / 866

Dropping parameters

def mkString(ints: List): String =
  recurse(base, step)(ints)
121 / 866

Dropping parameters

def mkString(ints: List): String =
  recurse(base, step)(ints)
122 / 866

Dropping parameters

def mkString: String =
  recurse(base, step)
123 / 866

Dropping parameters

def mkString: List => String =
  recurse(base, step)
124 / 866

Dropping parameters

​def mkString: List => String =
  recurse(base, step)
125 / 866

Dropping parameters

​val mkString: List => String =
  recurse(base, step)
126 / 866

Dropping parameters

val mkString: List => String =
  recurse(base, step)
mkString(ints)
// res8: String = 3 :: 2 :: 1 :: nil
127 / 866

Naming things

def recurse[A](
  base: A,
  step: (Int, A) => A
): List => A = {
  def loop(state: List): A =
    state match {
      case Cons(head, tail) => step(head, loop(tail))
      case Nil              => base
    }
  loop
}
128 / 866

Naming things

def fold[A](
  base: A,
  step: (Int, A) => A
): List => A = {
  def loop(state: List): A =
    state match {
      case Cons(head, tail) => step(head, loop(tail))
      case Nil              => base
    }
  loop
}
129 / 866

Naming things

def fold[A](
  base: A,
  step: (Int, A) => A
): List => A = {
  def loop(state: List): A =
    state match {
      case Cons(head, tail) => step(head, loop(tail))
      case Nil              => base
    }
  loop
}
fold(base, step)(ints)
// res9: String = 3 :: 2 :: 1 :: nil
130 / 866

product as a fold

val product: List => Int =
  fold[Int](
    base = 1,
    step = (head, tailProduct) => head * tailProduct
  )
131 / 866

product as a fold

val product: List => Int =
  fold[Int](
    base = 1,
    step = (head, tailProduct) => head * tailProduct
  )
132 / 866

product as a fold

val product: List => Int =
  fold[Int](
    base = 1,
    step = (head, tailProduct) => head * tailProduct
  )
133 / 866

product as a fold

val product: List => Int =
  fold[Int](
    base = 1,
    step = (head, tailProduct) => head * tailProduct
  )
134 / 866

product as a fold

val product: List => Int =
  fold[Int](
    base = 1,
    step = (head, tailProduct) => head * tailProduct
  )
product(ints)
// res10: Int = 6
135 / 866

Key takeaways

Structural recursion is generalised by:

136 / 866

Key takeaways

Structural recursion is generalised by:

  • parameterising the base case.
137 / 866

Key takeaways

Structural recursion is generalised by:

  • parameterising the base case.

  • parameterising the step.

138 / 866

Key takeaways

Structural recursion is generalised by:

  • parameterising the base case.

  • parameterising the step.

  • ... knowing the structure of your type.

139 / 866

Generalised folds

140 / 866

Generalised folds

def fold[A](
  base: A,
  step: (Int, A) => A
): List => A = {
  def loop(state: List): A =
    state match {
      case Cons(head, tail) => step(head, loop(tail))
      case Nil              => base
    }
  loop
}
141 / 866

Generalised folds

Cata step 1

142 / 866

Abstracting over structure

Cata step 1

143 / 866

Abstracting over structure

def fold[A](
  base: A,
  step: (Int, A) => A
): List => A = {
  def loop(state: List): A =
    state match {
      case Cons(head, tail) => step(head, loop(tail))
      case Nil              => base
    }
  loop
}
144 / 866

List projection

val project: List => Option[(Int, List)] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
145 / 866

List projection

val project: List => Option[(Int, List)] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
146 / 866

List projection

val project: List => Option[(Int, List)] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
147 / 866

List projection

val project: List => Option[(Int, List)] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
148 / 866

List projection

val project: List => Option[(Int, List)] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
149 / 866

List projection

val project: List => Option[(Int, List)] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
150 / 866

Abstracting over structure

def fold[A](
  base: A,
  step: (Int, A) => A
): List => A = {
  def loop(state: List): A =
    state match {
      case Cons(head, tail) => step(head, loop(tail))
      case Nil              => base
    }
  loop
}
151 / 866

Abstracting over structure

def fold[A](
  base: A,
  step: (Int, A) => A
): List => A = {
  def loop(state: List): A =
    project(state) match {
      case Cons(head, tail) => step(head, loop(tail))
      case Nil              => base
    }
  loop
}
152 / 866

Abstracting over structure

def fold[A](
  base: A,
  step: (Int, A) => A
): List => A = {
  def loop(state: List): A =
    project(state) match {
      case Cons(head, tail) => step(head, loop(tail))
      case Nil              => base
    }
  loop
}
153 / 866

Abstracting over structure

def fold[A](
  base: A,
  step: (Int, A) => A
): List => A = {
  def loop(state: List): A =
    project(state) match {
      case Some((head, tail)) => step(head, loop(tail))
      case Nil                => base
    }
  loop
}
154 / 866

Abstracting over structure

def fold[A](
  base: A,
  step: (Int, A) => A
): List => A = {
  def loop(state: List): A =
    project(state) match {
      case Some((head, tail)) => step(head, loop(tail))
      case Nil                => base
    }
  loop
}
155 / 866

Abstracting over structure

def fold[A](
  base: A,
  step: (Int, A) => A
): List => A = {
  def loop(state: List): A =
    project(state) match {
      case Some((head, tail)) => step(head, loop(tail))
      case None               => base
    }
  loop
}
156 / 866

Abstracting over structure

def fold[A](
  base: A,
  step: (Int, A) => A
): List => A = {
  def loop(state: List): A =
    project(state) match {
      case Some((head, tail)) => step(head, loop(tail))
      case None               => base
    }
  loop
}
157 / 866

Abstracting over structure

def fold[A](
  base   : A,
  step   : (Int, A) => A,
  project: List => Option[(Int, List)]
): List => A = {
  def loop(state: List): A =
    project(state) match {
      case Some((head, tail)) => step(head, loop(tail))
      case None               => base
    }
  loop
}
158 / 866

Abstracting over structure

def fold[A](
  base   : A,
  step   : (Int, A) => A,
  project: List => Option[(Int, List)]
): List => A = {
  def loop(state: List): A =
    project(state) match {
      case Some((head, tail)) => step(head, loop(tail))
      case None               => base
    }
  loop
}
fold(base, step, project)(ints)
// res11: String = 3 :: 2 :: 1 :: nil
159 / 866

Abstracting over structure

Cata step 1

160 / 866

Abstracting over structure

Cata step 2

161 / 866

Abstracting over structure

Cata step 2

162 / 866

Simplifying base and step

Cata step 2

163 / 866

Simplifying base and step

def fold[A](
  base   : A,
  step   : (Int, A) => A,
  project: List => Option[(Int, List)]
): List => A = {
  def loop(state: List): A =
    project(state) match {
      case Some((head, tail)) => step(head, loop(tail))
      case None               => base
    }
  loop
}
164 / 866

Simplifying base and step

val op: Option[(Int, String)] => String = {
  case Some((head, tailResult)) => step(head, tailResult)
  case None                     => base
}
165 / 866

Simplifying base and step

val op: Option[(Int, String)] => String = {
  case Some((head, tailResult)) => step(head, tailResult)
  case None                     => base
}
166 / 866

Simplifying base and step

val op: Option[(Int, String)] => String = {
  case Some((head, tailResult)) => step(head, tailResult)
  case None                     => base
}
167 / 866

Simplifying base and step

val op: Option[(Int, String)] => String = {
  case Some((head, tailResult)) => step(head, tailResult)
  case None                     => base
}
168 / 866

Simplifying base and step

val op: Option[(Int, String)] => String = {
  case Some((head, tailResult)) => head + " :: " + tailResult
  case None                     => base
}
169 / 866

Simplifying base and step

val op: Option[(Int, String)] => String = {
  case Some((head, tailResult)) => head + " :: " + tailResult
  case None                     => base
}
170 / 866

Simplifying base and step

val op: Option[(Int, String)] => String = {
  case Some((head, tailResult)) => head + " :: " + tailResult
  case None                     => base
}
171 / 866

Simplifying base and step

val op: Option[(Int, String)] => String = {
  case Some((head, tailResult)) => head + " :: " + tailResult
  case None                     => "nil"
}
172 / 866

Simplifying base and step

val op: Option[(Int, String)] => String = {
  case Some((head, tailResult)) => head + " :: " + tailResult
  case None                     => "nil"
}
173 / 866

Simplifying base and step

def fold[A](
  base   : A,
  step   : (Int, A) => A,
  project: List => Option[(Int, List)]
): List => A = {
  def loop(state: List): A =
    project(state) match {
      case Some((head, tail)) => step(head, loop(tail))
      case None               => base
    }
  loop
}
174 / 866

Simplifying base and step

def fold[A](
  op     : Option[(Int, A)] => A,
  project: List => Option[(Int, List)]
): List => A = {
  def loop(state: List): A =
    project(state) match {
      case Some((head, tail)) => step(head, loop(tail))
      case None               => base
    }
  loop
}
175 / 866

Simplifying base and step

def fold[A](
  op     : Option[(Int, A)] => A,
  project: List => Option[(Int, List)]
): List => A = {
  def loop(state: List): A =
    project(state) match {
      case Some((head, tail)) => step(head, loop(tail))
      case None               => base
    }
  loop
}
176 / 866

Simplifying base and step

def fold[A](
  op     : Option[(Int, A)] => A,
  project: List => Option[(Int, List)]
): List => A = {
  def loop(state: List): A =
    project(state) match {
      case Some((head, tail)) => op(Some((head, loop(tail))))
      case None               => base
    }
  loop
}
177 / 866

Simplifying base and step

def fold[A](
  op     : Option[(Int, A)] => A,
  project: List => Option[(Int, List)]
): List => A = {
  def loop(state: List): A =
    project(state) match {
      case Some((head, tail)) => op(Some((head, loop(tail))))
      case None               => base
    }
  loop
}
178 / 866

Simplifying base and step

def fold[A](
  op     : Option[(Int, A)] => A,
  project: List => Option[(Int, List)]
): List => A = {
  def loop(state: List): A =
    project(state) match {
      case Some((head, tail)) => op(Some((head, loop(tail))))
      case None               => op(None)
    }
  loop
}
179 / 866

Simplifying base and step

def fold[A](
  op     : Option[(Int, A)] => A,
  project: List => Option[(Int, List)]
): List => A = {
  def loop(state: List): A =
    project(state) match {
      case Some((head, tail)) => op(Some((head, loop(tail))))
      case None               => op(None)
    }
  loop
}
fold(op, project)(ints)
// res12: String = 3 :: 2 :: 1 :: nil
180 / 866

Simplifying base and step

Cata step 2

181 / 866

Simplifying base and step

Cata step 3

182 / 866

Simplifying base and step

def fold[A](
  op     : Option[(Int, A)] => A,
  project: List => Option[(Int, List)]
): List => A = {
  def loop(state: List): A =
    project(state) match {
      case Some((head, tail)) => op(Some((head, loop(tail))))
      case None               => op(None)
    }
  loop
}
183 / 866

Simplifying base and step

def fold[A](
  op     : Option[(Int, A)] => A,
  project: List => Option[(Int, List)]
): List => A = {
  def loop(state: List): A =
    op(project(state) match {
      case Some((head, tail)) => Some((head, loop(tail)))
      case None               => None
    })
  loop
}
184 / 866

Simplifying base and step

def fold[A](
  op     : Option[(Int, A)] => A,
  project: List => Option[(Int, List)]
): List => A = {
  def loop(state: List): A =
    op(project(state) match {
      case Some((head, tail)) => Some((head, loop(tail)))
      case None               => None
    })
  loop
}
fold(op, project)(ints)
// res13: String = 3 :: 2 :: 1 :: nil
185 / 866

Simplifying base and step

Cata step 3

186 / 866

Simplifying base and step

Cata step 4

187 / 866

Simplifying base and step

Cata step 4

188 / 866

Intermediate representation

Cata step 4

189 / 866

Intermediate representation

type ListF[A] = Option[(Int, A)]
190 / 866

Intermediate representation

type ListF[A] = Option[(Int, A)]
191 / 866

Intermediate representation

type ListF[A] = Option[(Int, A)]
192 / 866

Intermediate representation

type ListF[A] = Option[(Int, A)]
val project: List => ListF[List] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
193 / 866

Intermediate representation

type ListF[A] = Option[(Int, A)]
val project: List => ListF[List] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
194 / 866

Intermediate representation

type ListF[A] = Option[(Int, A)]
val op: ListF[String] => String = {
  case Some((head, tailResult)) => head + " :: " + tailResult
  case None                     => "nil"
}
195 / 866

Intermediate representation

type ListF[A] = Option[(Int, A)]
val op: ListF[String] => String = {
  case Some((head, tailResult)) => head + " :: " + tailResult
  case None                     => "nil"
}
196 / 866

Intermediate representation

def fold[A](
  op     : Option[(Int, A)] => A,
  project: List => Option[(Int, List)]
): List => A = {
  def loop(state: List): A =
    op(project(state) match {
      case Some((head, tail)) => Some((head, loop(tail)))
      case None               => None
    })
  loop
}
197 / 866

Intermediate representation

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(project(state) match {
      case Some((head, tail)) => Some((head, loop(tail)))
      case None               => None
    })
  loop
}
198 / 866

Intermediate representation

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(project(state) match {
      case Some((head, tail)) => Some((head, loop(tail)))
      case None               => None
    })
  loop
}
fold(op, project)(ints)
// res14: String = 3 :: 2 :: 1 :: nil
199 / 866

Intermediate representation

Cata step 4

200 / 866

Intermediate representation

Cata step 5

201 / 866

Generalising recursion

Cata step 5

202 / 866

Generalising recursion

Cata step 5

203 / 866

Generalising recursion

Cata step 5

204 / 866

Generalising recursion

Cata step 5

205 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(project(state) match {
      case Some((head, tail)) => Some((head, loop(tail)))
      case None               => None
    })
  loop
}
206 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(project(state) match {
      case Some((head, tail)) => Some((head, loop(tail)))
      case None               => None
    })
  loop
}
207 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(project(state) match {
      case Some((head, tail)) => Some((head, loop(tail)))
      case None               => None
    })
  loop
}
208 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(project(state) match {
      case Some((head, tail)) => Some((head, loop(tail)))
      case None               => None
    })
  loop
}
209 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(project(state) match {
      case Some((head, tail)) => Some((head, loop(tail)))
      case None               => None
    })
  loop
}
210 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(project(state) match {
      case Some((head, tail)) => Some((head, loop(tail)))
      case None               => None
    })
  loop
}
211 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(go(project(state)))
  def go(state: ListF[List]): ListF[A] =
    state match {
      case Some((head, tail)) => Some((head, loop(tail)))
      case None               => None
    }
  loop
}
212 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(go(project(state)))
  def go(state: ListF[List]): ListF[A] =
    state match {
      case Some((head, tail)) => Some((head, loop(tail)))
      case None               => None
    }
  loop
}
213 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(go(project(state)))
  def go(state: ListF[List]): ListF[A] =
    state match {
      case Some((head, tail)) => Some((head, loop(tail)))
      case None               => None
    }
  loop
}
214 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(go(project(state)))
  def go(state: ListF[List]): ListF[A] =
    state match {
      case Some((head, tail)) => Some((head, loop(tail)))
      case None               => None
    }
  loop
}
215 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(go(project(state)))
  def go(state: ListF[List]): ListF[A] =
    state match {
      case Some((head, tail)) => Some((head, loop(tail)))
      case None               => None
    }
  loop
}
216 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(go(project(state)))
  def go(state: ListF[List]): ListF[A] =
    state match {
      case Some((head, tail)) => Some((head, loop(tail)))
      case None               => None
    }
  loop
}
217 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(go(project(state)))
  def go(state: ListF[List]): ListF[A] =
    state match {
      case Some((head, tail)) => Some((head, loop(tail)))
      case None               => None
    }
  loop
}
218 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(go(project(state)))
  def go(state: ListF[List]): ListF[A] =
    state match {
      case Some((head, tail)) => Some((head, loop(tail)))
      case None               => None
    }
  loop
}
219 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(go(project(state)))
  def go(state: ListF[List], f: List => A): ListF[A] =
    state match {
      case Some((head, tail)) => Some((head, loop(tail)))
      case None               => None
    }
  loop
}
220 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(go(project(state)))
  def go(state: ListF[List], f: List => A): ListF[A] =
    state match {
      case Some((head, tail)) => Some((head, loop(tail)))
      case None               => None
    }
  loop
}
221 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(go(project(state)))
  def go(state: ListF[List], f: List => A): ListF[A] =
    state match {
      case Some((head, tail)) => Some((head, f(tail)))
      case None               => None
    }
  loop
}
222 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(go(project(state), loop))
  def go(state: ListF[List], f: List => A): ListF[A] =
    state match {
      case Some((head, tail)) => Some((head, f(tail)))
      case None               => None
    }
  loop
}
223 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(go(project(state), loop))
  def go(state: ListF[List], f: List => A): ListF[A] =
    state match {
      case Some((head, tail)) => Some((head, f(tail)))
      case None               => None
    }
  loop
}
224 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(go(project(state), loop))
  def go(state: ListF[List], f: List => A): ListF[A] =
    state match {
      case Some((head, tail)) => Some((head, f(tail)))
      case None               => None
    }
  loop
}
225 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(go(project(state), loop))
  def go(state: ListF[List], f: List => A): ListF[A] =
    state match {
      case Some((head, tail)) => Some((head, f(tail)))
      case None               => None
    }
  loop
}
226 / 866

Generalising recursion

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(go(project(state), loop))
  def go(state: ListF[List], f: List => A): ListF[A] =
    state match {
      case Some((head, tail)) => Some((head, f(tail)))
      case None               => None
    }
  loop
}
227 / 866

Functor

trait Functor[F[_]] {
  def map[A, B](fa: F[A], f: A => B): F[B]
}
228 / 866

Functor

trait Functor[F[_]] {
  def map[A, B](fa: F[A], f: A => B): F[B]
}
229 / 866

Functor

trait Functor[F[_]] {
  def map[A, B](fa: F[A], f: A => B): F[B]
}
230 / 866

Functor

trait Functor[F[_]] {
  def map[A, B](fa: F[A], f: A => B): F[B]
}
231 / 866

Functor

trait Functor[F[_]] {
  def map[A, B](fa: F[A], f: A => B): F[B]
}
232 / 866

Functor

trait Functor[F[_]] {
  def map[A, B](fa: F[A], f: A => B): F[B]
}
233 / 866

Functor

trait Functor[F[_]] {
  def map[A, B](fa: F[A], f: A => B): F[B]
}
234 / 866

Functor

implicit val listFFunctor = new Functor[ListF] {
  override def map[A, B](list: ListF[A], f: A => B) =
    list match {
      case Some((head, tail)) => Some((head, f(tail)))
      case None               => None
    }
}
235 / 866

Functor

implicit val listFFunctor = new Functor[ListF] {
  override def map[A, B](list: ListF[A], f: A => B) =
    list match {
      case Some((head, tail)) => Some((head, f(tail)))
      case None               => None
    }
}
236 / 866

Functor

implicit val listFFunctor = new Functor[ListF] {
  override def map[A, B](list: ListF[A], f: A => B) =
    list match {
      case Some((head, tail)) => Some((head, f(tail)))
      case None               => None
    }
}
237 / 866

Functor

implicit val listFFunctor = new Functor[ListF] {
  override def map[A, B](list: ListF[A], f: A => B) =
    list match {
      case Some((head, tail)) => Some((head, f(tail)))
      case None               => None
    }
}
238 / 866

Functor

implicit val listFFunctor = new Functor[ListF] {
  override def map[A, B](list: ListF[A], f: A => B) =
    list match {
      case Some((head, tail)) => Some((head, f(tail)))
      case None               => None
    }
}
239 / 866

Functor

implicit val listFFunctor = new Functor[ListF] {
  override def map[A, B](list: ListF[A], f: A => B) =
    list match {
      case Some((head, tail)) => Some((head, f(tail)))
      case None               => None
    }
}
240 / 866

Functor

implicit val listFFunctor = new Functor[ListF] {
  override def map[A, B](list: ListF[A], f: A => B) =
    list match {
      case Some((head, tail)) => Some((head, f(tail)))
      case None               => None
    }
}
241 / 866

Functor

def map[F[_], A, B](
  fa     : F[A],
  f      : A => B
)(implicit
  functor: Functor[F]
): F[B] =
  functor.map(fa, f)
242 / 866

Functor

def map[F[_], A, B](
  fa     : F[A],
  f      : A => B
)(implicit
  functor: Functor[F]
): F[B] =
  functor.map(fa, f)
243 / 866

Functor

def map[F[_], A, B](
  fa     : F[A],
  f      : A => B
)(implicit
  functor: Functor[F]
): F[B] =
  functor.map(fa, f)
244 / 866

Functor

def map[F[_], A, B](
  fa     : F[A],
  f      : A => B
)(implicit
  functor: Functor[F]
): F[B] =
  functor.map(fa, f)
245 / 866

Functor

def map[F[_], A, B](
  fa     : F[A],
  f      : A => B
)(implicit
  functor: Functor[F]
): F[B] =
  functor.map(fa, f)
246 / 866

Functor

def map[F[_], A, B](
  fa     : F[A],
  f      : A => B
)(implicit
  functor: Functor[F]
): F[B] =
  functor.map(fa, f)
247 / 866

Using Functor

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(go(project(state), loop))
  def go(state: ListF[List], f: List => A): ListF[A] =
    state match {
      case Some((head, tail)) => Some((head, f(tail)))
      case None               => None
    }
  loop
}
248 / 866

Using Functor

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(go(project(state), loop))
  def go(state: ListF[List], f: List => A): ListF[A] =
    map(state, f)
  loop
}
249 / 866

Using Functor

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(go(project(state), loop))
  def go(state: ListF[List], f: List => A): ListF[A] =
    map(state, f)
  loop
}
250 / 866

Using Functor

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(map(project(state), loop))
  def go(state: ListF[List], f: List => A): ListF[A] =
    map(state, f)
  loop
}
251 / 866

Using Functor

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(map(project(state), loop))
  def go(state: ListF[List], f: List => A): ListF[A] =
    map(state, f)
  loop
}
252 / 866

Using Functor

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(map(project(state), loop))
  loop
}
253 / 866

Using Functor

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(map(project(state), loop))
  loop
}
fold(op, project)(ints)
// res15: String = 3 :: 2 :: 1 :: nil
254 / 866

Using Functor

Cata step 5

255 / 866

Using Functor

Cata step 6

256 / 866

Abstracting over ListF

Cata step 6

257 / 866

Abstracting over ListF

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(map(project(state), loop))
  loop
}
258 / 866

Abstracting over ListF

def fold[A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(map(project(state), loop))
  loop
}
259 / 866

Abstracting over ListF

def fold[F[_]: Functor, A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(map(project(state), loop))
  loop
}
260 / 866

Abstracting over ListF

def fold[F[_]: Functor, A](
  op     : ListF[A] => A,
  project: List => ListF[List]
): List => A = {
  def loop(state: List): A =
    op(map(project(state), loop))
  loop
}
261 / 866

Abstracting over ListF

def fold[F[_]: Functor, A](
  op     : F[A] => A,
  project: List => F[List]
): List => A = {
  def loop(state: List): A =
    op(map(project(state), loop))
  loop
}
262 / 866

Abstracting over ListF

def fold[F[_]: Functor, A](
  op     : F[A] => A,
  project: List => F[List]
): List => A = {
  def loop(state: List): A =
    op(map(project(state), loop))
  loop
}
fold(op, project).apply(ints)
// res16: String = 3 :: 2 :: 1 :: nil
263 / 866

Abstracting over ListF

Cata step 6

264 / 866

Abstracting over ListF

Cata step 7

265 / 866

Abstracting over List

Cata step 7

266 / 866

Abstracting over List

def fold[F[_]: Functor, A](
  op     : F[A] => A,
  project: List => F[List]
): List => A = {
  def loop(state: List): A =
    op(map(project(state), loop))
  loop
}
267 / 866

Abstracting over List

def fold[F[_]: Functor, A, B](
  op     : F[A] => A,
  project: List => F[List]
): List => A = {
  def loop(state: List): A =
    op(map(project(state), loop))
  loop
}
268 / 866

Abstracting over List

def fold[F[_]: Functor, A, B](
  op     : F[A] => A,
  project: List => F[List]
): List => A = {
  def loop(stage: List): A =
    op(map(project(state), loop))
  loop
}
269 / 866

Abstracting over List

def fold[F[_]: Functor, A, B](
  op     : F[A] => A,
  project: B => F[B]
): B => A = {
  def loop(state: B): A =
    op(map(project(state), loop))
  loop
}
270 / 866

Abstracting over List

def fold[F[_]: Functor, A, B](
  op     : F[A] => A,
  project: B => F[B]
): B => A = {
  def loop(state: B): A =
    op(map(project(state), loop))
  loop
}
fold(op, project).apply(ints)
// res17: String = 3 :: 2 :: 1 :: nil
271 / 866

Abstracting over List

Cata step 7

272 / 866

Abstracting over List

Cata step 8

273 / 866

Abstracting over List

Cata step 8

274 / 866

Naming things

def fold[F[_]: Functor, A, B](
  op     : F[A] => A,
  project: B => F[B]
): B => A = {
  def loop(state: B): A =
    op(map(project(state), loop))
  loop
}
275 / 866

Naming things

def cata[F[_]: Functor, A, B](
  op     : F[A] => A,
  project: B => F[B]
): B => A = {
  def loop(state: B): A =
    op(map(project(state), loop))
  loop
}
276 / 866

Naming things

def cata[F[_]: Functor, A, B](
  op     : F[A] => A,
  project: B => F[B]
): B => A = {
  def loop(state: B): A =
    op(map(project(state), loop))
  loop
}
277 / 866

Naming things

def cata[F[_]: Functor, A, B](
  algebra: F[A] => A,
  project: B => F[B]
): B => A = {
  def loop(state: B): A =
    algebra(map(project(state), loop))
  loop
}
278 / 866

Naming things

def cata[F[_]: Functor, A, B](
  algebra: F[A] => A,
  project: B => F[B]
): B => A = {
  def loop(state: B): A =
    algebra(map(project(state), loop))
  loop
}
279 / 866

Naming things

def cata[F[_]: Functor, A, B](
  algebra: F[A] => A,
  project: B => F[B]
): B => A = {
  def loop(state: B): A =
    algebra(map(project(state), loop))
  loop
}
cata(op, project).apply(ints)
// res18: String = 3 :: 2 :: 1 :: nil
280 / 866

Naming things

Cata step 9

281 / 866

Naming things

Cata step 9

282 / 866

Naming things

Cata step 9

283 / 866

product as a cata

val productAlgebra: ListF[Int] => Int = {
  case Some((head, tailProduct)) => head * tailProduct
  case None                      => 1
}
val product: List => Int =
  cata(productAlgebra, project)
284 / 866

product as a cata

val productAlgebra: ListF[Int] => Int = {
  case Some((head, tailProduct)) => head * tailProduct
  case None                      => 1
}
val product: List => Int =
  cata(productAlgebra, project)
285 / 866

product as a cata

val productAlgebra: ListF[Int] => Int = {
  case Some((head, tailProduct)) => head * tailProduct
  case None                      => 1
}
val product: List => Int =
  cata(productAlgebra, project)
286 / 866

product as a cata

val productAlgebra: ListF[Int] => Int = {
  case Some((head, tailProduct)) => head * tailProduct
  case None                      => 1
}
val product: List => Int =
  cata(productAlgebra, project)
287 / 866

product as a cata

val productAlgebra: ListF[Int] => Int = {
  case Some((head, tailProduct)) => head * tailProduct
  case None                      => 1
}
val product: List => Int =
  cata(productAlgebra, project)
288 / 866

product as a cata

val productAlgebra: ListF[Int] => Int = {
  case Some((head, tailProduct)) => head * tailProduct
  case None                      => 1
}
val product: List => Int =
  cata(productAlgebra, project)
289 / 866

product as a cata

val productAlgebra: ListF[Int] => Int = {
  case Some((head, tailProduct)) => head * tailProduct
  case None                      => 1
}
val product: List => Int =
  cata(productAlgebra, project)
290 / 866

product as a cata

val productAlgebra: ListF[Int] => Int = {
  case Some((head, tailProduct)) => head * tailProduct
  case None                      => 1
}
val product: List => Int =
  cata(productAlgebra, project)
product(ints)
// res19: Int = 6
291 / 866

Key takeaways

Catamorphisms are:

292 / 866

Key takeaways

Catamorphisms are:

  • structural recursion for types that can be projected into pattern functors.
293 / 866

Key takeaways

Catamorphisms are:

  • structural recursion for types that can be projected into pattern functors.

  • far less complicated than their names make them out to be.

294 / 866

Key takeaways

Catamorphisms are:

  • structural recursion for types that can be projected into pattern functors.

  • far less complicated than their names make them out to be.

  • a simple refactoring away from the familiar fold.

295 / 866

Can this be applied to other types?

296 / 866

Binary Tree

Tree

297 / 866

Binary Tree

Tree Node

298 / 866

Binary Tree

Tree Leaf

299 / 866

Binary Tree

Tree Node

300 / 866

Binary Tree

Tree Node

301 / 866

Binary Tree

Tree Node

302 / 866

Binary Tree

Tree Node

303 / 866

Binary Tree

Tree Node

304 / 866

Binary Tree

Tree Leaf

305 / 866

Binary Tree

sealed trait Tree
case class Node(
  left : Tree,
  value: Int,
  right: Tree
) extends Tree
case object Leaf extends Tree
306 / 866

Binary Tree

sealed trait Tree
case class Node(
  left : Tree,
  value: Int,
  right: Tree
) extends Tree
case object Leaf extends Tree
307 / 866

Binary Tree

sealed trait Tree
case class Node(
  left : Tree,
  value: Int,
  right: Tree
) extends Tree
case object Leaf extends Tree
308 / 866

Binary Tree

sealed trait Tree
case class Node(
  left : Tree,
  value: Int,
  right: Tree
) extends Tree
case object Leaf extends Tree
309 / 866

Binary Tree

sealed trait Tree
case class Node(
  left : Tree,
  value: Int,
  right: Tree
) extends Tree
case object Leaf extends Tree
310 / 866

Binary Tree

sealed trait Tree
case class Node(
  left : Tree,
  value: Int,
  right: Tree
) extends Tree
case object Leaf extends Tree
311 / 866

Binary Tree

sealed trait Tree
case class Node(
  left : Tree,
  value: Int,
  right: Tree
) extends Tree
case object Leaf extends Tree
312 / 866

Binary Tree

sealed trait Tree
case class Node(
  left : Tree,
  value: Int,
  right: Tree
) extends Tree
case object Leaf extends Tree
313 / 866

Binary Tree

val intTree =
  Node(
    Node(
      Node(Leaf, 1, Leaf),
      2,
      Node(Leaf, 3, Leaf)
    ),
    4,
    Leaf
  )
// intTree: Node = Node(Node(Node(Leaf,1,Leaf),2,Node(Leaf,3,Leaf)),4,Leaf)
314 / 866

Binary Tree

val intTree =
  Node(
    Node(
      Node(Leaf, 1, Leaf),
      2,
      Node(Leaf, 3, Leaf)
    ),
    4,
    Leaf
  )
315 / 866

Tree Height

Tree Height

316 / 866

Tree Height

Tree Height

317 / 866

Tree Height

Tree catamorphism

318 / 866

Tree Height

Tree catamorphism

319 / 866

Tree Height

Tree catamorphism

320 / 866

Pattern functor

Tree catamorphism

321 / 866

Pattern functor

sealed trait Tree
case class Node(
  left : Tree,
  value: Int,
  right: Tree
) extends Tree
case object Leaf extends Tree
322 / 866

Pattern functor

sealed trait Tree
case class Node(
  left : Tree,
  value: Int,
  right: Tree
) extends Tree
case object Leaf extends Tree
323 / 866

Pattern functor

sealed trait TreeF
case class Node(
  left : Tree,
  value: Int,
  right: Tree
) extends TreeF
case object Leaf extends TreeF
324 / 866

Pattern functor

sealed trait TreeF
case class Node(
  left : Tree,
  value: Int,
  right: Tree
) extends TreeF
case object Leaf extends TreeF
325 / 866

Pattern functor

sealed trait TreeF
case class NodeF(
  left : Tree,
  value: Int,
  right: Tree
) extends TreeF
case object Leaf extends TreeF
326 / 866

Pattern functor

sealed trait TreeF
case class NodeF(
  left : Tree,
  value: Int,
  right: Tree
) extends TreeF
case object Leaf extends TreeF
327 / 866

Pattern functor

sealed trait TreeF
case class NodeF(
  left : Tree,
  value: Int,
  right: Tree
) extends TreeF
case object LeafF extends TreeF
328 / 866

Pattern functor

sealed trait TreeF
case class NodeF(
  left : Tree,
  value: Int,
  right: Tree
) extends TreeF
case object LeafF extends TreeF
329 / 866

Pattern functor

sealed trait TreeF[A]
case class NodeF(
  left : Tree,
  value: Int,
  right: Tree
) extends TreeF
case object LeafF extends TreeF
330 / 866

Pattern functor

sealed trait TreeF[A]
case class NodeF(
  left : Tree,
  value: Int,
  right: Tree
) extends TreeF
case object LeafF extends TreeF
331 / 866

Pattern functor

sealed trait TreeF[A]
case class NodeF[A](
  left : Tree,
  value: Int,
  right: Tree
) extends TreeF[A]
case object LeafF extends TreeF
332 / 866

Pattern functor

sealed trait TreeF[A]
case class NodeF[A](
  left : Tree,
  value: Int,
  right: Tree
) extends TreeF[A]
case object LeafF extends TreeF
333 / 866

Pattern functor

sealed trait TreeF[A]
case class NodeF[A](
  left : A,
  value: Int,
  right: A
) extends TreeF[A]
case object LeafF extends TreeF
334 / 866

Pattern functor

sealed trait TreeF[A]
case class NodeF[A](
  left : A,
  value: Int,
  right: A
) extends TreeF[A]
case object LeafF extends TreeF
335 / 866

Pattern functor

sealed trait TreeF[A]
case class NodeF[A](
  left : A,
  value: Int,
  right: A
) extends TreeF[A]
case object LeafF extends TreeF[???]
336 / 866

Pattern functor

sealed trait TreeF[A]
case class NodeF[A](
  left : A,
  value: Int,
  right: A
) extends TreeF[A]
case object LeafF extends TreeF[Nothing]
337 / 866

Pattern functor

sealed trait TreeF[A]
case class NodeF[A](
  left : A,
  value: Int,
  right: A
) extends TreeF[A]
case object LeafF extends TreeF[Nothing]
338 / 866

Pattern functor

sealed trait TreeF[+A]
case class NodeF[A](
  left : A,
  value: Int,
  right: A
) extends TreeF[A]
case object LeafF extends TreeF[Nothing]
339 / 866

Pattern functor

sealed trait TreeF[+A]
case class NodeF[A](
  left : A,
  value: Int,
  right: A
) extends TreeF[A]
case object LeafF extends TreeF[Nothing]
340 / 866

Pattern functor

Tree catamorphism

341 / 866

Pattern functor

Tree catamorphism

342 / 866

Projection

Tree catamorphism

343 / 866

Projection

def projectTree: Tree => TreeF[Tree] = {
  case Node(l, v, r) => NodeF(l, v, r)
  case Leaf          => LeafF
}
344 / 866

Projection

def projectTree: Tree => TreeF[Tree] = {
  case Node(l, v, r) => NodeF(l, v, r)
  case Leaf          => LeafF
}
345 / 866

Projection

def projectTree: Tree => TreeF[Tree] = {
  case Node(l, v, r) => NodeF(l, v, r)
  case Leaf          => LeafF
}
346 / 866

Projection

def projectTree: Tree => TreeF[Tree] = {
  case Node(l, v, r) => NodeF(l, v, r)
  case Leaf          => LeafF
}
347 / 866

Projection

def projectTree: Tree => TreeF[Tree] = {
  case Node(l, v, r) => NodeF(l, v, r)
  case Leaf          => LeafF
}
348 / 866

Projection

def projectTree: Tree => TreeF[Tree] = {
  case Node(l, v, r) => NodeF(l, v, r)
  case Leaf          => LeafF
}
349 / 866

Projection

Tree catamorphism

350 / 866

Projection

Tree catamorphism

351 / 866

Functor instance

Tree catamorphism

352 / 866

Functor instance

implicit val treeFFunctor = new Functor[TreeF] {
  override def map[A, B](tree: TreeF[A], f: A => B) =
    tree match {
      case NodeF(left, i, right) => NodeF(f(left), i, f(right))
      case LeafF                 => LeafF
    }
}
353 / 866

Functor instance

implicit val treeFFunctor = new Functor[TreeF] {
  override def map[A, B](tree: TreeF[A], f: A => B) =
    tree match {
      case NodeF(left, i, right) => NodeF(f(left), i, f(right))
      case LeafF                 => LeafF
    }
}
354 / 866

Functor instance

implicit val treeFFunctor = new Functor[TreeF] {
  override def map[A, B](tree: TreeF[A], f: A => B) =
    tree match {
      case NodeF(left, i, right) => NodeF(f(left), i, f(right))
      case LeafF                 => LeafF
    }
}
355 / 866

Functor instance

implicit val treeFFunctor = new Functor[TreeF] {
  override def map[A, B](tree: TreeF[A], f: A => B) =
    tree match {
      case NodeF(left, i, right) => NodeF(f(left), i, f(right))
      case LeafF                 => LeafF
    }
}
356 / 866

Functor instance

implicit val treeFFunctor = new Functor[TreeF] {
  override def map[A, B](tree: TreeF[A], f: A => B) =
    tree match {
      case NodeF(left, i, right) => NodeF(f(left), i, f(right))
      case LeafF                 => LeafF
    }
}
357 / 866

Functor instance

implicit val treeFFunctor = new Functor[TreeF] {
  override def map[A, B](tree: TreeF[A], f: A => B) =
    tree match {
      case NodeF(left, i, right) => NodeF(f(left), i, f(right))
      case LeafF                 => LeafF
    }
}
358 / 866

Functor instance

implicit val treeFFunctor = new Functor[TreeF] {
  override def map[A, B](tree: TreeF[A], f: A => B) =
    tree match {
      case NodeF(left, i, right) => NodeF(f(left), i, f(right))
      case LeafF                 => LeafF
    }
}
359 / 866

Functor instance

Tree catamorphism

360 / 866

F-Algebra

Tree catamorphism

361 / 866

F-Algebra

val heightAlgebra: TreeF[Int] => Int = {
  case NodeF(left, _, right) => 1 + math.max(left, right)
  case LeafF                 => 0
}
362 / 866

F-Algebra

val heightAlgebra: TreeF[Int] => Int = {
  case NodeF(left, _, right) => 1 + math.max(left, right)
  case LeafF                 => 0
}
363 / 866

F-Algebra

val heightAlgebra: TreeF[Int] => Int = {
  case NodeF(left, _, right) => 1 + math.max(left, right)
  case LeafF                 => 0
}
364 / 866

F-Algebra

val heightAlgebra: TreeF[Int] => Int = {
  case NodeF(left, _, right) => 1 + math.max(left, right)
  case LeafF                 => 0
}
365 / 866

F-Algebra

val heightAlgebra: TreeF[Int] => Int = {
  case NodeF(left, _, right) => 1 + math.max(left, right)
  case LeafF                 => 0
}
366 / 866

F-Algebra

val heightAlgebra: TreeF[Int] => Int = {
  case NodeF(left, _, right) => 1 + math.max(left, right)
  case LeafF                 => 0
}
367 / 866

F-Algebra

Tree catamorphism

368 / 866

F-Algebra

Tree catamorphism

369 / 866

F-Algebra

Tree catamorphism

370 / 866

Tree height

val height: Tree => Int =
  cata(heightAlgebra, projectTree)
371 / 866

Tree height

val height: Tree => Int =
  cata(heightAlgebra, projectTree)
372 / 866

Tree height

val height: Tree => Int =
  cata(heightAlgebra, projectTree)
height(intTree)
// res20: Int = 3
373 / 866

Tree height

Tree Height

374 / 866

Key takeaways

  • cata works just fine with Tree.
375 / 866

Key takeaways

  • cata works just fine with Tree.

  • it involves a lot of busywork though...

376 / 866

What now?

377 / 866

Reducing the boilerplate

378 / 866

List in terms of ListF

type List2 = ListF[???]
379 / 866

List in terms of ListF

type List2 = ListF[???]
380 / 866

List in terms of ListF

type List2 = ListF[???]
381 / 866

List in terms of ListF

type List2 = ListF[???]
382 / 866

List in terms of ListF

type List2 = ListF[List2]
383 / 866

List in terms of ListF

type List2 = ListF[List2]
//        type List2 = ListF[List2]
//                           ^
// On line 2: error: illegal cyclic reference involving type List2
384 / 866

List in terms of ListF

case class List2(value: ListF[List2])
385 / 866

List in terms of ListF

case class List2(value: ListF[List2])
386 / 866

Building a List2

List2 init

val ints2: List2 =
  ???: List2
387 / 866

Building a List2

List2 init

val ints2: List2 =
  ???: List2
388 / 866

Building a List2

List2

val ints2: List2 =
  List2(???: ListF[List2])
389 / 866

Building a List2

List2

val ints2: List2 =
  List2(???: ListF[List2])
390 / 866

Building a List2

List2

val ints2: List2 =
  List2(Some((3,
    ???: List2
  )))
391 / 866

Building a List2

List2

val ints2: List2 =
  List2(Some((3,
    ???: List2
  )))
392 / 866

Building a List2

List2 step 1

val ints2: List2 =
  List2(Some((3,
    ???: List2
  )))
393 / 866

Building a List2

List2 step 1

val ints2: List2 =
  List2(Some((3,
    List2(???: ListF[List2])
  )))
394 / 866

Building a List2

List2 step 1

val ints2: List2 =
  List2(Some((3,
    List2(???: ListF[List2])
  )))
395 / 866

Building a List2

List2 step 1

val ints2: List2 =
  List2(Some((3,
    List2(Some((2,
      ???: List2
    )))
  )))
396 / 866

Building a List2

List2 step 1

val ints2: List2 =
  List2(Some((3,
    List2(Some((2,
      ???: List2
    )))
  )))
397 / 866

Building a List2

List2 step 1

val ints2: List2 =
  List2(Some((3,
    List2(Some((2,
      ???: List2
    )))
  )))
398 / 866

Building a List2

List2 step 1

val ints2: List2 =
  List2(Some((3,
    List2(Some((2,
      List2(???: ListF[List2])
    )))
  )))
399 / 866

Building a List2

List2 step 1

val ints2: List2 =
  List2(Some((3,
    List2(Some((2,
      List2(???: ListF[List2])
    )))
  )))
400 / 866

Building a List2

List2 step 1

val ints2: List2 =
  List2(Some((3,
    List2(Some((2,
      List2(Some((1,
        ???: List2
      )))
    )))
  )))
401 / 866

Building a List2

List2 step 1

val ints2: List2 =
  List2(Some((3,
    List2(Some((2,
      List2(Some((1,
        ???: List2
      )))
    )))
  )))
402 / 866

Building a List2

List2 step 1

val ints2: List2 =
  List2(Some((3,
    List2(Some((2,
      List2(Some((1,
        ???: List2
      )))
    )))
  )))
403 / 866

Building a List2

List2 step 1

val ints2: List2 =
  List2(Some((3,
    List2(Some((2,
      List2(Some((1,
        List2(???: ListF[List2])
      )))
    )))
  )))
404 / 866

Building a List2

List2 step 1

val ints2: List2 =
  List2(Some((3,
    List2(Some((2,
      List2(Some((1,
        List2(???: ListF[List2])
      )))
    )))
  )))
405 / 866

Building a List2

List2 full

val ints2: List2 =
  List2(Some((3,
    List2(Some((2,
      List2(Some((1,
        List2(None)
      )))
    )))
  )))
406 / 866

Building a List2

List2 full

val ints2: List2 =
  List2(Some((3,
    List2(Some((2,
      List2(Some((1,
        List2(None)
      )))
    )))
  )))
407 / 866

Building a List2

List2 full

val ints2: List2 =
  List2(Some((3,
    List2(Some((2,
      List2(Some((1,
        List2(None)
      )))
    )))
  )))
408 / 866

Building a List2

List2 full

val ints2: List2 =
  List2(Some((3,
    List2(Some((2,
      List2(Some((1,
        List2(None)
      )))
    )))
  )))
409 / 866

Generalising List2

case class Tree2(value: TreeF[Tree2])
410 / 866

Generalising List2

case class Tree2(value: TreeF[Tree2])
411 / 866

Generalising List2

case class Tree2(value: TreeF[Tree2])
412 / 866

Generalising List2

case class Tree2(value: TreeF[Tree2])
413 / 866

Generalising List2

case class List2(value: ListF[List2])
414 / 866

Generalising List2

case class List2(value: ListF[List2])
415 / 866

Generalising List2

case class List2[F[_]](value: ListF[List2])
416 / 866

Generalising List2

case class List2[F[_]](value: ListF[List2])
417 / 866

Generalising List2

case class List2[F[_]](value: F[List2])
418 / 866

Generalising List2

case class List2[F[_]](value: F[List2[???]])
419 / 866

Generalising List2

case class List2[F[_]](value: F[List2[???]])
420 / 866

Generalising List2

case class List2[F[_]](value: F[List2[F]])
421 / 866

Generalising List2

case class List2[F[_]](value: F[List2[F]])
422 / 866

Naming things

case class List2[F[_]](value: F[List2[F]])
423 / 866

Naming things

case class Fix[F[_]](value: F[Fix[F]])
424 / 866

Naming things

case class Fix[F[_]](value: F[Fix[F]])
425 / 866

Naming things

case class Fix[F[_]](value: F[Fix[F]])
f(x)   = x
426 / 866

Naming things

case class Fix[F[_]](value: F[Fix[F]])
f(x)   = x
fix(f) = x
427 / 866

Naming things

case class Fix[F[_]](value: F[Fix[F]])
f(x)   = x
fix(f) = x
fix(f) = x
428 / 866

Naming things

case class Fix[F[_]](value: F[Fix[F]])
f(x)   = x
fix(f) = x
fix(f) = x
429 / 866

Naming things

case class Fix[F[_]](value: F[Fix[F]])
​f(x)   = x
fix(f) = x
fix(f) = x
430 / 866

Naming things

case class Fix[F[_]](value: F[Fix[F]])
f(x)   = x
fix(f) = x
fix(f) = x
431 / 866

Naming things

case class Fix[F[_]](value: F[Fix[F]])
f(x)   = x
fix(f) = x
fix(f) = f(x)
432 / 866

Naming things

case class Fix[F[_]](value: F[Fix[F]])
f(x)   = x
fix(f) = x
fix(f) = f(x)
433 / 866

Naming things

case class Fix[F[_]](value: F[Fix[F]])
f(x)   = x
​fix(f) = x
fix(f) = f(x)
434 / 866

Naming things

case class Fix[F[_]](value: F[Fix[F]])
f(x)   = x
fix(f) = x
fix(f) = f(x)
435 / 866

Naming things

case class Fix[F[_]](value: F[Fix[F]])
f(x)   = x
fix(f) = x
fix(f) = f(fix(f))
436 / 866

Naming things

case class Fix[F[_]](value: F[Fix[F]])
f(x)   = x
fix(f) = x
​fix(f) = f(fix(f))
437 / 866

Naming things

case class Fix[F[_]](value: F[Fix[F]])
f(x)   = x
fix(f) = x
fix(f) = f(fix(f))
438 / 866

Naming things

case class Fix[F[_]](value: F[Fix[F]])
f(x)   = x
fix(f) = x
fix(f) = f(fix(f))
439 / 866

Naming things

case class Fix[F[_]](value: F[Fix[F]])
f(x)   = x
fix(f) = x
fix(f) = f(fix(f))
440 / 866

Naming things

case class Fix[F[_]](value: F[Fix[F]])
f(x)   = x
fix(f) = x
fix(f) = f(fix(f))
441 / 866

List in terms of Fix

type FixedList = Fix[ListF]
442 / 866

List in terms of Fix

type FixedList = Fix[ListF]
443 / 866

List in terms of Fix

type FixedList = Fix[ListF]
444 / 866

List in terms of Fix

val fixedInts: FixedList =
  Fix[ListF](Some((3,
    Fix[ListF](Some((2,
      Fix[ListF](Some((1,
        Fix[ListF](None)
      )))
    )))
  )))
445 / 866

List in terms of Fix

val fixedInts: FixedList =
  Fix[ListF](Some((3,
    Fix[ListF](Some((2,
      Fix[ListF](Some((1,
        Fix[ListF](None)
      )))
    )))
  )))
446 / 866

List in terms of Fix

val fixedInts: FixedList =
  Fix[ListF](Some((3,
    Fix[ListF](Some((2,
      Fix[ListF](Some((1,
        Fix[ListF](None)
      )))
    )))
  )))
447 / 866

Tree in terms of TreeF

type FixedTree = Fix[TreeF]
448 / 866

Tree in terms of TreeF

type FixedTree = Fix[TreeF]
449 / 866

Tree in terms of TreeF

type FixedTree = Fix[TreeF]
450 / 866

Tree in terms of TreeF

val fixedIntTree: FixedTree =
  Fix[TreeF](NodeF(
    Fix[TreeF](NodeF(
      Fix[TreeF](NodeF(Fix[TreeF](LeafF), 1, Fix[TreeF](LeafF))),
      2,
      Fix[TreeF](NodeF(Fix[TreeF](LeafF), 3, Fix[TreeF](LeafF)))
    )),
    4,
    Fix[TreeF](LeafF)
  ))
451 / 866

Tree in terms of TreeF

val fixedIntTree: FixedTree =
  Fix[TreeF](NodeF(
    Fix[TreeF](NodeF(
      Fix[TreeF](NodeF(Fix[TreeF](LeafF), 1, Fix[TreeF](LeafF))),
      2,
      Fix[TreeF](NodeF(Fix[TreeF](LeafF), 3, Fix[TreeF](LeafF)))
    )),
    4,
    Fix[TreeF](LeafF)
  ))
452 / 866

cata with Fix

def cata[F[_]: Functor, A, B](
  algebra: F[A] => A,
  project: B => F[B]
): B => A = {
  def loop(state: B): A =
    algebra(map(project(state), loop))
  loop
}
453 / 866

cata with Fix

def cata[F[_]: Functor, A, B](
  algebra: F[A] => A,
  project: B => F[B]
): B => A = {
  def loop(state: B): A =
    algebra(map(project(state), loop))
  loop
}
454 / 866

cata with Fix

def cataFix[F[_]: Functor, A, B](
  algebra: F[A] => A,
  project: B => F[B]
): B => A = {
  def loop(state: B): A =
    algebra(map(project(state), loop))
  loop
}
455 / 866

cata with Fix

def cataFix[F[_]: Functor, A, B](
  algebra: F[A] => A,
  project: B => F[B]
): B => A = {
  def loop(state: B): A =
    algebra(map(project(state), loop))
  loop
}
456 / 866

cata with Fix

Linked List

457 / 866

cata with Fix

Linked List

458 / 866

cata with Fix

def cataFix[F[_]: Functor, A, B](
  algebra: F[A] => A,
  project: B => F[B]
): B => A = {
  def loop(state: B): A =
    algebra(map(project(state), loop))
  loop
}
459 / 866

cata with Fix

def cataFix[F[_]: Functor, A](
  algebra: F[A] => A,
  project: Fix[F] => F[Fix[F]]
): Fix[F] => A = {
  def loop(state: Fix[F]): A =
    algebra(map(project(state), loop))
  loop
}
460 / 866

cata with Fix

def cataFix[F[_]: Functor, A](
  algebra: F[A] => A,
  project: Fix[F] => F[Fix[F]]
): Fix[F] => A = {
  def loop(state: Fix[F]): A =
    algebra(map(project(state), loop))
  loop
}
461 / 866

cata with Fix

Linked List

462 / 866

cata with Fix

Linked List

463 / 866

Projecting Fix

Linked List

464 / 866

Projecting Fix

val project: List => ListF[List] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
465 / 866

Projecting Fix

val project: List => ListF[List] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
466 / 866

Projecting Fix

val projectFix: List => ListF[List] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
467 / 866

Projecting Fix

val projectFix: List => ListF[List] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
468 / 866

Projecting Fix

val projectFix: List => ListF[List] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
469 / 866

Projecting Fix

val projectFix: FixedList => ListF[FixedList] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
470 / 866

Projecting Fix

val projectFix: FixedList => ListF[FixedList] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
471 / 866

Projecting Fix

val projectFix: Fix[ListF] => ListF[Fix[ListF]] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
472 / 866

Projecting Fix

val projectFix: Fix[ListF] => ListF[Fix[ListF]] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
473 / 866

Projecting Fix

val projectFix: Fix[ListF] => ListF[Fix[ListF]] = {
  case Fix(Some((head, tail))) => Some((head, tail))
  case Nil                     => None
}
474 / 866

Projecting Fix

val projectFix: Fix[ListF] => ListF[Fix[ListF]] = {
  case Fix(Some((head, tail))) => Some((head, tail))
  case Nil                     => None
}
475 / 866

Projecting Fix

val projectFix: Fix[ListF] => ListF[Fix[ListF]] = {
  case Fix(Some((head, tail))) => Some((head, tail))
  case Fix(None)               => None
}
476 / 866

Projecting Fix

val projectFix: Fix[ListF] => ListF[Fix[ListF]] = {
  case Fix(Some((head, tail))) => Some((head, tail))
  case Fix(None)               => None
}
477 / 866

Projecting Fix

val projectFix: Fix[ListF] => ListF[Fix[ListF]] = {
  case Fix(Some((head, tail))) => Some((head, tail))
  case Fix(None)               => None
}
478 / 866

Projecting Fix

val projectFix: Fix[ListF] => ListF[Fix[ListF]] = {
  case Fix(Some((head, tail))) => Some((head, tail))
  case Fix(None)               => None
}
479 / 866

Projecting Fix

val projectFix: Fix[ListF] => ListF[Fix[ListF]] = {
  case Fix(Some((head, tail))) => Some((head, tail))
  case Fix(None)               => None
}
480 / 866

Projecting Fix

val projectFix: Fix[ListF] => ListF[Fix[ListF]] =
  _.value
481 / 866

Projecting Fix

val projectFix: Fix[ListF] => ListF[Fix[ListF]] =
  _.value
482 / 866

Projecting Fix

val projectFix: Fix[ListF] => ListF[Fix[ListF]] =
  _.value
483 / 866

Projecting Fix

​val projectFix: Fix[ListF] => ListF[Fix[ListF]] =
  _.value
484 / 866

Projecting Fix

​def projectFix: Fix[ListF] => ListF[Fix[ListF]] =
  _.value
485 / 866

Projecting Fix

​def projectFix[F[_]]: Fix[ListF] => ListF[Fix[ListF]] =
  _.value
486 / 866

Projecting Fix

def projectFix[F[_]]: Fix[ListF] => ListF[Fix[ListF]] =
  _.value
487 / 866

Projecting Fix

def projectFix[F[_]]: Fix[F] => F[Fix[F]] =
  _.value
488 / 866

Projecting Fix

def projectFix[F[_]]: Fix[F] => F[Fix[F]] =
  _.value
489 / 866

Projecting Fix

def cataFix[F[_]: Functor, A](
  algebra: F[A] => A,
  project: Fix[F] => F[Fix[F]]
): Fix[F] => A = {
  def loop(state: Fix[F]): A =
    algebra(map(project(state), loop))
  loop
}
490 / 866

Projecting Fix

def cataFix[F[_]: Functor, A](
  algebra: F[A] => A,
  project: Fix[F] => F[Fix[F]]
): Fix[F] => A = {
  def loop(state: Fix[F]): A =
    algebra(map(project(state), loop))
  loop
}
491 / 866

Projecting Fix

def cataFix[F[_]: Functor, A](
  algebra: F[A] => A,
  project: Fix[F] => F[Fix[F]]
): Fix[F] => A = {
  def loop(state: Fix[F]): A =
    algebra(map(state.value, loop))
  loop
}
492 / 866

Projecting Fix

def cataFix[F[_]: Functor, A](
  algebra: F[A] => A,
  project: Fix[F] => F[Fix[F]]
): Fix[F] => A = {
  def loop(state: Fix[F]): A =
    algebra(map(state.value, loop))
  loop
}
493 / 866

Projecting Fix

def cataFix[F[_]: Functor, A](
  algebra: F[A] => A
): Fix[F] => A = {
  def loop(state: Fix[F]): A =
    algebra(map(state.value, loop))
  loop
}
494 / 866

Projecting Fix

Linked List

495 / 866

Projecting Fix

Linked List

496 / 866

Functor instance

Linked List

497 / 866

F-Algebra

Linked List

498 / 866

product in terms of cataFix

val productFix: FixedList => Int =
  cataFix(productAlgebra)
499 / 866

product in terms of cataFix

val productFix: FixedList => Int =
  cataFix(productAlgebra)
500 / 866

product in terms of cataFix

val productFix: FixedList => Int =
  cataFix(productAlgebra)
501 / 866

product in terms of cataFix

val productFix: FixedList => Int =
  cataFix(productAlgebra)
productFix(fixedInts)
// res21: Int = 6
502 / 866

height in terms of cataFix

val heightFix: FixedTree => Int =
  cataFix(heightAlgebra)
503 / 866

height in terms of cataFix

val heightFix: FixedTree => Int =
  cataFix(heightAlgebra)
504 / 866

height in terms of cataFix

val heightFix: FixedTree => Int =
  cataFix(heightAlgebra)
505 / 866

height in terms of cataFix

val heightFix: FixedTree => Int =
  cataFix(heightAlgebra)
heightFix(fixedIntTree)
// res22: Int = 3
506 / 866

Cost of Fix

def headOpt(list: FixedList): Option[Int] = list match {
  case Fix(Some((head, _))) => Some(head)
  case Fix(None)            => None
}
507 / 866

Cost of Fix

def headOpt(list:      List): Option[Int] = list match {
  case Cons(     head, _)   => Some(head)
  case Nil                  => None
}
508 / 866

Cost of Fix

val list: FixedList =
  Fix[ListF](Some((3,
    Fix[ListF](Some((2,
      Fix[ListF](Some((1,
        Fix[ListF](None)
      )))
    )))
  )))
509 / 866

Cost of Fix

val list:      List =
  Cons(            3,
    Cons(            2,
      Cons(            1,
        Nil
      )
    )
  )
510 / 866

Key takeaways

Using Fix makes:

511 / 866

Key takeaways

Using Fix makes:

  • the hard case easier.
512 / 866

Key takeaways

Using Fix makes:

  • the hard case easier.

  • the easy case harder.

513 / 866

Key takeaways

Using Fix makes:

  • the hard case easier.

  • the easy case harder.

  • little sense.

514 / 866

What now?

515 / 866

Generative Recursion

516 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))

Linked List

517 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))

Linked List

518 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))

Linked List

519 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))

Linked List

520 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))

Linked List

521 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))

Linked List

522 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))

Linked List

523 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))

Linked List

524 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))

Linked List

525 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))

Linked List

526 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))

Linked List

527 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))

Linked List

528 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))

Linked List

529 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))

Linked List

530 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))

Linked List

531 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))

Linked List

532 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))

Linked List

533 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))

Linked List

534 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))
// res24: String = 3 :: 2 :: 1 :: nil
535 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))
536 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))
537 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))
538 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))
539 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))
540 / 866

Creating ranges

def range(
  from: Int
): List = {
  if(from > 0) Cons(from, range(from - 1))
  else         Nil
}
mkString(range(3))
541 / 866

Extracting character codes

def charCodes(
  from: String
): List = {
  if(from.nonEmpty)
    Cons(from.head.toInt, charCodes(from.tail))
  else Nil
}
542 / 866

Extracting character codes

def charCodes(
  from: String
): List = {
  if(from.nonEmpty)
    Cons(from.head.toInt, charCodes(from.tail))
  else Nil
}
543 / 866

Extracting character codes

def charCodes(
  from: String
): List = {
  if(from.nonEmpty)
    Cons(from.head.toInt, charCodes(from.tail))
  else Nil
}
544 / 866

Extracting character codes

def charCodes(
  from: String
): List = {
  if(from.nonEmpty)
    Cons(from.head.toInt, charCodes(from.tail))
  else Nil
}
545 / 866

Extracting character codes

def charCodes(
  from: String
): List = {
  if(from.nonEmpty)
    Cons(from.head.toInt, charCodes(from.tail))
  else Nil
}
546 / 866

Extracting character codes

def charCodes(
  from: String
): List = {
  if(from.nonEmpty)
    Cons(from.head.toInt, charCodes(from.tail))
  else Nil
}
547 / 866

Extracting character codes

def charCodes(
  from: String
): List = {
  if(from.nonEmpty)
    Cons(from.head.toInt, charCodes(from.tail))
  else Nil
}
548 / 866

Extracting character codes

def charCodes(
  from: String
): List = {
  if(from.nonEmpty)
    Cons(from.head.toInt, charCodes(from.tail))
  else Nil
}
549 / 866

Extracting character codes

def charCodes(
  from: String
): List = {
  if(from.nonEmpty)
    Cons(from.head.toInt, charCodes(from.tail))
  else Nil
}
550 / 866

Extracting character codes

def charCodes(
  from: String
): List = {
  if(from.nonEmpty)
    Cons(from.head.toInt, charCodes(from.tail))
  else Nil
}
mkString(charCodes("cata"))
// res25: String = 99 :: 97 :: 116 :: 97 :: nil
551 / 866

Key takeaways

Generative recursion is composed of:

552 / 866

Key takeaways

Generative recursion is composed of:

  • a predicate that tells us whether to keep recursing.
553 / 866

Key takeaways

Generative recursion is composed of:

  • a predicate that tells us whether to keep recursing.

  • a way of extracting a value and a new state from a given state.

554 / 866

Key takeaways

Generative recursion is composed of:

  • a predicate that tells us whether to keep recursing.

  • a way of extracting a value and a new state from a given state.

  • some recursive structure around these elements.

555 / 866

Generalised generative recursion

556 / 866

Generalising charCodes

def charCodes(
  from: String
): List = {
  if(from.nonEmpty)
    Cons(from.head.toInt, charCodes(from.tail))
  else Nil
}
557 / 866

Generalising charCodes

def charCodes(
  from: String
): List = {
  if(from.nonEmpty)
    Cons(from.head.toInt, charCodes(from.tail))
  else Nil
}
558 / 866

Generalising charCodes

def recurse(
  from: String
): List = {
  if(from.nonEmpty)
    Cons(from.head.toInt, recurse(from.tail))
  else Nil
}
559 / 866

Generalising charCodes

def recurse(
  from: String
): List = {
  if(from.nonEmpty)
    Cons(from.head.toInt, recurse(from.tail))
  else Nil
}
mkString(recurse("cata"))
// res26: String = 99 :: 97 :: 116 :: 97 :: nil
560 / 866

Generalising charCodes

Linked List

561 / 866

Generalising charCodes

Linked List

562 / 866

Generalising charCodes

Linked List

563 / 866

Generalising charCodes

Linked List

564 / 866

Generalising charCodes

Linked List

565 / 866

Generalising charCodes

Linked List

566 / 866

Generalising charCodes

Linked List

567 / 866

Generalising charCodes

Linked List

568 / 866

Generalising charCodes

Linked List

569 / 866

Generalising charCodes

Linked List

570 / 866

Generalising the predicate

Linked List

571 / 866

Generalising the predicate

def recurse(
  from: String
): List = {
  if(from.nonEmpty)
    Cons(from.head.toInt, recurse(from.tail))
  else Nil
}
572 / 866

Generalising the predicate

def recurse(
  from: String
): List = {
  if(from.nonEmpty)
    Cons(from.head.toInt, recurse(from.tail))
  else Nil
}
def predicate(from: String): Boolean =
  from.nonEmpty
573 / 866

Generalising the predicate

def recurse(
  from: String
): List = {
  if(from.nonEmpty)
    Cons(from.head.toInt, recurse(from.tail))
  else Nil
}
def predicate(from: String): Boolean =
  from.nonEmpty
574 / 866

Generalising the predicate

def recurse(
  from: String
): List = {
  if(predicate(from))
    Cons(from.head.toInt, recurse(from.tail))
  else Nil
}
def predicate(from: String): Boolean =
  from.nonEmpty
575 / 866

Generalising the predicate

def recurse(
  predicate: String => Boolean,
  from     : String
): List = {
  if(predicate(from))
    Cons(from.head.toInt, recurse(from.tail))
  else Nil
}
576 / 866

Generalising the predicate

def recurse(
  predicate: String => Boolean,
  from     : String
): List = {
  if(predicate(from))
    Cons(from.head.toInt, recurse(predicate, from.tail))
  else Nil
}
577 / 866

Generalising the predicate

def recurse(
  predicate: String => Boolean,
  from     : String
): List = {
  if(predicate(from))
    Cons(from.head.toInt, recurse(predicate, from.tail))
  else Nil
}
mkString(recurse(predicate, "cata"))
// res27: String = 99 :: 97 :: 116 :: 97 :: nil
578 / 866

Generalising the predicate

Linked List

579 / 866

Generalising the predicate

Linked List

580 / 866

Generalising the update

Linked List

581 / 866

Generalising the update

def recurse(
  predicate: String => Boolean,
  from     : String
): List = {
  if(predicate(from))
    Cons(from.head.toInt, recurse(predicate, from.tail))
  else Nil
}
582 / 866

Generalising the update

def recurse(
  predicate: String => Boolean,
  from     : String
): List = {
  if(predicate(from))
    Cons(from.head.toInt, recurse(predicate, from.tail))
  else Nil
}
def update(from: String): (Int, String) =
  (from.head.toInt, from.tail)
583 / 866

Generalising the update

def recurse(
  predicate: String => Boolean,
  from     : String
): List = {
  if(predicate(from))
    Cons(from.head.toInt, recurse(predicate, from.tail))
  else Nil
}
def update(from: String): (Int, String) =
  (from.head.toInt, from.tail)
584 / 866

Generalising the update

def recurse(
  predicate: String => Boolean,
  from     : String
): List = {
  if(predicate(from)) {
    val (head, nextState) = update(from)
    Cons(head, recurse(predicate, nextState))
  }
  else Nil
}
def update(from: String): (Int, String) =
  (from.head.toInt, from.tail)
585 / 866

Generalising the update

def recurse(
  predicate: String => Boolean,
  from     : String
): List = {
  if(predicate(from)) {
    val (head, nextState) = update(from)
    Cons(head, recurse(predicate, nextState))
  }
  else Nil
}
def update(from: String): (Int, String) =
  (from.head.toInt, from.tail)
586 / 866

Generalising the update

def recurse(
  predicate: String => Boolean,
  from     : String
): List = {
  if(predicate(from)) {
    val (head, nextState) = update(from)
    Cons(head, recurse(predicate, nextState))
  }
  else Nil
}
def update(from: String): (Int, String) =
  (from.head.toInt, from.tail)
587 / 866

Generalising the update

def recurse(
  predicate: String => Boolean,
  from     : String
): List = {
  if(predicate(from)) {
    val (head, nextState) = update(from)
    Cons(head, recurse(predicate, nextState))
  }
  else Nil
}
def update(from: String): (Int, String) =
  (from.head.toInt, from.tail)
588 / 866

Generalising the update

def recurse(
  predicate: String => Boolean,
  from     : String
): List = {
  if(predicate(from)) {
    val (head, nextState) = update(from)
    Cons(head, recurse(predicate, nextState))
  }
  else Nil
}
def update(from: String): (Int, String) =
  (from.head.toInt, from.tail)
589 / 866

Generalising the update

def recurse(
  predicate: String => Boolean,
  update   : String => (Int, String),
  from     : String
): List = {
  if(predicate(from)) {
    val (head, nextState) = update(from)
    Cons(head, recurse(predicate, nextState))
  }
  else Nil
}
590 / 866

Generalising the update

def recurse(
  predicate: String => Boolean,
  update   : String => (Int, String),
  from     : String
): List = {
  if(predicate(from)) {
    val (head, nextState) = update(from)
    Cons(head, recurse(predicate, update, nextState))
  }
  else Nil
}
591 / 866

Generalising the update

def recurse(
  predicate: String => Boolean,
  update   : String => (Int, String),
  from     : String
): List = {
  if(predicate(from)) {
    val (head, nextState) = update(from)
    Cons(head, recurse(predicate, update, nextState))
  }
  else Nil
}
mkString(recurse(predicate, update, "cata"))
// res28: String = 99 :: 97 :: 116 :: 97 :: nil
592 / 866

Generalising the update

Linked List

593 / 866

Generalising the update

Linked List

594 / 866

Generalising the input type

Linked List

595 / 866

Generalising the input type

def recurse(
  predicate: String => Boolean,
  update   : String => (Int, String),
  from     : String
): List = {
  if(predicate(from)) {
    val (head, nextState) = update(from)
    Cons(head, recurse(predicate, update, nextState))
  }
  else Nil
}
596 / 866

Generalising the input type

def recurse[A](
  predicate: String => Boolean,
  update   : String => (Int, String),
  from     : String
): List = {
  if(predicate(from)) {
    val (head, nextState) = update(from)
    Cons(head, recurse(predicate, update, nextState))
  }
  else Nil
}
597 / 866

Generalising the input type

def recurse[A](
  predicate: String => Boolean,
  update   : String => (Int, String),
  from     : String
): List = {
  if(predicate(from)) {
    val (head, nextState) = update(from)
    Cons(head, recurse(predicate, update, nextState))
  }
  else Nil
}
598 / 866

Generalising the input type

def recurse[A](
  predicate: A => Boolean,
  update   : A => (Int, A),
  from     : A
): List = {
  if(predicate(from)) {
    val (head, nextState) = update(from)
    Cons(head, recurse(predicate, update, nextState))
  }
  else Nil
}
599 / 866

Generalising the input type

def recurse[A](
  predicate: A => Boolean,
  update   : A => (Int, A),
  from     : A
): List = {
  if(predicate(from)) {
    val (head, nextState) = update(from)
    Cons(head, recurse(predicate, update, nextState))
  }
  else Nil
}
mkString(recurse(predicate, update, "cata"))
// res29: String = 99 :: 97 :: 116 :: 97 :: nil
600 / 866

Generalising the input type

Linked List

601 / 866

Generalising the input type

Linked List

602 / 866

Generalising the input type

Linked List

603 / 866

Simplifying the step

def recurse[A](
  predicate: A => Boolean,
  update   : A => (Int, A),
  from     : A
): List = {
  if(predicate(from)) {
    val (head, nextState) = update(from)
    Cons(head, recurse(predicate, update, nextState))
  }
  else Nil
}
604 / 866

Simplifying the step

def recurse[A](
  predicate: A => Boolean,
  update   : A => (Int, A),
  from     : A
): List = {
  if(predicate(from)) {
    val (head, nextState) = update(from)
    Cons(head, recurse(predicate, update, nextState))
  }
  else Nil
}
605 / 866

Simplifying the step

def recurse[A](
  predicate: A => Boolean,
  update   : A => (Int, A),
  from     : A
): List = {
  if(predicate(from)) {
    val (head, nextState) = update(from)
    Cons(head, recurse(predicate, update, nextState))
  }
  else Nil
}
606 / 866

Simplifying the step

def recurse[A](
  predicate: A => Boolean,
  update   : A => (Int, A),
  from     : A
): List = {
  if(predicate(from)) {
    val (head, nextState) = update(from)
    Cons(head, recurse(predicate, update, nextState))
  }
  else Nil
}
607 / 866

Simplifying the step

def recurse[A](
  predicate: A => Boolean,
  update   : A => (Int, A),
  from     : A
): List = {
  def loop(state: A): List =
    if(predicate(state)) {
      val (head, nextState) = update(state)
      Cons(head, loop(nextState))
    }
    else Nil
  loop(from)
}
608 / 866

Simplifying the step

def recurse[A](
  predicate: A => Boolean,
  update   : A => (Int, A),
  from     : A
): List = {
  def loop(state: A): List =
    if(predicate(state)) {
      val (head, nextState) = update(state)
      Cons(head, loop(nextState))
    }
    else Nil
  loop(from)
}
609 / 866

Simplifying the step

def recurse[A](
  predicate: A => Boolean,
  update   : A => (Int, A),
  from     : A
): List = {
  def loop(state: A): List =
    if(predicate(state)) {
      val (head, nextState) = update(state)
      Cons(head, loop(nextState))
    }
    else Nil
  loop(from)
}
610 / 866

Simplifying the step

def recurse[A](
  predicate: A => Boolean,
  update   : A => (Int, A),
  from     : A
): List = {
  def loop(state: A): List =
    if(predicate(state)) {
      val (head, nextState) = update(state)
      Cons(head, loop(nextState))
    }
    else Nil
  loop(from)
}
611 / 866

Simplifying the step

def recurse[A](
  predicate: A => Boolean,
  update   : A => (Int, A),
  from     : A
): List = {
  def loop(state: A): List =
    if(predicate(state)) {
      val (head, nextState) = update(state)
      Cons(head, loop(nextState))
    }
    else Nil
  loop(from)
}
612 / 866

Simplifying the step

def recurse[A](
  predicate: A => Boolean,
  update   : A => (Int, A),
  from     : A
): List = {
  def loop(state: A): List =
    if(predicate(state)) {
      val (head, nextState) = update(state)
      Cons(head, loop(nextState))
    }
    else Nil
  loop(from)
}
613 / 866

Simplifying the step

Linked List

614 / 866

Simplifying the step

Linked List

615 / 866

Simplifying the step

Linked List

616 / 866

Dropping parameters

def recurse[A](
  predicate: A => Boolean,
  update   : A => (Int, A),
  from     : A
): List = {
  def loop(state: A): List =
    if(predicate(state)) {
      val (head, nextState) = update(state)
      Cons(head, loop(nextState))
    }
    else Nil
  loop(from)
}
617 / 866

Dropping parameters

def recurse[A](
  predicate: A => Boolean,
  update   : A => (Int, A)
): List = {
  def loop(state: A): List =
    if(predicate(state)) {
      val (head, nextState) = update(state)
      Cons(head, loop(nextState))
    }
    else Nil
  loop
}
618 / 866

Dropping parameters

def recurse[A](
  predicate: A => Boolean,
  update   : A => (Int, A)
): List = {
  def loop(state: A): List =
    if(predicate(state)) {
      val (head, nextState) = update(state)
      Cons(head, loop(nextState))
    }
    else Nil
  loop
}
619 / 866

Dropping parameters

def recurse[A](
  predicate: A => Boolean,
  update   : A => (Int, A)
): A => List = {
  def loop(state: A): List =
    if(predicate(state)) {
      val (head, nextState) = update(state)
      Cons(head, loop(nextState))
    }
    else Nil
  loop
}
620 / 866

Dropping parameters

def recurse[A](
  predicate: A => Boolean,
  update   : A => (Int, A)
): A => List = {
  def loop(state: A): List =
    if(predicate(state)) {
      val (head, nextState) = update(state)
      Cons(head, loop(nextState))
    }
    else Nil
  loop
}
mkString(recurse(predicate, update)("cata"))
// res30: String = 99 :: 97 :: 116 :: 97 :: nil
621 / 866

Naming things

def recurse[A](
  predicate: A => Boolean,
  update   : A => (Int, A)
): A => List = {
  def loop(state: A): List =
    if(predicate(state)) {
      val (head, nextState) = update(state)
      Cons(head, loop(nextState))
    }
    else Nil
  loop
}
622 / 866

Naming things

def unfold[A](
  predicate: A => Boolean,
  update   : A => (Int, A)
): A => List = {
  def loop(state: A): List =
    if(predicate(state)) {
      val (head, nextState) = update(state)
      Cons(head, loop(nextState))
    }
    else Nil
  loop
}
623 / 866

Naming things

def unfold[A](
  predicate: A => Boolean,
  update   : A => (Int, A)
): A => List = {
  def loop(state: A): List =
    if(predicate(state)) {
      val (head, nextState) = update(state)
      Cons(head, loop(nextState))
    }
    else Nil
  loop
}
mkString(unfold(predicate, update)("cata"))
// res31: String = 99 :: 97 :: 116 :: 97 :: nil
624 / 866

range as an unfold

val range: Int => List =
  unfold[Int](
    predicate = state => state > 0,
    update    = state => (state, state - 1)
  )
625 / 866

range as an unfold

val range: Int => List =
  unfold[Int](
    predicate = state => state > 0,
    update    = state => (state, state - 1)
  )
626 / 866

range as an unfold

val range: Int => List =
  unfold[Int](
    predicate = state => state > 0,
    update    = state => (state, state - 1)
  )
627 / 866

range as an unfold

val range: Int => List =
  unfold[Int](
    predicate = state => state > 0,
    update    = state => (state, state - 1)
  )
628 / 866

range as an unfold

val range: Int => List =
  unfold[Int](
    predicate = state => state > 0,
    update    = state => (state, state - 1)
  )
mkString(range(3))
// res32: String = 3 :: 2 :: 1 :: nil
629 / 866

Key takeaways

Generative recursion is generalised by:

630 / 866

Key takeaways

Generative recursion is generalised by:

  • parameterising the predicate.
631 / 866

Key takeaways

Generative recursion is generalised by:

  • parameterising the predicate.

  • parameterising the state update.

632 / 866

Key takeaways

Generative recursion is generalised by:

  • parameterising the predicate.

  • parameterising the state update.

  • ... knowing the structure of your type.

633 / 866

Generalised unfolds

634 / 866

Generalised unfolds

def unfold[A](
  predicate: A => Boolean,
  update   : A => (Int, A)
): A => List = {
  def loop(state: A): List =
    if(predicate(state)) {
      val (head, nextState) = update(state)
      Cons(head, loop(nextState))
    }
    else Nil
  loop
}
635 / 866

Generalised unfolds

Linked List

636 / 866

Simplifying predicate and update

Linked List

637 / 866

Simplifying predicate and update

Linked List

638 / 866

Simplifying predicate and update

def unfold[A](
  predicate: A => Boolean,
  update   : A => (Int, A)
): A => List = {
  def loop(state: A): List =
    if(predicate(state)) {
      val (head, nextState) = update(state)
      Cons(head, loop(nextState))
    }
    else Nil
  loop
}
639 / 866

Simplifying predicate and update

val op: String => Option[(Int, String)] =
  state => {
    if(predicate(state)) Some(update(state))
    else                 None
  }
640 / 866

Simplifying predicate and update

val op: String => Option[(Int, String)] =
  state => {
    if(predicate(state)) Some(update(state))
    else                 None
  }
641 / 866

Simplifying predicate and update

val op: String => Option[(Int, String)] =
  state => {
    if(predicate(state)) Some(update(state))
    else                 None
  }
642 / 866

Simplifying predicate and update

val op: String => Option[(Int, String)] =
  state => {
    if(state.nonEmpty) Some(update(state))
    else               None
  }
643 / 866

Simplifying predicate and update

val op: String => Option[(Int, String)] =
  state => {
    if(state.nonEmpty) Some(update(state))
    else               None
  }
644 / 866

Simplifying predicate and update

val op: String => Option[(Int, String)] =
  state => {
    if(state.nonEmpty) Some(update(state))
    else               None
  }
645 / 866

Simplifying predicate and update

val op: String => Option[(Int, String)] =
  state => {
    if(state.nonEmpty) Some((state.head.toInt, state.tail))
    else               None
  }
646 / 866

Simplifying predicate and update

val op: String => Option[(Int, String)] =
  state => {
    if(state.nonEmpty) Some((state.head.toInt, state.tail))
    else               None
  }
647 / 866

Simplifying predicate and update

val op: String => Option[(Int, String)] =
  state => {
    if(state.nonEmpty) Some((state.head.toInt, state.tail))
    else               None
  }
648 / 866

Simplifying predicate and update

val op: String => ListF[String] =
  state => {
    if(state.nonEmpty) Some((state.head.toInt, state.tail))
    else               None
  }
649 / 866

Simplifying predicate and update

val op: String => ListF[String] =
  state => {
    if(state.nonEmpty) Some((state.head.toInt, state.tail))
    else               None
  }
650 / 866

Simplifying predicate and update

def unfold[A](
  predicate: A => Boolean,
  update   : A => (Int, A)
): A => List = {
  def loop(state: A): List =
    if(predicate(state)) {
      val (head, nextState) = update(state)
      Cons(head, loop(nextState))
    }
    else Nil
  loop
}
651 / 866

Simplifying predicate and update

def unfold[A](
  op: A => ListF[A]
): A => List = {
  def loop(state: A): List =
    if(predicate(state)) {
      val (head, nextState) = update(state)
      Cons(head, loop(nextState))
    }
    else Nil
  loop
}
652 / 866

Simplifying predicate and update

def unfold[A](
  op: A => ListF[A]
): A => List = {
  def loop(state: A): List =
    if(predicate(state)) {
      val (head, nextState) = update(state)
      Cons(head, loop(nextState))
    }
    else Nil
  loop
}
653 / 866

Simplifying predicate and update

def unfold[A](
  op: A => ListF[A]
): A => List = {
  def loop(state: A): List =
    op(state) match {
      case Some((head, nextState)) => Cons(head, loop(nextState))
      case None                    => Nil
    }
  loop
}
654 / 866

Simplifying predicate and update

def unfold[A](
  op: A => ListF[A]
): A => List = {
  def loop(state: A): List =
    op(state) match {
      case Some((head, nextState)) => Cons(head, loop(nextState))
      case None                    => Nil
    }
  loop
}
655 / 866

Simplifying predicate and update

def unfold[A](
  op: A => ListF[A]
): A => List = {
  def loop(state: A): List =
    op(state) match {
      case Some((head, nextState)) => Cons(head, loop(nextState))
      case None                    => Nil
    }
  loop
}
656 / 866

Simplifying predicate and update

def unfold[A](
  op: A => ListF[A]
): A => List = {
  def loop(state: A): List =
    op(state) match {
      case Some((head, nextState)) => Cons(head, loop(nextState))
      case None                    => Nil
    }
  loop
}
657 / 866

Simplifying predicate and update

def unfold[A](
  op: A => ListF[A]
): A => List = {
  def loop(state: A): List =
    op(state) match {
      case Some((head, nextState)) => Cons(head, loop(nextState))
      case None                    => Nil
    }
  loop
}
658 / 866

Simplifying predicate and update

def unfold[A](
  op: A => ListF[A]
): A => List = {
  def loop(state: A): List =
    op(state) match {
      case Some((head, nextState)) => Cons(head, loop(nextState))
      case None                    => Nil
    }
  loop
}
659 / 866

Simplifying predicate and update

def unfold[A](
  op: A => ListF[A]
): A => List = {
  def loop(state: A): List =
    op(state) match {
      case Some((head, nextState)) => Cons(head, loop(nextState))
      case None                    => Nil
    }
  loop
}
mkString(unfold(op)("cata"))
// res33: String = 99 :: 97 :: 116 :: 97 :: nil
660 / 866

Simplifying predicate and update

Linked List

661 / 866

Simplifying predicate and update

Linked List

662 / 866

Abstracting over structure

Linked List

663 / 866

Abstracting over structure

def unfold[A](
  op: A => ListF[A]
): A => List = {
  def loop(state: A): List =
    op(state) match {
      case Some((head, state)) => Cons(head, loop(state))
      case None                => Nil
    }
  loop
}
664 / 866

Abstracting over structure

val embed: Option[(Int, List)] => List = {
  case Some((head, tail)) => Cons(head, tail)
  case None               => Nil
}
665 / 866

Abstracting over structure

val embed: Option[(Int, List)] => List = {
  case Some((head, tail)) => Cons(head, tail)
  case None               => Nil
}
666 / 866

Abstracting over structure

val embed: Option[(Int, List)] => List = {
  case Some((head, tail)) => Cons(head, tail)
  case None               => Nil
}
667 / 866

Abstracting over structure

val embed: Option[(Int, List)] => List = {
  case Some((head, tail)) => Cons(head, tail)
  case None               => Nil
}
668 / 866

Abstracting over structure

val embed: Option[(Int, List)] => List = {
  case Some((head, tail)) => Cons(head, tail)
  case None               => Nil
}
669 / 866

Abstracting over structure

val embed: Option[(Int, List)] => List = {
  case Some((head, tail)) => Cons(head, tail)
  case None               => Nil
}
670 / 866

Abstracting over structure

val embed: Option[(Int, List)] => List = {
  case Some((head, tail)) => Cons(head, tail)
  case None               => Nil
}
671 / 866

Abstracting over structure

val embed: ListF[List] => List = {
  case Some((head, tail)) => Cons(head, tail)
  case None               => Nil
}
672 / 866

Abstracting over structure

val embed: ListF[List] => List = {
  case Some((head, tail)) => Cons(head, tail)
  case None               => Nil
}
673 / 866

Abstracting over structure

def unfold[A](
  op   : A => ListF[A]
): A => List = {
  def loop(state: A): List =
    op(state) match {
      case Some((head, state)) => Cons(head, loop(state))
      case None                => Nil
    }
  loop
}
674 / 866

Abstracting over structure

def unfold[A](
  op   : A => ListF[A],
  embed: ListF[List] => List
): A => List = {
  def loop(state: A): List =
    op(state) match {
      case Some((head, state)) => Cons(head, loop(state))
      case None                => Nil
    }
  loop
}
675 / 866

Abstracting over structure

def unfold[A](
  op   : A => ListF[A],
  embed: ListF[List] => List
): A => List = {
  def loop(state: A): List =
    op(state) match {
      case Some((head, state)) => Cons(head, loop(state))
      case None                => Nil
    }
  loop
}
676 / 866

Abstracting over structure

def unfold[A](
  op   : A => ListF[A],
  embed: ListF[List] => List
): A => List = {
  def loop(state: A): List =
    op(state) match {
      case Some((head, state)) => embed(Some((head, loop(state))))
      case None                => Nil
    }
  loop
}
677 / 866

Abstracting over structure

def unfold[A](
  op   : A => ListF[A],
  embed: ListF[List] => List
): A => List = {
  def loop(state: A): List =
    op(state) match {
      case Some((head, state)) => embed(Some((head, loop(state))))
      case None                => Nil
    }
  loop
}
678 / 866

Abstracting over structure

def unfold[A](
  op   : A => ListF[A],
  embed: ListF[List] => List
): A => List = {
  def loop(state: A): List =
    op(state) match {
      case Some((head, state)) => embed(Some((head, loop(state))))
      case None                => embed(None)
    }
  loop
}
679 / 866

Abstracting over structure

def unfold[A](
  op   : A => ListF[A],
  embed: ListF[List] => List
): A => List = {
  def loop(state: A): List =
    op(state) match {
      case Some((head, state)) => embed(Some((head, loop(state))))
      case None                => embed(None)
    }
  loop
}
680 / 866

Abstracting over structure

def unfold[A](
  op   : A => ListF[A],
  embed: ListF[List] => List
): A => List = {
  def loop(state: A): List =
    op(state) match {
      case Some((head, state)) => embed(Some((head, loop(state))))
      case None                => embed(None)
    }
  loop
}
681 / 866

Abstracting over structure

def unfold[A](
  op   : A => ListF[A],
  embed: ListF[List] => List
): A => List = {
  def loop(state: A): List =
    embed(op(state) match {
      case Some((head, state)) => Some((head, loop(state)))
      case None                => None
    })
  loop
}
682 / 866

Abstracting over structure

def unfold[A](
  op   : A => ListF[A],
  embed: ListF[List] => List
): A => List = {
  def loop(state: A): List =
    embed(op(state) match {
      case Some((head, state)) => Some((head, loop(state)))
      case None                => None
    })
  loop
}
mkString(unfold(op, embed)("cata"))
// res34: String = 99 :: 97 :: 116 :: 97 :: nil
683 / 866

Abstracting over structure

Linked List

684 / 866

Abstracting over structure

Linked List

685 / 866

Using Functor

Linked List

686 / 866

Using Functor

Linked List

687 / 866

Using Functor

def unfold[A](
  op   : A => ListF[A],
  embed: ListF[List] => List
): A => List = {
  def loop(state: A): List =
    embed(op(state) match {
      case Some((head, state)) => Some((head, loop(state)))
      case None                => None
    })
  loop
}
688 / 866

Using Functor

def unfold[A](
  op   : A => ListF[A],
  embed: ListF[List] => List
): A => List = {
  def loop(state: A): List =
    embed(op(state) match {
      case Some((head, state)) => Some((head, loop(state)))
      case None                => None
    })
  loop
}
689 / 866

Using Functor

def unfold[A](
  op   : A => ListF[A],
  embed: ListF[List] => List
): A => List = {
  def loop(state: A): List =
    embed(op(state) match {
      case Some((head, state)) => Some((head, loop(state)))
      case None                => None
    })
  loop
}
690 / 866

Using Functor

def unfold[A](
  op   : A => ListF[A],
  embed: ListF[List] => List
): A => List = {
  def loop(state: A): List =
    embed(op(state) match {
      case Some((head, state)) => Some((head, loop(state)))
      case None                => None
    })
  loop
}
691 / 866

Using Functor

def unfold[A](
  op   : A => ListF[A],
  embed: ListF[List] => List
): A => List = {
  def loop(state: A): List =
    embed(op(state) match {
      case Some((head, state)) => Some((head, loop(state)))
      case None                => None
    })
  loop
}
692 / 866

Using Functor

def unfold[A](
  op   : A => ListF[A],
  embed: ListF[List] => List
): A => List = {
  def loop(state: A): List =
    embed(op(state) match {
      case Some((head, state)) => Some((head, loop(state)))
      case None                => None
    })
  loop
}
693 / 866

Using Functor

def unfold[A](
  op   : A => ListF[A],
  embed: ListF[List] => List
): A => List = {
  def loop(state: A): List =
    embed(map(op(state), loop))
  loop
}
694 / 866

Using Functor

def unfold[A](
  op   : A => ListF[A],
  embed: ListF[List] => List
): A => List = {
  def loop(state: A): List =
    embed(map(op(state), loop))
  loop
}
mkString(unfold(op, embed)("cata"))
// res35: String = 99 :: 97 :: 116 :: 97 :: nil
695 / 866

Using Functor

Linked List

696 / 866

Using Functor

Linked List

697 / 866

Abstracting over ListF

Linked List

698 / 866

Abstracting over ListF

def unfold[A](
  op   : A => ListF[A],
  embed: ListF[List] => List
): A => List = {
  def loop(state: A): List =
    embed(map(op(state), loop))
  loop
}
699 / 866

Abstracting over ListF

def unfold[A](
  op   : A => ListF[A],
  embed: ListF[List] => List
): A => List = {
  def loop(state: A): List =
    embed(map(op(state), loop))
  loop
}
700 / 866

Abstracting over ListF

def unfold[F[_]: Functor, A](
  op   : A => ListF[A],
  embed: ListF[List] => List
): A => List = {
  def loop(state: A): List =
    embed(map(op(state), loop))
  loop
}
701 / 866

Abstracting over ListF

def unfold[F[_]: Functor, A](
  op   : A => ListF[A],
  embed: ListF[List] => List
): A => List = {
  def loop(state: A): List =
    embed(map(op(state), loop))
  loop
}
702 / 866

Abstracting over ListF

def unfold[F[_]: Functor, A](
  op   : A => F[A],
  embed: F[List] => List
): A => List = {
  def loop(state: A): List =
    embed(map(op(state), loop))
  loop
}
703 / 866

Abstracting over ListF

def unfold[F[_]: Functor, A](
  op   : A => F[A],
  embed: F[List] => List
): A => List = {
  def loop(state: A): List =
    embed(map(op(state), loop))
  loop
}
mkString(unfold(op, embed).apply("cata"))
// res36: String = 99 :: 97 :: 116 :: 97 :: nil
704 / 866

Abstracting over ListF

Linked List

705 / 866

Abstracting over ListF

Linked List

706 / 866

Abstracting over List

Linked List

707 / 866

Abstracting over List

def unfold[F[_]: Functor, A](
  op   : A => F[A],
  embed: F[List] => List
): A => List = {
  def loop(state: A): List =
    embed(map(op(state), loop))
  loop
}
708 / 866

Abstracting over List

def unfold[F[_]: Functor, A, B](
  op   : A => F[A],
  embed: F[List] => List
): A => List = {
  def loop(state: A): List =
    embed(map(op(state), loop))
  loop
}
709 / 866

Abstracting over List

def unfold[F[_]: Functor, A, B](
  op   : A => F[A],
  embed: F[List] => List
): A => List = {
  def loop(state: A): List =
    embed(map(op(state), loop))
  loop
}
710 / 866

Abstracting over List

def unfold[F[_]: Functor, A, B](
  op   : A => F[A],
  embed: F[B] => B
): A => B = {
  def loop(state: A): B =
    embed(map(op(state), loop))
  loop
}
711 / 866

Abstracting over List

def unfold[F[_]: Functor, A, B](
  op   : A => F[A],
  embed: F[B] => B
): A => B = {
  def loop(state: A): B =
    embed(map(op(state), loop))
  loop
}
mkString(unfold(op, embed).apply("cata"))
// res37: String = 99 :: 97 :: 116 :: 97 :: nil
712 / 866

Abstracting over List

Linked List

713 / 866

Abstracting over List

Linked List

714 / 866

Abstracting over List

Linked List

715 / 866

Naming things

def unfold[F[_]: Functor, A, B](
  op   : A => F[A],
  embed: F[B] => B
): A => B = {
  def loop(state: A): B =
    embed(map(op(state), loop))
  loop
}
716 / 866

Naming things

def ana[F[_]: Functor, A, B](
  op   : A => F[A],
  embed: F[B] => B
): A => B = {
  def loop(state: A): B =
    embed(map(op(state), loop))
  loop
}
717 / 866

Naming things

def ana[F[_]: Functor, A, B](
  op   : A => F[A],
  embed: F[B] => B
): A => B = {
  def loop(state: A): B =
    embed(map(op(state), loop))
  loop
}
718 / 866

Naming things

def ana[F[_]: Functor, A, B](
  coAlgebra: A => F[A],
  embed    : F[B] => B
): A => B = {
  def loop(state: A): B =
    embed(map(coAlgebra(state), loop))
  loop
}
719 / 866

Naming things

def ana[F[_]: Functor, A, B](
  coAlgebra: A => F[A],
  embed    : F[B] => B
): A => B = {
  def loop(state: A): B =
    embed(map(coAlgebra(state), loop))
  loop
}
mkString(ana(op, embed).apply("cata"))
// res38: String = 99 :: 97 :: 116 :: 97 :: nil
720 / 866

Naming things

Linked List

721 / 866

Naming things

Linked List

722 / 866

Naming things

Linked List

723 / 866

range as an ana

val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
val range: Int => List =
  ana(rangeCoAlgebra, embed)
724 / 866

range as an ana

val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
val range: Int => List =
  ana(rangeCoAlgebra, embed)
725 / 866

range as an ana

val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
val range: Int => List =
  ana(rangeCoAlgebra, embed)
726 / 866

range as an ana

val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
val range: Int => List =
  ana(rangeCoAlgebra, embed)
727 / 866

range as an ana

val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
val range: Int => List =
  ana(rangeCoAlgebra, embed)
728 / 866

range as an ana

val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
val range: Int => List =
  ana(rangeCoAlgebra, embed)
729 / 866

range as an ana

val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
val range: Int => List =
  ana(rangeCoAlgebra, embed)
mkString(range(3))
// res39: String = 3 :: 2 :: 1 :: nil
730 / 866

Key takeaways

Anamorphisms are:

731 / 866

Key takeaways

Anamorphisms are:

  • generative recursion for types that can be embedded from a pattern functor.
732 / 866

Key takeaways

Anamorphisms are:

  • generative recursion for types that can be embedded from a pattern functor.

  • fare less complicated than their names make them out to be.

733 / 866

Key takeaways

Anamorphisms are:

  • generative recursion for types that can be embedded from a pattern functor.

  • fare less complicated than their names make them out to be.

  • suspiciously similar to catamorphisms...

734 / 866

Generalised generalised folds!

735 / 866

cata and ana

Cata VS Ana

736 / 866

cata and ana

Cata VS Ana

737 / 866

cata and ana

Cata VS Ana

738 / 866

Duality of cata and ana

Linked List

739 / 866

Duality of cata and ana

Linked List

740 / 866

Duality of cata and ana

Linked List

741 / 866

Duality of cata and ana

Linked List

742 / 866

Duality of cata and ana

Linked List

743 / 866

Composing cata and ana

Linked List

744 / 866

Composing cata and ana

Linked List

745 / 866

Composing cata and ana

Linked List

746 / 866

Composing cata and ana

val factorial: Int => Int =
  range andThen product
747 / 866

Composing cata and ana

val factorial: Int => Int =
  range andThen product
748 / 866

Composing cata and ana

val factorial: Int => Int =
  range andThen product
749 / 866

Composing cata and ana

val factorial: Int => Int =
  range andThen product
750 / 866

Composing cata and ana

val factorial: Int => Int =
  range andThen product
factorial(3)
// res40: Int = 6
751 / 866

Composing cata and ana

val showRange: Int => String =
  range andThen mkString
752 / 866

Composing cata and ana

val showRange: Int => String =
  range andThen mkString
753 / 866

Composing cata and ana

val showRange: Int => String =
  range andThen mkString
754 / 866

Composing cata and ana

val showRange: Int => String =
  range andThen mkString
755 / 866

Composing cata and ana

val showRange: Int => String =
  range andThen mkString
showRange(3)
// res41: String = 3 :: 2 :: 1 :: nil
756 / 866

Simplifying ana andThen cata

Linked List

757 / 866

Simplifying ana andThen cata

Linked List

758 / 866

Simplifying ana andThen cata

Linked List

759 / 866

Simplifying ana andThen cata

Linked List

760 / 866

Simplifying ana andThen cata

Linked List

761 / 866

Simplifying ana andThen cata

Linked List

762 / 866

Simplifying ana andThen cata

Linked List

763 / 866

Simplifying ana andThen cata

Linked List

764 / 866

Simplifying ana andThen cata

Linked List

765 / 866

Simplifying ana andThen cata

Linked List

766 / 866

Simplifying ana andThen cata

Linked List

767 / 866

Simplifying ana andThen cata

Linked List

768 / 866

Simplifying ana andThen cata

Linked List

769 / 866

Simplifying ana andThen cata

Linked List

770 / 866

Simplifying ana andThen cata

Linked List

771 / 866

Simplifying ana andThen cata

3
772 / 866

Simplifying ana andThen cata

Linked List

773 / 866

Simplifying ana andThen cata

3                                    // rangeCoAlgebra
val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
774 / 866

Simplifying ana andThen cata

​3                                    // rangeCoAlgebra
val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
775 / 866

Simplifying ana andThen cata

​Some((3, 2))                         // rangeCoAlgebra
val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
776 / 866

Simplifying ana andThen cata

Some((3, 2))                         // rangeCoAlgebra
val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
777 / 866

Simplifying ana andThen cata

Some((3, 2))                         // rangeCoAlgebra
val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
778 / 866

Simplifying ana andThen cata

Some((3, 2))                         // rangeCoAlgebra
val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
779 / 866

Simplifying ana andThen cata

Some((3, Some((2, 1)))               // rangeCoAlgebra
val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
780 / 866

Simplifying ana andThen cata

Some((3, Some((2, 1)))               // rangeCoAlgebra
val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
781 / 866

Simplifying ana andThen cata

Some((3, Some((2, 1)))               // rangeCoAlgebra
val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
782 / 866

Simplifying ana andThen cata

Some((3, Some((2, 1)))               // rangeCoAlgebra
val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
783 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, 0)))))    // rangeCoAlgebra
val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
784 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, 0)))))    // rangeCoAlgebra
val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
785 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, 0)))))    // rangeCoAlgebra
val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
786 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, 0)))))    // rangeCoAlgebra
val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
787 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
788 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
val rangeCoAlgebra: Int => ListF[Int] = i => {
  if(i > 0) Some((i, i - 1))
  else      None
}
789 / 866

Simplifying ana andThen cata

Linked List

790 / 866

Simplifying ana andThen cata

Linked List

791 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
​                                     // embed
val embed: ListF[List] => List = {
  case Some((head, tail)) => Cons(head, tail)
  case None               => Nil
}
792 / 866

Simplifying ana andThen cata

​Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
​                                     // embed
val embed: ListF[List] => List = {
  case Some((head, tail)) => Cons(head, tail)
  case None               => Nil
}
793 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
​Cons(    Cons(    Cons(        )))   // embed
val embed: ListF[List] => List = {
  case Some((head, tail)) => Cons(head, tail)
  case None               => Nil
}
794 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons(    Cons(    Cons(        )))   // embed
val embed: ListF[List] => List = {
  case Some((head, tail)) => Cons(head, tail)
  case None               => Nil
}
795 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons(    Cons(    Cons(    Nil )))   // embed
val embed: ListF[List] => List = {
  case Some((head, tail)) => Cons(head, tail)
  case None               => Nil
}
796 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons(    Cons(    Cons(    Nil )))   // embed
val embed: ListF[List] => List = {
  case Some((head, tail)) => Cons(head, tail)
  case None               => Nil
}
797 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons( 3, Cons( 2, Cons( 1, Nil )))   // embed
val embed: ListF[List] => List = {
  case Some((head, tail)) => Cons(head, tail)
  case None               => Nil
}
798 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons( 3, Cons( 2, Cons( 1, Nil )))   // embed
val embed: ListF[List] => List = {
  case Some((head, tail)) => Cons(head, tail)
  case None               => Nil
}
799 / 866

Simplifying ana andThen cata

Linked List

800 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons( 3, Cons( 2, Cons( 1, Nil )))   // embed
                                     // project
val project: List => ListF[List] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
801 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
​Cons( 3, Cons( 2, Cons( 1, Nil )))   // embed
                                     // project
val project: List => ListF[List] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
802 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons( 3, Cons( 2, Cons( 1, Nil )))   // embed
​Some((   Some((   Some((       ))))) // project
val project: List => ListF[List] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
803 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons( 3, Cons( 2, Cons( 1, Nil )))   // embed
Some((   Some((   Some((       ))))) // project
val project: List => ListF[List] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
804 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons( 3, Cons( 2, Cons( 1, Nil )))   // embed
Some((   Some((   Some((   None))))) // project
val project: List => ListF[List] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
805 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons( 3, Cons( 2, Cons( 1, Nil )))   // embed
Some((   Some((   Some((   None))))) // project
val project: List => ListF[List] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
806 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons( 3, Cons( 2, Cons( 1, Nil )))   // embed
Some((3, Some((2, Some((1, None))))) // project
val project: List => ListF[List] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
807 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons( 3, Cons( 2, Cons( 1, Nil )))   // embed
Some((3, Some((2, Some((1, None))))) // project
val project: List => ListF[List] = {
  case Cons(head, tail) => Some((head, tail))
  case Nil              => None
}
808 / 866

Simplifying ana andThen cata

Linked List

809 / 866

Simplifying ana andThen cata

Linked List

810 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons( 3, Cons( 2, Cons( 1, Nil )))   // embed
Some((3, Some((2, Some((1, None))))) // project
                                     // mkStringAlgebra
val mkStringAlgebra: ListF[String] => String = {
  case Some((head, tailResult)) => step(head, tailResult)
  case None                     => base
}
811 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons( 3, Cons( 2, Cons( 1, Nil )))   // embed
​Some((3, Some((2, Some((1, None))))) // project
                                     // mkStringAlgebra
val mkStringAlgebra: ListF[String] => String = {
  case Some((head, tailResult)) => step(head, tailResult)
  case None                     => base
}
812 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons( 3, Cons( 2, Cons( 1, Nil )))   // embed
Some((3, Some((2, Some((1, None))))) // project
​step(    step(    step(        )))   // mkStringAlgebra
val mkStringAlgebra: ListF[String] => String = {
  case Some((head, tailResult)) => step(head, tailResult)
  case None                     => base
}
813 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons( 3, Cons( 2, Cons( 1, Nil )))   // embed
Some((3, Some((2, Some((1, None))))) // project
step(    step(    step(        )))   // mkStringAlgebra
val mkStringAlgebra: ListF[String] => String = {
  case Some((head, tailResult)) => step(head, tailResult)
  case None                     => base
}
814 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons( 3, Cons( 2, Cons( 1, Nil )))   // embed
Some((3, Some((2, Some((1, None))))) // project
step(    step(    step(    base)))   // mkStringAlgebra
val mkStringAlgebra: ListF[String] => String = {
  case Some((head, tailResult)) => step(head, tailResult)
  case None                     => base
}
815 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons( 3, Cons( 2, Cons( 1, Nil )))   // embed
Some((3, Some((2, Some((1, None))))) // project
step(    step(    step(    base)))   // mkStringAlgebra
val mkStringAlgebra: ListF[String] => String = {
  case Some((head, tailResult)) => step(head, tailResult)
  case None                     => base
}
816 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons( 3, Cons( 2, Cons( 1, Nil )))   // embed
Some((3, Some((2, Some((1, None))))) // project
step( 3, step( 2, step( 1, base)))   // mkStringAlgebra
val mkStringAlgebra: ListF[String] => String = {
  case Some((head, tailResult)) => step(head, tailResult)
  case None                     => base
}
817 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons( 3, Cons( 2, Cons( 1, Nil )))   // embed
Some((3, Some((2, Some((1, None))))) // project
step( 3, step( 2, step( 1, base)))   // mkStringAlgebra
val mkStringAlgebra: ListF[String] => String = {
  case Some((head, tailResult)) => step(head, tailResult)
  case None                     => base
}
818 / 866

Simplifying ana andThen cata

​Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons( 3, Cons( 2, Cons( 1, Nil )))   // embed
​Some((3, Some((2, Some((1, None))))) // project
step( 3, step( 2, step( 1, base)))   // mkStringAlgebra
819 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
​Cons( 3, Cons( 2, Cons( 1, Nil )))   // embed
​Some((3, Some((2, Some((1, None))))) // project
step( 3, step( 2, step( 1, base)))   // mkStringAlgebra
820 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
Cons( 3, Cons( 2, Cons( 1, Nil )))   // embed
Some((3, Some((2, Some((1, None))))) // project
step( 3, step( 2, step( 1, base)))   // mkStringAlgebra
821 / 866

Simplifying ana andThen cata

Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra
step( 3, step( 2, step( 1, base)))   // mkStringAlgebra
822 / 866

Simplifying ana andThen cata

Linked List

823 / 866

Simplifying ana andThen cata

Linked List

824 / 866

Simplifying ana andThen cata

Linked List

825 / 866

Simplifying ana andThen cata

Linked List

826 / 866

Simplifying ana andThen cata

Linked List

827 / 866

Simplifying ana andThen cata

Linked List

828 / 866

Simplifying ana andThen cata

Linked List

829 / 866

Simplifying ana andThen cata

Linked List

830 / 866

Simplifying ana andThen cata

Linked List

831 / 866

Simplifying ana andThen cata

Linked List

832 / 866

Simplifying ana andThen cata

Linked List

833 / 866

Simplifying ana andThen cata

Linked List

834 / 866

Simplifying ana andThen cata

Linked List

835 / 866

Simplifying ana andThen cata

Linked List

836 / 866

Simplifying ana andThen cata

def ana[F[_]: Functor, A, B](
  coAlgebra: A => F[A],
  embed    : F[B] => B
): A => B = {
  def loop(state: A): B =
    embed(map(coAlgebra(state), loop))
  loop
}
837 / 866

Simplifying ana andThen cata

def ana[F[_]: Functor, A, B](
  coAlgebra: A => F[A],
  embed    : F[B] => B
): A => B = {
  def loop(state: A): B =
    embed(map(coAlgebra(state), loop))
  loop
}
838 / 866

Simplifying ana andThen cata

def ana[F[_]: Functor, A, B](
  coAlgebra: A => F[A],
  algebra  : F[B] => B
): A => B = {
  def loop(state: A): B =
    algebra(map(coAlgebra(state), loop))
  loop
}
839 / 866

Simplifying ana andThen cata

def ana[F[_]: Functor, A, B](
  coAlgebra: A => F[A],
  algebra  : F[B] => B
): A => B = {
  def loop(state: A): B =
    algebra(map(coAlgebra(state), loop))
  loop
}
840 / 866

Simplifying ana andThen cata

def showRange: Int => String =
  ana(rangeCoAlgebra, mkStringAlgebra)
841 / 866

Simplifying ana andThen cata

def showRange: Int => String =
  ana(rangeCoAlgebra, mkStringAlgebra)
842 / 866

Simplifying ana andThen cata

def showRange: Int => String =
  ana(rangeCoAlgebra, mkStringAlgebra)
843 / 866

Simplifying ana andThen cata

def showRange: Int => String =
  ana(rangeCoAlgebra, mkStringAlgebra)
844 / 866

Simplifying ana andThen cata

def showRange: Int => String =
  ana(rangeCoAlgebra, mkStringAlgebra)
845 / 866

Simplifying ana andThen cata

def showRange: Int => String =
  ana(rangeCoAlgebra, mkStringAlgebra)
showRange(3)
// res42: String = 3 :: 2 :: 1 :: nil
846 / 866

Naming things

def ana[F[_]: Functor, A, B](
  coAlgebra: A => F[A],
  algebra  : F[B] => B
): A => B = {
  def loop(state: A): B =
    algebra(map(coAlgebra(state), loop))
  loop
}
847 / 866

Naming things

def hylo[F[_]: Functor, A, B](
  coAlgebra: A => F[A],
  algebra  : F[B] => B
): A => B = {
  def loop(state: A): B =
    algebra(map(coAlgebra(state), loop))
  loop
}
848 / 866

Naming things

def hylo[F[_]: Functor, A, B](
  coAlgebra: A => F[A],
  algebra  : F[B] => B
): A => B = {
  def loop(state: A): B =
    algebra(map(coAlgebra(state), loop))
  loop
}
849 / 866

A magic trick

def hylo[F[_]: Functor, A, B](
  coAlgebra: A => F[A],
  algebra  : F[B] => B
): A => B = {
  def loop(state: A): B =
    algebra(map(coAlgebra(state), loop))
  loop
}
850 / 866

A magic trick

def hylo[F[_]: Functor, A, B](
  coAlgebra: B => F[B],
  algebra  : F[A] => A
): B => A = {
  def loop(state: B): A =
    algebra(map(coAlgebra(state), loop))
  loop
}
851 / 866

A magic trick

def hylo[F[_]: Functor, A, B](
  coAlgebra: B => F[B],
  algebra  : F[A] => A
): B => A = {
  def loop(state: B): A =
    algebra(map(coAlgebra(state), loop))
  loop
}
852 / 866

A magic trick

def hylo[F[_]: Functor, A, B](
  algebra  : F[A] => A,
  coAlgebra: B => F[B]
): B => A = {
  def loop(state: B): A =
    algebra(map(coAlgebra(state), loop))
  loop
}
853 / 866

A magic trick

def hylo[F[_]: Functor, A, B](
  algebra  : F[A] => A,
  coAlgebra: B => F[B]
): B => A = {
  def loop(state: B): A =
    algebra(map(coAlgebra(state), loop))
  loop
}
854 / 866

A magic trick

def hylo[F[_]: Functor, A, B](
  algebra: F[A] => A,
  project: B => F[B]
): B => A = {
  def loop(state: B): A =
    algebra(map(project(state), loop))
  loop
}
855 / 866

A magic trick

def hylo[F[_]: Functor, A, B](
  algebra: F[A] => A,
  project: B => F[B]
): B => A = {
  def loop(state: B): A =
    algebra(map(project(state), loop))
  loop
}
856 / 866

A magic trick

def cata[F[_]: Functor, A, B](
  algebra: F[A] => A,
  project: B => F[B]
): B => A = {
  def loop(state: B): A =
    algebra(map(project(state), loop))
  loop
}
857 / 866

Key takeaways

  • catamorphisms and anamorphisms are duals of each other.
858 / 866

Key takeaways

  • catamorphisms and anamorphisms are duals of each other.

  • they're also the same thing.

859 / 866

Key takeaways

  • catamorphisms and anamorphisms are duals of each other.

  • they're also the same thing.

  • yes, this gives me a headache too.

860 / 866

In closing

861 / 866

If you only remember 1 slide...

862 / 866

If you only remember 1 slide...

  • Recursion schemes are Design Patterns for recursion.
863 / 866

If you only remember 1 slide...

  • Recursion schemes are Design Patterns for recursion.
  • Once you known about pattern functors, the rest is refactoring.
864 / 866

If you only remember 1 slide...

  • Recursion schemes are Design Patterns for recursion.
  • Once you known about pattern functors, the rest is refactoring.
  • You can now study the really wild bits - duality and composition.
865 / 866

Questions?

Nicolas Rinaudo • @NicolasRinaudo • Besedo

866 / 866

Recursive Data Types

2 / 866
Paused

Help

Keyboard shortcuts

↑, ←, Pg Up, k Go to previous slide
↓, →, Pg Dn, Space, j Go to next slide
Home Go to first slide
End Go to last slide
Number + Return Go to specific slide
b / m / f Toggle blackout / mirrored / fullscreen mode
c Clone slideshow
p Toggle presenter mode
t Restart the presentation timer
?, h Toggle this help
Esc Back to slideshow