class: center, middle # An introduction to recursion schemes Nicolas Rinaudo • [@NicolasRinaudo] • [Besedo] --- class: center, middle # Recursive Data Types --- ## Linked list .center[] --- ## Linked list .center[] --- ## Linked list .center[] --- ## Linked list .center[] --- ## Linked list .center[] --- ## Linked list .center[] --- ## Linked list .center[] --- ## Linked list .center[] --- ## Linked list ```scala sealed trait List case class Cons( head: Int, tail: List ) extends List case object Nil extends List ``` --- ## Linked list ```scala *sealed trait List case class Cons( head: Int, tail: List ) extends List case object Nil extends List ``` --- ## Linked list ```scala sealed trait List *case class Cons( * head: Int, * tail: List *) extends List case object Nil extends List ``` --- ## Linked list ```scala sealed trait List case class Cons( head: Int, tail: List ) extends List *case object Nil extends List ``` --- ## Linked list ```scala sealed trait List *case class Cons( * head: Int, * tail: List *) extends List case object Nil extends List ``` --- ## Linked list ```scala sealed trait List case class Cons( `head: Int`, tail: List ) extends List case object Nil extends List ``` --- ## Linked list ```scala sealed trait List case class Cons( head: Int, `tail: List` ) extends List case object Nil extends List ``` --- ## Linked list ```scala val ints: List = Cons(3, Cons(2, Cons(1, Nil))) ``` --- ## Linked list ```scala val ints: List = Cons(`3`, Cons(`2`, Cons(`1`, Nil))) ``` --- class: center, middle # Structural Recursion --- ## Product ```scala def product( values: List ): Int = values match { case Cons(head, tail) => head * product(tail) case Nil => 1 } ``` ```scala product(ints) = ??? ``` .center[] --- ## Product ```scala def product( `values: List` ): Int = values match { case Cons(head, tail) => head * product(tail) case Nil => 1 } ``` ```scala product(ints) = ??? ``` .center[] --- ## Product ```scala def product( values: List ): `Int` = values match { case Cons(head, tail) => head * product(tail) case Nil => 1 } ``` ```scala product(ints) = ??? ``` .center[] --- ## Product ```scala def product( values: List ): Int = values match { case `Cons(head, tail)` => head * product(tail) case Nil => 1 } ``` ```scala product(ints) = ??? ``` .center[] --- ## Product ```scala def product( values: List ): Int = values match { case Cons(head, tail) => `head` * product(tail) case Nil => 1 } ``` ```scala product(ints) = `3` * ??? ``` .center[] --- ## Product ```scala def product( values: List ): Int = values match { case Cons(head, tail) => head `*` product(tail) case Nil => 1 } ``` ```scala product(ints) = 3 `*` ??? ``` .center[] --- ## Product ```scala def product( values: List ): Int = values match { case Cons(head, tail) => head * `product(tail)` case Nil => 1 } ``` ```scala product(ints) = 3 * `???` ``` .center[] --- ## Product ```scala def product( values: List ): Int = values match { case `Cons(head, tail)` => head * product(tail) case Nil => 1 } ``` ```scala product(ints) = 3 * ??? ``` .center[] --- ## Product ```scala def product( values: List ): Int = values match { case Cons(head, tail) => `head` * product(tail) case Nil => 1 } ``` ```scala product(ints) = 3 * `2` * ??? ``` .center[] --- ## Product ```scala def product( values: List ): Int = values match { case Cons(head, tail) => head `*` product(tail) case Nil => 1 } ``` ```scala product(ints) = 3 * 2 `*` ??? ``` .center[] --- ## Product ```scala def product( values: List ): Int = values match { case Cons(head, tail) => head * `product(tail)` case Nil => 1 } ``` ```scala product(ints) = 3 * 2 * `???` ``` .center[] --- ## Product ```scala def product( values: List ): Int = values match { case `Cons(head, tail)` => head * product(tail) case Nil => 1 } ``` ```scala product(ints) = 3 * 2 * ??? ``` .center[] --- ## Product ```scala def product( values: List ): Int = values match { case Cons(head, tail) => `head` * product(tail) case Nil => 1 } ``` ```scala product(ints) = 3 * 2 * `1` * ??? ``` .center[] --- ## Product ```scala def product( values: List ): Int = values match { case Cons(head, tail) => head `*` product(tail) case Nil => 1 } ``` ```scala product(ints) = 3 * 2 * 1 `*` ??? ``` .center[] --- ## Product ```scala def product( values: List ): Int = values match { case Cons(head, tail) => head * `product(tail)` case Nil => 1 } ``` ```scala product(ints) = 3 * 2 * 1 * `???` ``` .center[] --- ## Product ```scala def product( values: List ): Int = values match { case Cons(head, tail) => head * product(tail) case `Nil` => 1 } ``` ```scala product(ints) = 3 * 2 * 1 * ??? ``` .center[] --- ## Product ```scala def product( values: List ): Int = values match { case Cons(head, tail) => head * product(tail) case Nil => `1` } ``` ```scala product(ints) = 3 * 2 * 1 * `1` ``` .center[] --- ## Product ```scala def product( values: List ): Int = values match { case Cons(head, tail) => head * product(tail) case Nil => 1 } ``` ```scala product(ints) = `3 * 2 * 1 * 1` ``` .center[] --- ## Product ```scala def product( values: List ): Int = values match { case Cons(head, tail) => head * product(tail) case Nil => 1 } ``` ```scala product(ints) // res0: Int = 6 ``` --- ## Product ```scala def product( values: List ): Int = values match { case Cons(head, tail) => head * product(tail) `case Nil` => 1 } ``` ```scala product(ints) ``` --- ## Product ```scala def product( values: List ): Int = values match { case Cons(head, tail) => head * product(tail) case Nil => `1` } ``` ```scala product(ints) ``` --- ## Product ```scala def product( values: List ): Int = values match { `case Cons(head, tail)` => head * product(tail) case Nil => 1 } ``` ```scala product(ints) ``` --- ## Product ```scala def product( values: List ): Int = values match { case Cons(head, tail) => `head * product(tail)` case Nil => 1 } ``` ```scala product(ints) ``` --- ## String representation ```scala def mkString( values: List ): String = values match { case Cons(head, tail) => head + " :: " + mkString(tail) case Nil => "nil" } ``` --- ## String representation ```scala def mkString( `values: List` ): String = values match { case Cons(head, tail) => head + " :: " + mkString(tail) case Nil => "nil" } ``` --- ## String representation ```scala def mkString( values: List ): `String` = values match { case Cons(head, tail) => head + " :: " + mkString(tail) case Nil => "nil" } ``` --- ## String representation ```scala def mkString( values: List ): String = values match { case Cons(head, tail) => head + " :: " + mkString(tail) `case Nil` => "nil" } ``` --- ## String representation ```scala def mkString( values: List ): String = values match { case Cons(head, tail) => head + " :: " + mkString(tail) case Nil => `"nil"` } ``` --- ## String representation ```scala def mkString( values: List ): String = values match { `case Cons(head, tail)` => head + " :: " + mkString(tail) case Nil => "nil" } ``` --- ## String representation ```scala def mkString( values: List ): String = values match { case Cons(head, tail) => `head` + " :: " + mkString(tail) case Nil => "nil" } ``` --- ## String representation ```scala def mkString( values: List ): String = values match { case Cons(head, tail) => head + `" :: "` + mkString(tail) case Nil => "nil" } ``` --- ## String representation ```scala def mkString( values: List ): String = values match { case Cons(head, tail) => head + " :: " + `mkString(tail)` case Nil => "nil" } ``` --- ## String representation ```scala def mkString( values: List ): String = values match { case Cons(head, tail) => head + " :: " + mkString(tail) case Nil => "nil" } ``` ```scala mkString(ints) // res1: String = 3 :: 2 :: 1 :: nil ``` --- ## 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. --- class: center, middle # Generalised structural recursion --- ## Generalising `mkString` ```scala def mkString( values: List ): String = values match { case Cons(head, tail) => head + " :: " + mkString(tail) case Nil => "nil" } ``` --- ## Generalising `mkString` .diff-rm[ ```scala *def `mkString`( values: List ): String = values match { * case Cons(head, tail) => head + " :: " + `mkString`(tail) case Nil => "nil" } ``` ] --- ## Generalising `mkString` .diff-add[ ```scala *def `recurse`( values: List ): String = values match { * case Cons(head, tail) => head + " :: " + `recurse`(tail) case Nil => "nil" } ``` ] --- ## Generalising `mkString` ```scala def recurse( values: List ): String = values match { case Cons(head, tail) => head + " :: " + recurse(tail) case Nil => "nil" } ``` ```scala recurse(ints) // res2: String = 3 :: 2 :: 1 :: nil ``` --- ## Generalising `mkString` .center[] --- ## Generalising `mkString` .center[] --- ## Generalising `mkString` .center[] --- ## Generalising `mkString` .center[] --- ## Generalising `mkString` .center[] --- ## Generalising `mkString` .center[] --- ## Generalising `mkString` .center[] --- ## Generalising `mkString` .center[] --- ## Generalising the base case .center[] --- ## Generalising the base case ```scala def recurse( values: List ): String = values match { case Cons(head, tail) => head + " :: " + recurse(tail) case Nil => `"nil"` } ``` --- ## Generalising the base case ```scala def recurse( values: List ): String = values match { case Cons(head, tail) => head + " :: " + recurse(tail) case Nil => "nil" } ``` ```scala ​`val base = "nil"` ``` --- ## Generalising the base case .diff-rm[ ```scala def recurse( values: List ): String = values match { case Cons(head, tail) => head + " :: " + recurse(tail) * case Nil => `"nil"` } ``` ] ```scala val base = "nil" ``` --- ## Generalising the base case .diff-add[ ```scala def recurse( values: List ): String = values match { case Cons(head, tail) => head + " :: " + recurse(tail) * case Nil => `base` } ``` ] ```scala val base = "nil" ``` --- ## Generalising the base case .diff-add[ ```scala def recurse( * `base : String`, values: List ): String = values match { case Cons(head, tail) => head + " :: " + recurse(tail) case Nil => base } ``` ] --- ## Generalising the base case .diff-add[ ```scala def recurse( base : String, values: List ): String = values match { * case Cons(head, tail) => head + " :: " + recurse(`base`, tail) case Nil => base } ``` ] --- ## Generalising the base case ```scala def recurse( base : String, values: List ): String = values match { case Cons(head, tail) => head + " :: " + recurse(base, tail) case Nil => base } ``` ```scala recurse(base, ints) // res3: String = 3 :: 2 :: 1 :: nil ``` --- ## Generalising the base case .center[] --- ## Generalising the base case .center[] --- ## Generalising the step .center[] --- ## Generalising the step ```scala def recurse( base : String, values: List ): String = values match { case Cons(head, tail) => `head + " :: " + recurse(base, tail)` case Nil => base } ``` --- ## Generalising the step ```scala def recurse( base : String, values: List ): String = values match { case Cons(head, tail) => `head` + " :: " + recurse(base, tail) case Nil => base } ``` --- ## Generalising the step ```scala def recurse( base : String, values: List ): String = values match { case Cons(head, tail) => head + " :: " + `recurse(base, tail)` case Nil => base } ``` --- ## Generalising the step ```scala def recurse( base : String, values: List ): String = values match { case Cons(head, tail) => head + " :: " + recurse(base, tail) case Nil => base } ``` ```scala *def step(head: Int, tailResult: String) = * head + " :: " + tailResult ``` --- ## Generalising the step .diff-rm[ ```scala def recurse( base : String, values: List ): String = values match { * case Cons(head, tail) => `head + " :: " + recurse(base, tail)` case Nil => base } ``` ] ```scala def step(head: Int, tailResult: String) = head + " :: " + tailResult ``` --- ## Generalising the step .diff-add[ ```scala def recurse( base : String, values: List ): String = values match { * case Cons(head, tail) => `step(head, recurse(base, tail))` case Nil => base } ``` ] ```scala def step(head: Int, tailResult: String) = head + " :: " + tailResult ``` --- ## Generalising the step .diff-add[ ```scala 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 } ``` ] --- ## Generalising the step .diff-add[ ```scala 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 } ``` ] --- ## Generalising the step ```scala 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 } ``` ```scala recurse(base, step, ints) // res4: String = 3 :: 2 :: 1 :: nil ``` --- ## Generalising the step .center[] --- ## Generalising the step .center[] --- ## Generalising the return type .center[] --- ## Generalising the return type ```scala 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 } ``` --- ## Generalising the return type .diff-add[ ```scala *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 } ``` ] --- ## Generalising the return type .diff-rm[ ```scala 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 } ``` ] --- ## Generalising the return type .diff-add[ ```scala 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 } ``` ] --- ## Generalising the return type ```scala 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 } ``` ```scala recurse(base, step, ints) // res5: String = 3 :: 2 :: 1 :: nil ``` --- ## Generalising the return type .center[] --- ## Generalising the return type .center[] --- ## Generalising the return type .center[] --- ## Simplifying the step ```scala 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 } ``` --- ## Simplifying the step ```scala 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 } ``` --- ## Simplifying the step ```scala 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 } ``` --- ## Simplifying the step ```scala 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 } ``` --- ## Simplifying the step .diff-rm[ ```scala 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` * `}` ``` ] --- ## Simplifying the step .diff-add[ ```scala 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) } ``` ] --- ## Simplifying the step .diff-add[ ```scala 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)` } ``` ] --- ## Simplifying the step ```scala 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) } ``` --- ## Simplifying the step ```scala 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) } ``` --- ## Simplifying the step ```scala 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) } ``` --- ## Simplifying the step ```scala 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) } ``` ```scala recurse(base, step, ints) // res6: String = 3 :: 2 :: 1 :: nil ``` --- ## Simplifying the step .center[] --- ## Simplifying the step .center[] --- ## Simplifying the step .center[] --- ## Dropping parameters .diff-rm[ ```scala 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)` } ``` ] --- ## Dropping parameters .diff-add[ ```scala 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` } ``` ] --- ## Dropping parameters .diff-rm[ ```scala 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 } ``` ] --- ## Dropping parameters .diff-add[ ```scala 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 } ``` ] --- ## Dropping parameters ```scala 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 } ``` ```scala recurse(base, step)(ints) // res7: String = 3 :: 2 :: 1 :: nil ``` --- ## Dropping parameters ```scala def mkString(ints: List): String = recurse(base, step)(ints) ``` --- ## Dropping parameters .diff-rm[ ```scala *def mkString(`ints: List`): String = * recurse(base, step)`(ints)` ``` ] --- ## Dropping parameters .diff-rm[ ```scala *def mkString: `String` = recurse(base, step) ``` ] --- ## Dropping parameters .diff-add[ ```scala *def mkString: `List => String` = recurse(base, step) ``` ] --- ## Dropping parameters .diff-rm[ ```scala *​`def mkString`: List => String = recurse(base, step) ``` ] --- ## Dropping parameters .diff-add[ ```scala *​`val mkString`: List => String = recurse(base, step) ``` ] --- ## Dropping parameters ```scala val mkString: List => String = recurse(base, step) ``` ```scala mkString(ints) // res8: String = 3 :: 2 :: 1 :: nil ``` --- ## Naming things .diff-rm[ ```scala *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 } ``` ] --- ## Naming things .diff-add[ ```scala *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 } ``` ] --- ## Naming things ```scala 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 } ``` ```scala fold(base, step)(ints) // res9: String = 3 :: 2 :: 1 :: nil ``` --- ## `product` as a fold ```scala val product: List => Int = fold[Int]( base = 1, step = (head, tailProduct) => head * tailProduct ) ``` --- ## `product` as a fold ```scala val product: List => Int = `fold`[Int]( base = 1, step = (head, tailProduct) => head * tailProduct ) ``` --- ## `product` as a fold ```scala val product: List => Int = fold[Int]( `base = 1`, step = (head, tailProduct) => head * tailProduct ) ``` --- ## `product` as a fold ```scala val product: List => Int = fold[Int]( base = 1, `step = (head, tailProduct) => head * tailProduct` ) ``` --- ## `product` as a fold ```scala val product: List => Int = fold[Int]( base = 1, step = (head, tailProduct) => head * tailProduct ) ``` ```scala product(ints) // res10: Int = 6 ``` --- ## Key takeaways Structural recursion is generalised by: -- * parameterising the _base case_. -- * parameterising the _step_. -- * ... knowing the structure of your type. --- class: center, middle # Generalised folds --- ## Generalised folds ```scala 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 } ``` --- ## Generalised folds .center[] --- ## Abstracting over structure .center[] --- ## Abstracting over structure ```scala 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 } ``` --- ## List projection ```scala val project: List => Option[(Int, List)] = { case Cons(head, tail) => Some((head, tail)) case Nil => None } ``` --- ## List projection ```scala val `project`: List => Option[(Int, List)] = { case Cons(head, tail) => Some((head, tail)) case Nil => None } ``` --- ## List projection ```scala val project: List => Option[(Int, List)] = { case `Cons(head, tail)` => Some((head, tail)) case Nil => None } ``` --- ## List projection ```scala val project: List => Option[(Int, List)] = { case Cons(head, tail) => `Some((head, tail))` case Nil => None } ``` --- ## List projection ```scala val project: List => Option[(Int, List)] = { case Cons(head, tail) => Some((head, tail)) case `Nil` => None } ``` --- ## List projection ```scala val project: List => Option[(Int, List)] = { case Cons(head, tail) => Some((head, tail)) case Nil => `None` } ``` --- ## Abstracting over structure .diff-rm[ ```scala 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 } ``` ] --- ## Abstracting over structure .diff-add[ ```scala 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 } ``` ] --- ## Abstracting over structure .diff-rm[ ```scala 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 } ``` ] --- ## Abstracting over structure .diff-add[ ```scala 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 } ``` ] --- ## Abstracting over structure .diff-rm[ ```scala 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 } ``` ] --- ## Abstracting over structure .diff-rm[ ```scala 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 } ``` ] --- ## Abstracting over structure ```scala 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 } ``` --- ## Abstracting over structure .diff-add[ ```scala 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 } ``` ] --- ## Abstracting over structure ```scala 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 } ``` ```scala fold(base, step, project)(ints) // res11: String = 3 :: 2 :: 1 :: nil ``` --- ## Abstracting over structure .center[] --- ## Abstracting over structure .center[] --- ## Abstracting over structure .center[] --- ## Simplifying `base` and `step` .center[] --- ## Simplifying `base` and `step` ```scala 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 } ``` --- ## Simplifying `base` and `step` ```scala val op: Option[(Int, String)] => String = { case Some((head, tailResult)) => step(head, tailResult) case None => base } ``` --- ## Simplifying `base` and `step` ```scala val `op`: Option[(Int, String)] => String = { case Some((head, tailResult)) => step(head, tailResult) case None => base } ``` --- ## Simplifying `base` and `step` ```scala val op: Option[(Int, String)] => String = { case `Some((head, tailResult))` => step(head, tailResult) case None => base } ``` --- ## Simplifying `base` and `step` .diff-rm[ ```scala val op: Option[(Int, String)] => String = { * case Some((head, tailResult)) => `step(head, tailResult)` case None => base } ``` ] --- ## Simplifying `base` and `step` .diff-add[ ```scala val op: Option[(Int, String)] => String = { * case Some((head, tailResult)) => `head + " :: " + tailResult` case None => base } ``` ] --- ## Simplifying `base` and `step` ```scala val op: Option[(Int, String)] => String = { case Some((head, tailResult)) => head + " :: " + tailResult case `None` => base } ``` --- ## Simplifying `base` and `step` .diff-rm[ ```scala val op: Option[(Int, String)] => String = { case Some((head, tailResult)) => head + " :: " + tailResult * case None => `base` } ``` ] --- ## Simplifying `base` and `step` .diff-add[ ```scala val op: Option[(Int, String)] => String = { case Some((head, tailResult)) => head + " :: " + tailResult * case None => `"nil"` } ``` ] --- ## Simplifying `base` and `step` ```scala val op: Option[(Int, String)] => String = { case Some((head, tailResult)) => head + " :: " + tailResult case None => "nil" } ``` --- ## Simplifying `base` and `step` .diff-rm[ ```scala 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 } ``` ] --- ## Simplifying `base` and `step` .diff-add[ ```scala 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 } ``` ] --- ## Simplifying `base` and `step` .diff-rm[ ```scala 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 } ``` ] --- ## Simplifying `base` and `step` .diff-add[ ```scala 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 } ``` ] --- ## Simplifying `base` and `step` .diff-rm[ ```scala 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 } ``` ] --- ## Simplifying `base` and `step` .diff-add[ ```scala 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 } ``` ] --- ## Simplifying `base` and `step` ```scala 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 } ``` ```scala fold(op, project)(ints) // res12: String = 3 :: 2 :: 1 :: nil ``` --- ## Simplifying `base` and `step` .center[] --- ## Simplifying `base` and `step` .center[] --- ## Simplifying `base` and `step` .diff-rm[ ```scala 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 } ``` ] --- ## Simplifying `base` and `step` .diff-add[ ```scala 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 } ``` ] --- ## Simplifying `base` and `step` ```scala 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 } ``` ```scala fold(op, project)(ints) // res13: String = 3 :: 2 :: 1 :: nil ``` --- ## Simplifying `base` and `step` .center[] --- ## Simplifying `base` and `step` .center[] --- ## Simplifying `base` and `step` .center[] --- ## Intermediate representation .center[] --- ## Intermediate representation ```scala type ListF[A] = Option[(Int, A)] ``` --- ## Intermediate representation ```scala type `ListF[A]` = Option[(Int, A)] ``` --- ## Intermediate representation ```scala type ListF[A] = `Option[(Int, A)]` ``` --- ## Intermediate representation ```scala type ListF[A] = Option[(Int, A)] ``` ```scala val project: List => ListF[List] = { case Cons(head, tail) => Some((head, tail)) case Nil => None } ``` --- ## Intermediate representation ```scala type ListF[`A`] = Option[(Int, A)] ``` ```scala val project: List => ListF[`List`] = { case Cons(head, tail) => Some((head, tail)) case Nil => None } ``` --- ## Intermediate representation ```scala type ListF[A] = Option[(Int, A)] ``` ```scala val op: ListF[String] => String = { case Some((head, tailResult)) => head + " :: " + tailResult case None => "nil" } ``` --- ## Intermediate representation ```scala type ListF[`A`] = Option[(Int, A)] ``` ```scala val op: ListF[`String`] => String = { case Some((head, tailResult)) => head + " :: " + tailResult case None => "nil" } ``` --- ## Intermediate representation .diff-rm[ ```scala 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 } ``` ] --- ## Intermediate representation .diff-add[ ```scala 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 } ``` ] --- ## Intermediate representation ```scala 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 } ``` ```scala fold(op, project)(ints) // res14: String = 3 :: 2 :: 1 :: nil ``` --- ## Intermediate representation .center[] --- ## Intermediate representation .center[] --- ## Generalising recursion .center[] --- ## Generalising recursion .center[] --- ## Generalising recursion .center[] --- ## Generalising recursion .center[] --- ## Generalising recursion ```scala 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 } ``` --- ## Generalising recursion ```scala 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 } ``` --- ## Generalising recursion ```scala 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 } ``` --- ## Generalising recursion ```scala 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 } ``` --- ## Generalising recursion ```scala 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 } ``` --- ## Generalising recursion .diff-rm[ ```scala 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 } ``` ] --- ## Generalising recursion .diff-add[ ```scala 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 } ``` ] --- ## Generalising recursion .diff-add[ ```scala 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 } ``` ] --- ## Generalising recursion ```scala 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 } ``` --- ## Generalising recursion ```scala 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 } ``` --- ## Generalising recursion ```scala 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 } ``` --- ## Generalising recursion ```scala 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 } ``` --- ## Generalising recursion ```scala 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 } ``` --- ## Generalising recursion ```scala 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 } ``` --- ## Generalising recursion .diff-add[ ```scala 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 } ``` ] --- ## Generalising recursion .diff-rm[ ```scala 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 } ``` ] --- ## Generalising recursion .diff-add[ ```scala 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 } ``` ] --- ## Generalising recursion .diff-add[ ```scala 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 } ``` ] --- ## Generalising recursion ```scala 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 } ``` --- ## Generalising recursion ```scala 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 } ``` --- ## Generalising recursion ```scala 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 } ``` --- ## Generalising recursion ```scala 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 } ``` --- ## Functor ```scala trait Functor[F[_]] { def map[A, B](fa: F[A], f: A => B): F[B] } ``` --- ## Functor ```scala trait `Functor`[F[_]] { def map[A, B](fa: F[A], f: A => B): F[B] } ``` --- ## Functor ```scala trait Functor[`F[_]`] { def map[A, B](fa: F[A], f: A => B): F[B] } ``` --- ## Functor ```scala trait Functor[F[_]] { def `map`[A, B](fa: F[A], f: A => B): F[B] } ``` --- ## Functor ```scala trait Functor[F[_]] { def map[A, B](`fa: F[A]`, f: A => B): F[B] } ``` --- ## Functor ```scala trait Functor[F[_]] { def map[A, B](fa: F[A], `f: A => B`): F[B] } ``` --- ## Functor ```scala trait Functor[F[_]] { def map[A, B](fa: F[A], f: A => B): `F[B]` } ``` --- ## Functor ```scala 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 } } ``` --- ## Functor ```scala 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 } } ``` --- ## Functor ```scala 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 * } } ``` --- ## Functor ```scala 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 } } ``` --- ## Functor ```scala 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 } } ``` --- ## Functor ```scala 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 } } ``` --- ## Functor ```scala 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` } } ``` --- ## Functor ```scala def map[F[_], A, B]( fa : F[A], f : A => B )(implicit functor: Functor[F] ): F[B] = functor.map(fa, f) ``` --- ## Functor ```scala def `map`[F[_], A, B]( fa : F[A], f : A => B )(implicit functor: Functor[F] ): F[B] = functor.map(fa, f) ``` --- ## Functor ```scala def map[F[_], A, B]( `fa : F[A]`, f : A => B )(implicit functor: Functor[F] ): F[B] = functor.map(fa, f) ``` --- ## Functor ```scala def map[F[_], A, B]( fa : F[A], `f : A => B` )(implicit functor: Functor[F] ): F[B] = functor.map(fa, f) ``` --- ## Functor ```scala def map[F[_], A, B]( fa : F[A], f : A => B )(implicit `functor: Functor[F]` ): F[B] = functor.map(fa, f) ``` --- ## Functor ```scala def map[F[_], A, B]( fa : F[A], f : A => B )(implicit functor: Functor[F] ): F[B] = `functor.map(fa, f)` ``` --- ## Using Functor .diff-rm[ ```scala 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 } ``` ] --- ## Using Functor .diff-add[ ```scala 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 } ``` ] --- ## Using Functor .diff-rm[ ```scala 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 } ``` ] --- ## Using Functor .diff-add[ ```scala 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 } ``` ] --- ## Using Functor .diff-rm[ ```scala 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 } ``` ] --- ## Using Functor ```scala def fold[A]( op : ListF[A] => A, project: List => ListF[List] ): List => A = { def loop(state: List): A = op(map(project(state), loop)) loop } ``` --- ## Using Functor ```scala def fold[A]( op : ListF[A] => A, project: List => ListF[List] ): List => A = { def loop(state: List): A = op(map(project(state), loop)) loop } ``` ```scala fold(op, project)(ints) // res15: String = 3 :: 2 :: 1 :: nil ``` --- ## Using Functor .center[] --- ## Using Functor .center[] --- ## Abstracting over `ListF` .center[] --- ## Abstracting over `ListF` ```scala def fold[A]( op : `ListF`[A] => A, project: List => `ListF`[List] ): List => A = { def loop(state: List): A = op(map(project(state), loop)) loop } ``` --- ## Abstracting over `ListF` ```scala def fold[A]( op : ListF[A] => A, project: List => ListF[List] ): List => A = { def loop(state: List): A = op(`map`(project(state), loop)) loop } ``` --- ## Abstracting over `ListF` .diff-add[ ```scala *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 } ``` ] --- ## Abstracting over `ListF` .diff-rm[ ```scala 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 } ``` ] --- ## Abstracting over `ListF` .diff-add[ ```scala 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 } ``` ] --- ## Abstracting over `ListF` ```scala 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 } ``` ```scala fold(op, project).apply(ints) // res16: String = 3 :: 2 :: 1 :: nil ``` --- ## Abstracting over `ListF` .center[] --- ## Abstracting over `ListF` .center[] --- ## Abstracting over `List` .center[] --- ## Abstracting over `List` ```scala 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 } ``` --- ## Abstracting over `List` .diff-add[ ```scala *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 } ``` ] --- ## Abstracting over `List` .diff-rm[ ```scala 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 } ``` ] --- ## Abstracting over `List` .diff-add[ ```scala 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 } ``` ] --- ## Abstracting over `List` ```scala 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 } ``` ```scala fold(op, project).apply(ints) // res17: String = 3 :: 2 :: 1 :: nil ``` --- ## Abstracting over `List` .center[] --- ## Abstracting over `List` .center[] --- ## Abstracting over `List` .center[] --- ## Naming things .diff-rm[ ```scala *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 } ``` ] --- ## Naming things .diff-add[ ```scala *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 } ``` ] --- ## Naming things .diff-rm[ ```scala 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 } ``` ] --- ## Naming things .diff-add[ ```scala 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 } ``` ] --- ## Naming things ```scala 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 } ``` --- ## Naming things ```scala 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 } ``` ```scala cata(op, project).apply(ints) // res18: String = 3 :: 2 :: 1 :: nil ``` --- ## Naming things .center[] --- ## Naming things .center[] --- ## Naming things .center[] --- ## `product` as a cata ```scala val productAlgebra: ListF[Int] => Int = { case Some((head, tailProduct)) => head * tailProduct case None => 1 } val product: List => Int = cata(productAlgebra, project) ``` --- ## `product` as a cata ```scala val `productAlgebra`: ListF[Int] => Int = { case Some((head, tailProduct)) => head * tailProduct case None => 1 } val product: List => Int = cata(productAlgebra, project) ``` --- ## `product` as a cata ```scala val productAlgebra: ListF[Int] => Int = { case `Some((head, tailProduct))` => head * tailProduct case None => 1 } val product: List => Int = cata(productAlgebra, project) ``` --- ## `product` as a cata ```scala val productAlgebra: ListF[Int] => Int = { case Some((head, tailProduct)) => `head * tailProduct` case None => 1 } val product: List => Int = cata(productAlgebra, project) ``` --- ## `product` as a cata ```scala val productAlgebra: ListF[Int] => Int = { case Some((head, tailProduct)) => head * tailProduct case `None` => 1 } val product: List => Int = cata(productAlgebra, project) ``` --- ## `product` as a cata ```scala val productAlgebra: ListF[Int] => Int = { case Some((head, tailProduct)) => head * tailProduct case None => `1` } val product: List => Int = cata(productAlgebra, project) ``` --- ## `product` as a cata ```scala val productAlgebra: ListF[Int] => Int = { case Some((head, tailProduct)) => head * tailProduct case None => 1 } val product: List => Int = `cata(productAlgebra, project)` ``` --- ## `product` as a cata ```scala val productAlgebra: ListF[Int] => Int = { case Some((head, tailProduct)) => head * tailProduct case None => 1 } val product: List => Int = cata(productAlgebra, project) ``` ```scala product(ints) // res19: Int = 6 ``` --- ## 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`. --- class: center, middle # Can this be applied to other types? --- ## Binary Tree .center[] --- ## Binary Tree .center[] --- ## Binary Tree .center[] --- ## Binary Tree .center[] --- ## Binary Tree .center[] --- ## Binary Tree .center[] --- ## Binary Tree .center[] --- ## Binary Tree .center[] --- ## Binary Tree .center[] --- ## Binary Tree ```scala sealed trait Tree case class Node( left : Tree, value: Int, right: Tree ) extends Tree case object Leaf extends Tree ``` --- ## Binary Tree ```scala *sealed trait Tree case class Node( left : Tree, value: Int, right: Tree ) extends Tree case object Leaf extends Tree ``` --- ## Binary Tree ```scala sealed trait Tree *case class Node( * left : Tree, * value: Int, * right: Tree *) extends Tree case object Leaf extends Tree ``` --- ## Binary Tree ```scala sealed trait Tree case class Node( left : Tree, value: Int, right: Tree ) extends Tree *case object Leaf extends Tree ``` --- ## Binary Tree ```scala sealed trait Tree *case class Node( * left : Tree, * value: Int, * right: Tree *) extends Tree case object Leaf extends Tree ``` --- ## Binary Tree ```scala sealed trait Tree case class Node( left : Tree, `value: Int`, right: Tree ) extends Tree case object Leaf extends Tree ``` --- ## Binary Tree ```scala sealed trait Tree case class Node( `left : Tree`, value: Int, right: Tree ) extends Tree case object Leaf extends Tree ``` --- ## Binary Tree ```scala sealed trait Tree case class Node( left : Tree, value: Int, `right: Tree` ) extends Tree case object Leaf extends Tree ``` --- ## Binary Tree ```scala 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) ``` --- ## Binary Tree ```scala val intTree = Node( Node( Node(Leaf, `1`, Leaf), `2`, Node(Leaf, `3`, Leaf) ), `4`, Leaf ) ``` --- ## Tree Height .center[] --- ## Tree Height .center[] --- ## Tree Height .center[] --- ## Tree Height .center[] --- ## Tree Height .center[] --- ## Pattern functor .center[] --- ## Pattern functor ```scala sealed trait Tree case class Node( left : Tree, value: Int, right: Tree ) extends Tree case object Leaf extends Tree ``` --- ## Pattern functor .diff-rm[ ```scala *sealed trait `Tree` case class Node( left : Tree, value: Int, right: Tree *) extends `Tree` *case object Leaf extends `Tree` ``` ] --- ## Pattern functor .diff-add[ ```scala *sealed trait `TreeF` case class Node( left : Tree, value: Int, right: Tree *) extends `TreeF` *case object Leaf extends `TreeF` ``` ] --- ## Pattern functor .diff-rm[ ```scala sealed trait TreeF *case class `Node`( left : Tree, value: Int, right: Tree ) extends TreeF case object Leaf extends TreeF ``` ] --- ## Pattern functor .diff-add[ ```scala sealed trait TreeF *case class `NodeF`( left : Tree, value: Int, right: Tree ) extends TreeF case object Leaf extends TreeF ``` ] --- ## Pattern functor .diff-rm[ ```scala sealed trait TreeF case class NodeF( left : Tree, value: Int, right: Tree ) extends TreeF *case object `Leaf` extends TreeF ``` ] --- ## Pattern functor .diff-add[ ```scala sealed trait TreeF case class NodeF( left : Tree, value: Int, right: Tree ) extends TreeF *case object `LeafF` extends TreeF ``` ] --- ## Pattern functor ```scala sealed trait TreeF case class NodeF( left : Tree, value: Int, right: Tree ) extends TreeF case object LeafF extends TreeF ``` --- ## Pattern functor .diff-add[ ```scala *sealed trait TreeF`[A]` case class NodeF( left : Tree, value: Int, right: Tree ) extends TreeF case object LeafF extends TreeF ``` ] --- ## Pattern functor ```scala sealed trait TreeF[A] *case class NodeF( * left : Tree, * value: Int, * right: Tree *) extends TreeF case object LeafF extends TreeF ``` --- ## Pattern functor .diff-add[ ```scala sealed trait TreeF[A] *case class NodeF`[A]`( left : Tree, value: Int, right: Tree *) extends TreeF`[A]` case object LeafF extends TreeF ``` ] --- ## Pattern functor .diff-rm[ ```scala sealed trait TreeF[A] case class NodeF[A]( * left : `Tree`, value: Int, * right: `Tree` ) extends TreeF[A] case object LeafF extends TreeF ``` ] --- ## Pattern functor .diff-add[ ```scala sealed trait TreeF[A] case class NodeF[A]( * left : `A`, value: Int, * right: `A` ) extends TreeF[A] case object LeafF extends TreeF ``` ] --- ## Pattern functor ```scala sealed trait TreeF[A] case class NodeF[A]( left : A, value: Int, right: A ) extends TreeF[A] *case object LeafF extends TreeF ``` --- ## Pattern functor .diff-rm[ ```scala sealed trait TreeF[A] case class NodeF[A]( left : A, value: Int, right: A ) extends TreeF[A] *case object LeafF extends TreeF`[???]` ``` ] --- ## Pattern functor .diff-add[ ```scala sealed trait TreeF[A] case class NodeF[A]( left : A, value: Int, right: A ) extends TreeF[A] *case object LeafF extends TreeF`[Nothing]` ``` ] --- ## Pattern functor .diff-rm[ ```scala *sealed trait TreeF[`A`] case class NodeF[A]( left : A, value: Int, right: A ) extends TreeF[A] case object LeafF extends TreeF[Nothing] ``` ] --- ## Pattern functor .diff-add[ ```scala *sealed trait TreeF[`+A`] case class NodeF[A]( left : A, value: Int, right: A ) extends TreeF[A] case object LeafF extends TreeF[Nothing] ``` ] --- ## Pattern functor ```scala sealed trait TreeF[+A] case class NodeF[A]( left : A, value: Int, right: A ) extends TreeF[A] case object LeafF extends TreeF[Nothing] ``` --- ## Pattern functor .center[] --- ## Pattern functor .center[] --- ## Projection .center[] --- ## Projection ```scala def projectTree: Tree => TreeF[Tree] = { case Node(l, v, r) => NodeF(l, v, r) case Leaf => LeafF } ``` --- ## Projection ```scala def `projectTree`: Tree => TreeF[Tree] = { case Node(l, v, r) => NodeF(l, v, r) case Leaf => LeafF } ``` --- ## Projection ```scala def projectTree: Tree => TreeF[Tree] = { case `Node(l, v, r)` => NodeF(l, v, r) case Leaf => LeafF } ``` --- ## Projection ```scala def projectTree: Tree => TreeF[Tree] = { case Node(l, v, r) => `NodeF(l, v, r)` case Leaf => LeafF } ``` --- ## Projection ```scala def projectTree: Tree => TreeF[Tree] = { case Node(l, v, r) => NodeF(l, v, r) case `Leaf` => LeafF } ``` --- ## Projection ```scala def projectTree: Tree => TreeF[Tree] = { case Node(l, v, r) => NodeF(l, v, r) case Leaf => `LeafF` } ``` --- ## Projection .center[] --- ## Projection .center[] --- ## Functor instance .center[] --- ## Functor instance ```scala 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 } } ``` --- ## Functor instance ```scala 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 } } ``` --- ## Functor instance ```scala 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 * } } ``` --- ## Functor instance ```scala 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 } } ``` --- ## Functor instance ```scala 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 } } ``` --- ## Functor instance ```scala 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 } } ``` --- ## Functor instance ```scala 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` } } ``` --- ## Functor instance .center[] --- ## F-Algebra .center[] --- ## F-Algebra ```scala val heightAlgebra: TreeF[Int] => Int = { case NodeF(left, _, right) => 1 + math.max(left, right) case LeafF => 0 } ``` --- ## F-Algebra ```scala val `heightAlgebra`: TreeF[Int] => Int = { case NodeF(left, _, right) => 1 + math.max(left, right) case LeafF => 0 } ``` --- ## F-Algebra ```scala val heightAlgebra: TreeF[Int] => Int = { case `NodeF(left, _, right)` => 1 + math.max(left, right) case LeafF => 0 } ``` --- ## F-Algebra ```scala val heightAlgebra: TreeF[Int] => Int = { case NodeF(left, _, right) => `1 + math.max(left, right)` case LeafF => 0 } ``` --- ## F-Algebra ```scala val heightAlgebra: TreeF[Int] => Int = { case NodeF(left, _, right) => 1 + math.max(left, right) case `LeafF` => 0 } ``` --- ## F-Algebra ```scala val heightAlgebra: TreeF[Int] => Int = { case NodeF(left, _, right) => 1 + math.max(left, right) case LeafF => `0` } ``` --- ## F-Algebra .center[] --- ## F-Algebra .center[] --- ## F-Algebra .center[] --- ## Tree height ```scala val height: Tree => Int = cata(heightAlgebra, projectTree) ``` --- ## Tree height ```scala val height: Tree => Int = `cata(heightAlgebra, projectTree)` ``` --- ## Tree height ```scala val height: Tree => Int = cata(heightAlgebra, projectTree) ``` ```scala height(intTree) // res20: Int = 3 ``` --- ## Tree height .center[] --- ## Key takeaways * `cata` works just fine with `Tree`. -- * it involves a lot of busywork though... --- ## What now? * [Conclusion](#closing) * [Reducing the boilerplate](#fix) * [Generative recursion](#unfold) --- class: center, middle name: fix # Reducing the boilerplate --- ## `List` in terms of `ListF` ```scala type List2 = ListF[???] ``` --- ## `List` in terms of `ListF` ```scala type `List2` = ListF[???] ``` --- ## `List` in terms of `ListF` ```scala type List2 = `ListF[???]` ``` --- ## `List` in terms of `ListF` .diff-rm[ ```scala *type List2 = ListF[`???`] ``` ] --- ## `List` in terms of `ListF` .diff-add[ ```scala *type List2 = ListF[`List2`] ``` ] --- ## `List` in terms of `ListF` ```scala type List2 = ListF[List2] // type List2 = ListF[List2] // ^ // On line 2: error: illegal cyclic reference involving type List2 ``` --- ## `List` in terms of `ListF` ```scala case class List2(value: ListF[List2]) ``` --- ## `List` in terms of `ListF` ```scala case class List2(`value: ListF[List2]`) ``` --- ## Building a `List2` .center[] ```scala val ints2: List2 = ???: List2 ``` --- ## Building a `List2` .center[] .diff-rm[ ```scala val ints2: List2 = * `???: List2` ``` ] --- ## Building a `List2` .center[] .diff-add[ ```scala val ints2: List2 = * `List2(???: ListF[List2])` ``` ] --- ## Building a `List2` .center[] .diff-rm[ ```scala val ints2: List2 = * List2(`???: ListF[List2]`) ``` ] --- ## Building a `List2` .center[] .diff-add[ ```scala val ints2: List2 = * List2(`Some((3`, * ???: List2 ))) ``` ] --- ## Building a `List2` .center[] .diff-add[ ```scala val ints2: List2 = * List2(Some((3, * `???: List2` ))) ``` ] --- ## Building a `List2` .center[] .diff-rm[ ```scala val ints2: List2 = List2(Some((3, * `???: List2` ))) ``` ] --- ## Building a `List2` .center[] .diff-add[ ```scala val ints2: List2 = List2(Some((3, * `List2(???: ListF[List2])` ))) ``` ] --- ## Building a `List2` .center[] .diff-rm[ ```scala val ints2: List2 = List2(Some((3, * List2(`???: ListF[List2]`) ))) ``` ] --- ## Building a `List2` .center[] .diff-add[ ```scala val ints2: List2 = List2(Some((3, * List2(`Some((2,` * ???: List2 ))) ))) ``` ] --- ## Building a `List2` .center[] .diff-add[ ```scala val ints2: List2 = List2(Some((3, * List2(Some((2, * `???: List2` ))) ))) ``` ] --- ## Building a `List2` .center[] .diff-rm[ ```scala val ints2: List2 = List2(Some((3, List2(Some((2, * `???: List2` ))) ))) ``` ] --- ## Building a `List2` .center[] .diff-add[ ```scala val ints2: List2 = List2(Some((3, List2(Some((2, * `List2(???: ListF[List2])` ))) ))) ``` ] --- ## Building a `List2` .center[] .diff-rm[ ```scala val ints2: List2 = List2(Some((3, List2(Some((2, * List2(`???: ListF[List2]`) ))) ))) ``` ] --- ## Building a `List2` .center[] .diff-add[ ```scala val ints2: List2 = List2(Some((3, List2(Some((2, * List2(`Some((1,` * ???: List2 ))) ))) ))) ``` ] --- ## Building a `List2` .center[] .diff-add[ ```scala val ints2: List2 = List2(Some((3, List2(Some((2, * List2(Some((1, * `???: List2` ))) ))) ))) ``` ] --- ## Building a `List2` .center[] .diff-rm[ ```scala val ints2: List2 = List2(Some((3, List2(Some((2, List2(Some((1, * `???: List2` ))) ))) ))) ``` ] --- ## Building a `List2` .center[] .diff-add[ ```scala val ints2: List2 = List2(Some((3, List2(Some((2, List2(Some((1, * `List2(???: ListF[List2])` ))) ))) ))) ``` ] --- ## Building a `List2` .center[] .diff-rm[ ```scala val ints2: List2 = List2(Some((3, List2(Some((2, List2(Some((1, * List2(`???: ListF[List2]`) ))) ))) ))) ``` ] --- ## Building a `List2` .center[] .diff-add[ ```scala val ints2: List2 = List2(Some((3, List2(Some((2, List2(Some((1, * List2(`None`) ))) ))) ))) ``` ] --- ## Building a `List2` .center[] ```scala val ints2: List2 = List2(Some((3, List2(Some((2, List2(Some((1, List2(None) ))) ))) ))) ``` --- ## Building a `List2` .center[] ```scala val ints2: List2 = List2(`Some((3`, List2(`Some((2`, List2(`Some((1`, List2(`None`) ))) ))) ))) ``` --- ## Building a `List2` .center[] ```scala val ints2: List2 = `List2(`Some((3, `List2(`Some((2, `List2(`Some((1, `List2(`None) ))) ))) ))) ``` --- ## Generalising `List2` ```scala case class Tree2(value: TreeF[Tree2]) ``` --- ## Generalising `List2` ```scala case class `Tree2`(value: TreeF[Tree2]) ``` --- ## Generalising `List2` ```scala case class Tree2(value: `TreeF`[Tree2]) ``` --- ## Generalising `List2` ```scala case class Tree2(value: TreeF[`Tree2`]) ``` --- ## Generalising `List2` ```scala case class List2(value: ListF[List2]) ``` --- ## Generalising `List2` ```scala case class List2(value: `ListF`[List2]) ``` --- ## Generalising `List2` .diff-add[ ```scala *case class List2[`F[_]`](value: ListF[List2]) ``` ] --- ## Generalising `List2` .diff-rm[ ```scala *case class List2[F[_]](value: `ListF`[List2]) ``` ] --- ## Generalising `List2` .diff-add[ ```scala *case class List2[F[_]](value: `F`[List2]) ``` ] --- ## Generalising `List2` .diff-add[ ```scala *case class List2[F[_]](value: F[List2`[???]`]) ``` ] --- ## Generalising `List2` .diff-rm[ ```scala *case class List2[F[_]](value: F[List2[`???`]]) ``` ] --- ## Generalising `List2` .diff-add[ ```scala *case class List2[F[_]](value: F[List2[`F`]]) ``` ] --- ## Generalising `List2` ```scala case class List2[F[_]](value: F[List2[F]]) ``` --- ## Naming things .diff-rm[ ```scala *case class `List2`[F[_]](value: F[`List2`[F]]) ``` ] --- ## Naming things .diff-add[ ```scala *case class `Fix`[F[_]](value: F[`Fix`[F]]) ``` ] --- ## Naming things ```scala case class Fix[F[_]](value: F[Fix[F]]) ``` --- ## Naming things ```scala case class Fix[F[_]](value: F[Fix[F]]) ``` ```scala f(x) = x ``` --- ## Naming things ```scala case class Fix[F[_]](value: F[Fix[F]]) ``` ```scala f(x) = x fix(f) = x ``` --- ## Naming things ```scala case class Fix[F[_]](value: F[Fix[F]]) ``` ```scala f(x) = x fix(f) = x fix(f) = x ``` --- ## Naming things ```scala case class Fix[F[_]](value: F[Fix[F]]) ``` ```scala f(x) = `x` fix(f) = x fix(f) = `x` ``` --- ## Naming things ```scala case class Fix[F[_]](value: F[Fix[F]]) ``` ```scala ​`f(x)` = x fix(f) = x fix(f) = `x` ``` --- ## Naming things ```scala case class Fix[F[_]](value: F[Fix[F]]) ``` .diff-rm[ ```scala f(x) = x fix(f) = x *fix(f) = `x` ``` ] --- ## Naming things ```scala case class Fix[F[_]](value: F[Fix[F]]) ``` .diff-add[ ```scala f(x) = x fix(f) = x *fix(f) = `f(x)` ``` ] --- ## Naming things ```scala case class Fix[F[_]](value: F[Fix[F]]) ``` ```scala f(x) = x fix(f) = `x` fix(f) = f(`x`) ``` --- ## Naming things ```scala case class Fix[F[_]](value: F[Fix[F]]) ``` ```scala f(x) = x ​`fix(f)` = x fix(f) = f(`x`) ``` --- ## Naming things ```scala case class Fix[F[_]](value: F[Fix[F]]) ``` .diff-rm[ ```scala f(x) = x fix(f) = x *fix(f) = f(`x`) ``` ] --- ## Naming things ```scala case class Fix[F[_]](value: F[Fix[F]]) ``` .diff-add[ ```scala f(x) = x fix(f) = x *fix(f) = f(`fix(f)`) ``` ] --- ## Naming things ```scala case class `Fix`[F[_]](value: F[Fix[F]]) ``` ```scala f(x) = x fix(f) = x ​`fix`(f) = f(fix(f)) ``` --- ## Naming things ```scala case class Fix[`F`[_]](value: F[Fix[F]]) ``` ```scala f(x) = x fix(f) = x fix(`f`) = f(fix(f)) ``` --- ## Naming things ```scala case class Fix[F[_]](value: `F`[Fix[F]]) ``` ```scala f(x) = x fix(f) = x fix(f) = `f`(fix(f)) ``` --- ## Naming things ```scala case class Fix[F[_]](value: F[`Fix`[F]]) ``` ```scala f(x) = x fix(f) = x fix(f) = f(`fix`(f)) ``` --- ## Naming things ```scala case class Fix[F[_]](value: F[Fix[`F`]]) ``` ```scala f(x) = x fix(f) = x fix(f) = f(fix(`f`)) ``` --- ## `List` in terms of `Fix` ```scala type FixedList = Fix[ListF] ``` --- ## `List` in terms of `Fix` ```scala type `FixedList` = Fix[ListF] ``` --- ## `List` in terms of `Fix` ```scala type FixedList = `Fix[ListF]` ``` --- ## `List` in terms of `Fix` ```scala val fixedInts: FixedList = Fix[ListF](Some((3, Fix[ListF](Some((2, Fix[ListF](Some((1, Fix[ListF](None) ))) ))) ))) ``` --- ## `List` in terms of `Fix` ```scala val fixedInts: FixedList = Fix[ListF](Some((`3`, Fix[ListF](Some((`2`, Fix[ListF](Some((`1`, Fix[ListF](None) ))) ))) ))) ``` --- ## `List` in terms of `Fix` ```scala val fixedInts: FixedList = `Fix[ListF](Some((`3`,` `Fix[ListF](Some((`2`,` `Fix[ListF](Some((`1`,` `Fix[ListF](None)` `)))` `)))` `)))` ``` --- ## `Tree` in terms of `TreeF` ```scala type FixedTree = Fix[TreeF] ``` --- ## `Tree` in terms of `TreeF` ```scala type `FixedTree` = Fix[TreeF] ``` --- ## `Tree` in terms of `TreeF` ```scala type FixedTree = `Fix[TreeF]` ``` --- ## `Tree` in terms of `TreeF` ```scala 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) )) ``` --- ## `Tree` in terms of `TreeF` ```scala 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) )) ``` --- ## `cata` with `Fix` ```scala 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` with `Fix` .diff-rm[ ```scala *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` with `Fix` .diff-add[ ```scala *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 } ``` ] --- ## `cata` with `Fix` ```scala 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 } ``` --- ## `cata` with `Fix` .center[] --- ## `cata` with `Fix` .center[] --- .diff-rm[ ## `cata` with `Fix` ```scala *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 } ``` ] --- ## `cata` with `Fix` .diff-add[ ```scala 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 } ``` ] --- ## `cata` with `Fix` ```scala 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 } ``` --- ## `cata` with `Fix` .center[] --- ## `cata` with `Fix` .center[] --- ## Projecting `Fix` .center[] --- ## Projecting `Fix` ```scala val project: List => ListF[List] = { case Cons(head, tail) => Some((head, tail)) case Nil => None } ``` --- ## Projecting `Fix` .diff-rm[ ```scala *val `project`: List => ListF[List] = { case Cons(head, tail) => Some((head, tail)) case Nil => None } ``` ] --- ## Projecting `Fix` .diff-add[ ```scala *val `projectFix`: List => ListF[List] = { case Cons(head, tail) => Some((head, tail)) case Nil => None } ``` ] --- ## Projecting `Fix` ```scala val projectFix: List => ListF[List] = { case Cons(head, tail) => Some((head, tail)) case Nil => None } ``` --- ## Projecting `Fix` .diff-rm[ ```scala *val projectFix: `List` => ListF[`List`] = { case Cons(head, tail) => Some((head, tail)) case Nil => None } ``` ] --- ## Projecting `Fix` .diff-add[ ```scala *val projectFix: `FixedList` => ListF[`FixedList`] = { case Cons(head, tail) => Some((head, tail)) case Nil => None } ``` ] --- ## Projecting `Fix` .diff-rm[ ```scala *val projectFix: `FixedList` => ListF[`FixedList`] = { case Cons(head, tail) => Some((head, tail)) case Nil => None } ``` ] --- ## Projecting `Fix` .diff-add[ ```scala *val projectFix: `Fix[ListF]` => ListF[`Fix[ListF]`] = { case Cons(head, tail) => Some((head, tail)) case Nil => None } ``` ] --- ## Projecting `Fix` .diff-rm[ ```scala val projectFix: Fix[ListF] => ListF[Fix[ListF]] = { * case `Cons(head, tail)` => Some((head, tail)) case Nil => None } ``` ] --- ## Projecting `Fix` .diff-add[ ```scala val projectFix: Fix[ListF] => ListF[Fix[ListF]] = { * case `Fix(Some((head, tail)))` => Some((head, tail)) case Nil => None } ``` ] --- ## Projecting `Fix` .diff-rm[ ```scala val projectFix: Fix[ListF] => ListF[Fix[ListF]] = { case Fix(Some((head, tail))) => Some((head, tail)) * case `Nil` => None } ``` ] --- ## Projecting `Fix` .diff-add[ ```scala val projectFix: Fix[ListF] => ListF[Fix[ListF]] = { case Fix(Some((head, tail))) => Some((head, tail)) * case `Fix(None)` => None } ``` ] --- ## Projecting `Fix` ```scala val projectFix: Fix[ListF] => ListF[Fix[ListF]] = { case Fix(Some((head, tail))) => Some((head, tail)) case Fix(None) => None } ``` --- ## Projecting `Fix` ```scala val projectFix: Fix[ListF] => ListF[Fix[ListF]] = { case Fix(`Some((head, tail))`) => `Some((head, tail))` case Fix(None) => None } ``` --- ## Projecting `Fix` ```scala val projectFix: Fix[ListF] => ListF[Fix[ListF]] = { case Fix(Some((head, tail))) => Some((head, tail)) case Fix(`None`) => `None` } ``` --- ## Projecting `Fix` .diff-rm[ ```scala val projectFix: Fix[ListF] => ListF[Fix[ListF]] = { * `case Fix(Some((head, tail))) => Some((head, tail))` * `case Fix(None) => None` } ``` ] --- ## Projecting `Fix` .diff-add[ ```scala val projectFix: Fix[ListF] => ListF[Fix[ListF]] = * `_.value` ``` ] --- ## Projecting `Fix` ```scala val projectFix: Fix[ListF] => ListF[Fix[ListF]] = _.value ``` --- ## Projecting `Fix` ```scala val projectFix: Fix[`ListF`] => `ListF`[Fix[`ListF`]] = _.value ``` --- ## Projecting `Fix` .diff-rm[ ```scala *​`val projectFix`: Fix[ListF] => ListF[Fix[ListF]] = _.value ``` ] --- ## Projecting `Fix` .diff-add[ ```scala *​`def projectFix`: Fix[ListF] => ListF[Fix[ListF]] = _.value ``` ] --- ## Projecting `Fix` .diff-add[ ```scala *​def projectFix[`F[_]`]: Fix[ListF] => ListF[Fix[ListF]] = _.value ``` ] --- ## Projecting `Fix` .diff-rm[ ```scala *def projectFix[F[_]]: Fix[`ListF`] => `ListF`[Fix[`ListF`]] = _.value ``` ] --- ## Projecting `Fix` .diff-add[ ```scala *def projectFix[F[_]]: Fix[`F`] => `F`[Fix[`F`]] = _.value ``` ] --- ## Projecting `Fix` ```scala def projectFix[F[_]]: Fix[F] => F[Fix[F]] = _.value ``` --- ## Projecting `Fix` ```scala 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 } ``` --- ## Projecting `Fix` .diff-rm[ ```scala 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 } ``` ] --- ## Projecting `Fix` .diff-add[ ```scala 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 } ``` ] --- ## Projecting `Fix` .diff-rm[ ```scala 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 } ``` ] --- ## Projecting `Fix` ```scala def cataFix[F[_]: Functor, A]( algebra: F[A] => A ): Fix[F] => A = { def loop(state: Fix[F]): A = algebra(map(state.value, loop)) loop } ``` --- ## Projecting `Fix` .center[] --- ## Projecting `Fix` .center[] --- ## Functor instance .center[] --- ## F-Algebra .center[] --- ## `product` in terms of `cataFix` ```scala val productFix: FixedList => Int = cataFix(productAlgebra) ``` --- ## `product` in terms of `cataFix` ```scala val productFix: `FixedList => Int` = cataFix(productAlgebra) ``` --- ## `product` in terms of `cataFix` ```scala val productFix: FixedList => Int = `cataFix(productAlgebra)` ``` --- ## `product` in terms of `cataFix` ```scala val productFix: FixedList => Int = cataFix(productAlgebra) ``` ```scala productFix(fixedInts) // res21: Int = 6 ``` --- ## `height` in terms of `cataFix` ```scala val heightFix: FixedTree => Int = cataFix(heightAlgebra) ``` --- ## `height` in terms of `cataFix` ```scala val heightFix: `FixedTree => Int` = cataFix(heightAlgebra) ``` --- ## `height` in terms of `cataFix` ```scala val heightFix: FixedTree => Int = `cataFix(heightAlgebra)` ``` --- ## `height` in terms of `cataFix` ```scala val heightFix: FixedTree => Int = cataFix(heightAlgebra) ``` ```scala heightFix(fixedIntTree) // res22: Int = 3 ``` --- ## Cost of `Fix` ```scala def headOpt(list: FixedList): Option[Int] = list match { case Fix(Some((head, _))) => Some(head) case Fix(None) => None } ``` --- ## Cost of `Fix` ```scala def headOpt(list: List): Option[Int] = list match { case Cons( head, _) => Some(head) case Nil => None } ``` --- ## Cost of `Fix` ```scala val list: FixedList = Fix[ListF](Some((3, Fix[ListF](Some((2, Fix[ListF](Some((1, Fix[ListF](None) ))) ))) ))) ``` --- ## Cost of `Fix` ```scala val list: List = Cons( 3, Cons( 2, Cons( 1, Nil ) ) ) ``` --- ## Key takeaways Using `Fix` makes: -- * the hard case easier. -- * the easy case harder. -- * little sense. --- ## What now? - [Conclusion](#closing) - [Generative recursion](#unfold) --- class: center, middle name: unfold # Generative Recursion --- ## Creating ranges ```scala def range( from: Int ): List = { if(from > 0) Cons(from, range(from - 1)) else Nil } ``` ```scala mkString(range(3)) ``` .center[] --- ## Creating ranges ```scala def range( `from: Int` ): List = { if(from > 0) Cons(from, range(from - 1)) else Nil } ``` ```scala mkString(range(3)) ``` .center[] --- ## Creating ranges ```scala def range( from: Int ): `List` = { if(from > 0) Cons(from, range(from - 1)) else Nil } ``` ```scala mkString(range(3)) ``` .center[] --- ## Creating ranges ```scala def range( from: Int ): List = { if(`from > 0`) Cons(from, range(from - 1)) else Nil } ``` ```scala mkString(range(3)) ``` .center[] --- ## Creating ranges ```scala def range( from: Int ): List = { if(from > 0) `Cons(from, range(from - 1))` else Nil } ``` ```scala mkString(range(3)) ``` .center[] --- ## Creating ranges ```scala def range( from: Int ): List = { if(from > 0) Cons(`from`, range(from - 1)) else Nil } ``` ```scala mkString(range(3)) ``` .center[] --- ## Creating ranges ```scala def range( from: Int ): List = { if(from > 0) Cons(from, `range(from - 1)`) else Nil } ``` ```scala mkString(range(3)) ``` .center[] --- ## Creating ranges ```scala def range( from: Int ): List = { if(`from > 0`) Cons(from, range(from - 1)) else Nil } ``` ```scala mkString(range(3)) ``` .center[] --- ## Creating ranges ```scala def range( from: Int ): List = { if(from > 0) `Cons(from, range(from - 1))` else Nil } ``` ```scala mkString(range(3)) ``` .center[] --- ## Creating ranges ```scala def range( from: Int ): List = { if(from > 0) Cons(`from`, range(from - 1)) else Nil } ``` ```scala mkString(range(3)) ``` .center[] --- ## Creating ranges ```scala def range( from: Int ): List = { if(from > 0) Cons(from, `range(from - 1)`) else Nil } ``` ```scala mkString(range(3)) ``` .center[] --- ## Creating ranges ```scala def range( from: Int ): List = { if(`from > 0`) Cons(from, range(from - 1)) else Nil } ``` ```scala mkString(range(3)) ``` .center[] --- ## Creating ranges ```scala def range( from: Int ): List = { if(from > 0) `Cons(from, range(from - 1))` else Nil } ``` ```scala mkString(range(3)) ``` .center[] --- ## Creating ranges ```scala def range( from: Int ): List = { if(from > 0) Cons(`from`, range(from - 1)) else Nil } ``` ```scala mkString(range(3)) ``` .center[] --- ## Creating ranges ```scala def range( from: Int ): List = { if(from > 0) Cons(from, `range(from - 1)`) else Nil } ``` ```scala mkString(range(3)) ``` .center[] --- ## Creating ranges ```scala def range( from: Int ): List = { if(`from > 0`) Cons(from, range(from - 1)) else Nil } ``` ```scala mkString(range(3)) ``` .center[] --- ## Creating ranges ```scala def range( from: Int ): List = { if(from > 0) Cons(from, range(from - 1)) else `Nil` } ``` ```scala mkString(range(3)) ``` .center[] --- ## Creating ranges ```scala def range( from: Int ): List = { if(from > 0) Cons(from, range(from - 1)) else Nil } ``` ```scala mkString(range(3)) ``` .center[] --- ## Creating ranges ```scala def range( from: Int ): List = { if(from > 0) Cons(from, range(from - 1)) else Nil } ``` ```scala mkString(range(3)) // res24: String = 3 :: 2 :: 1 :: nil ``` --- ## Creating ranges ```scala def range( from: Int ): List = { if(`from > 0`) Cons(from, range(from - 1)) else Nil } ``` ```scala mkString(range(3)) ``` --- ## Creating ranges ```scala def range( from: Int ): List = { if(from > 0) Cons(`from`, range(from - 1)) else Nil } ``` ```scala mkString(range(3)) ``` --- ## Creating ranges ```scala def range( from: Int ): List = { if(from > 0) Cons(from, range(`from - 1`)) else Nil } ``` ```scala mkString(range(3)) ``` --- ## Creating ranges ```scala def range( from: Int ): List = { if(from > 0) Cons(from, `range(from - 1)`) else Nil } ``` ```scala mkString(range(3)) ``` --- ## Creating ranges ```scala def range( from: Int ): List = { if(from > 0) `Cons(from, range(from - 1))` else Nil } ``` ```scala mkString(range(3)) ``` --- ## Creating ranges ```scala def range( from: Int ): List = { if(from > 0) Cons(from, range(from - 1)) else `Nil` } ``` ```scala mkString(range(3)) ``` --- ## Extracting character codes ```scala def charCodes( from: String ): List = { if(from.nonEmpty) Cons(from.head.toInt, charCodes(from.tail)) else Nil } ``` --- ## Extracting character codes ```scala def charCodes( `from: String` ): List = { if(from.nonEmpty) Cons(from.head.toInt, charCodes(from.tail)) else Nil } ``` --- ## Extracting character codes ```scala def charCodes( from: String ): `List` = { if(from.nonEmpty) Cons(from.head.toInt, charCodes(from.tail)) else Nil } ``` --- ## Extracting character codes ```scala def charCodes( from: String ): List = { if(`from.nonEmpty`) Cons(from.head.toInt, charCodes(from.tail)) else Nil } ``` --- ## Extracting character codes ```scala def charCodes( from: String ): List = { if(from.nonEmpty) Cons(`from.head.toInt`, charCodes(from.tail)) else Nil } ``` --- ## Extracting character codes ```scala def charCodes( from: String ): List = { if(from.nonEmpty) Cons(from.head.toInt, charCodes(`from.tail`)) else Nil } ``` --- ## Extracting character codes ```scala def charCodes( from: String ): List = { if(from.nonEmpty) Cons(from.head.toInt, `charCodes(from.tail)`) else Nil } ``` --- ## Extracting character codes ```scala def charCodes( from: String ): List = { if(from.nonEmpty) `Cons(from.head.toInt, charCodes(from.tail))` else Nil } ``` --- ## Extracting character codes ```scala def charCodes( from: String ): List = { if(from.nonEmpty) Cons(from.head.toInt, charCodes(from.tail)) else `Nil` } ``` --- ## Extracting character codes ```scala def charCodes( from: String ): List = { if(from.nonEmpty) Cons(from.head.toInt, charCodes(from.tail)) else Nil } ``` ```scala mkString(charCodes("cata")) // res25: String = 99 :: 97 :: 116 :: 97 :: nil ``` --- ## 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. --- class: center, middle # Generalised generative recursion --- ## Generalising `charCodes` ```scala def charCodes( from: String ): List = { if(from.nonEmpty) Cons(from.head.toInt, charCodes(from.tail)) else Nil } ``` --- ## Generalising `charCodes` .diff-rm[ ```scala *def `charCodes`( from: String ): List = { if(from.nonEmpty) * Cons(from.head.toInt, `charCodes`(from.tail)) else Nil } ``` ] --- ## Generalising `charCodes` .diff-add[ ```scala *def `recurse`( from: String ): List = { if(from.nonEmpty) * Cons(from.head.toInt, `recurse`(from.tail)) else Nil } ``` ] --- ## Generalising `charCodes` ```scala def recurse( from: String ): List = { if(from.nonEmpty) Cons(from.head.toInt, recurse(from.tail)) else Nil } ``` ```scala mkString(recurse("cata")) // res26: String = 99 :: 97 :: 116 :: 97 :: nil ``` --- ## Generalising `charCodes` .center[] --- ## Generalising `charCodes` .center[] --- ## Generalising `charCodes` .center[] --- ## Generalising `charCodes` .center[] --- ## Generalising `charCodes` .center[] --- ## Generalising `charCodes` .center[] --- ## Generalising `charCodes` .center[] --- ## Generalising `charCodes` .center[] --- ## Generalising `charCodes` .center[] --- ## Generalising `charCodes` .center[] --- ## Generalising the predicate .center[] --- ## Generalising the predicate ```scala def recurse( from: String ): List = { if(`from.nonEmpty`) Cons(from.head.toInt, recurse(from.tail)) else Nil } ``` --- ## Generalising the predicate ```scala def recurse( from: String ): List = { if(from.nonEmpty) Cons(from.head.toInt, recurse(from.tail)) else Nil } ``` ```scala *def predicate(from: String): Boolean = * from.nonEmpty ``` --- ## Generalising the predicate .diff-rm[ ```scala def recurse( from: String ): List = { * if(`from.nonEmpty`) Cons(from.head.toInt, recurse(from.tail)) else Nil } ``` ] ```scala def predicate(from: String): Boolean = from.nonEmpty ``` --- ## Generalising the predicate .diff-add[ ```scala def recurse( from: String ): List = { * if(`predicate(from)`) Cons(from.head.toInt, recurse(from.tail)) else Nil } ``` ] ```scala def predicate(from: String): Boolean = from.nonEmpty ``` --- ## Generalising the predicate .diff-add[ ```scala def recurse( * `predicate: String => Boolean`, from : String ): List = { if(predicate(from)) Cons(from.head.toInt, recurse(from.tail)) else Nil } ``` ] --- ## Generalising the predicate .diff-add[ ```scala def recurse( predicate: String => Boolean, from : String ): List = { if(predicate(from)) * Cons(from.head.toInt, recurse(`predicate`, from.tail)) else Nil } ``` ] --- ## Generalising the predicate ```scala def recurse( predicate: String => Boolean, from : String ): List = { if(predicate(from)) Cons(from.head.toInt, recurse(predicate, from.tail)) else Nil } ``` ```scala mkString(recurse(predicate, "cata")) // res27: String = 99 :: 97 :: 116 :: 97 :: nil ``` --- ## Generalising the predicate .center[] --- ## Generalising the predicate .center[] --- ## Generalising the update .center[] --- ## Generalising the update ```scala def recurse( predicate: String => Boolean, from : String ): List = { if(predicate(from)) Cons(`from.head.toInt`, recurse(predicate, `from.tail`)) else Nil } ``` --- ## Generalising the update ```scala def recurse( predicate: String => Boolean, from : String ): List = { if(predicate(from)) Cons(from.head.toInt, recurse(predicate, from.tail)) else Nil } ``` ```scala *def update(from: String): (Int, String) = * (from.head.toInt, from.tail) ``` --- ## Generalising the update .diff-rm[ ```scala def recurse( predicate: String => Boolean, from : String ): List = { if(predicate(from)) * `Cons(from.head.toInt, recurse(predicate, from.tail))` else Nil } ``` ] ```scala def update(from: String): (Int, String) = (from.head.toInt, from.tail) ``` --- ## Generalising the update .diff-add[ ```scala def recurse( predicate: String => Boolean, from : String ): List = { if(predicate(from)) { * `val (head, nextState) = update(from)` * `Cons(head, recurse(predicate, nextState))` } else Nil } ``` ] ```scala def update(from: String): (Int, String) = (from.head.toInt, from.tail) ``` --- ## Generalising the update ```scala def recurse( predicate: String => Boolean, from : String ): List = { if(predicate(from)) { val (head, nextState) = `update(from)` Cons(head, recurse(predicate, nextState)) } else Nil } ``` ```scala def update(from: String): (Int, String) = (from.head.toInt, from.tail) ``` --- ## Generalising the update ```scala def recurse( predicate: String => Boolean, from : String ): List = { if(predicate(from)) { val `(head, nextState)` = update(from) Cons(head, recurse(predicate, nextState)) } else Nil } ``` ```scala def update(from: String): (Int, String) = (from.head.toInt, from.tail) ``` --- ## Generalising the update ```scala def recurse( predicate: String => Boolean, from : String ): List = { if(predicate(from)) { val (head, nextState) = update(from) Cons(`head`, recurse(predicate, nextState)) } else Nil } ``` ```scala def update(from: String): (Int, String) = (from.head.toInt, from.tail) ``` --- ## Generalising the update ```scala def recurse( predicate: String => Boolean, from : String ): List = { if(predicate(from)) { val (head, nextState) = update(from) Cons(head, recurse(predicate, `nextState`)) } else Nil } ``` ```scala def update(from: String): (Int, String) = (from.head.toInt, from.tail) ``` --- ## Generalising the update .diff-add[ ```scala 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 } ``` ] --- ## Generalising the update .diff-add[ ```scala 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 } ``` ] --- ## Generalising the update ```scala 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 } ``` ```scala mkString(recurse(predicate, update, "cata")) // res28: String = 99 :: 97 :: 116 :: 97 :: nil ``` --- ## Generalising the update .center[] --- ## Generalising the update .center[] --- ## Generalising the input type .center[] --- ## Generalising the input type ```scala 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 } ``` --- ## Generalising the input type .diff-add[ ```scala *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 } ``` ] --- ## Generalising the input type .diff-rm[ ```scala 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 } ``` ] --- ## Generalising the input type .diff-add[ ```scala 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 } ``` ] --- ## Generalising the input type ```scala 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 } ``` ```scala mkString(recurse(predicate, update, "cata")) // res29: String = 99 :: 97 :: 116 :: 97 :: nil ``` --- ## Generalising the input type .center[] --- ## Generalising the input type .center[] --- ## Generalising the input type .center[] --- ## Simplifying the step ```scala 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 } ``` --- ## Simplifying the step ```scala 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 } ``` --- ## Simplifying the step ```scala 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 } ``` --- ## Simplifying the step .diff-rm[ ```scala 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` } ``` ] --- ## Simplifying the step .diff-add[ ```scala 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) } ``` ] --- ## Simplifying the step .diff-add[ ```scala 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)` } ``` ] --- ## Simplifying the step ```scala 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) } ``` --- ## Simplifying the step ```scala 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) } ``` --- ## Simplifying the step ```scala 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) } ``` --- ## Simplifying the step ```scala 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) } ``` --- ## Simplifying the step .center[] --- ## Simplifying the step .center[] --- ## Simplifying the step .center[] --- ## Dropping parameters .diff-rm[ ```scala 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)` } ``` ] --- ## Dropping parameters .diff-add[ ```scala 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` } ``` ] --- ## Dropping parameters .diff-rm[ ```scala 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 } ``` ] --- ## Dropping parameters .diff-add[ ```scala 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 } ``` ] --- ## Dropping parameters ```scala 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 } ``` ```scala mkString(recurse(predicate, update)("cata")) // res30: String = 99 :: 97 :: 116 :: 97 :: nil ``` --- ## Naming things .diff-rm[ ```scala *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 } ``` ] --- ## Naming things .diff-add[ ```scala *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 } ``` ] --- ## Naming things ```scala 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 } ``` ```scala mkString(unfold(predicate, update)("cata")) // res31: String = 99 :: 97 :: 116 :: 97 :: nil ``` --- ## `range` as an unfold ```scala val range: Int => List = unfold[Int]( predicate = state => state > 0, update = state => (state, state - 1) ) ``` --- ## `range` as an unfold ```scala val range: Int => List = `unfold`[Int]( predicate = state => state > 0, update = state => (state, state - 1) ) ``` --- ## `range` as an unfold ```scala val range: Int => List = unfold[Int]( `predicate = state => state > 0`, update = state => (state, state - 1) ) ``` --- ## `range` as an unfold ```scala val range: Int => List = unfold[Int]( predicate = state => state > 0, `update = state => (state, state - 1)` ) ``` --- ## `range` as an unfold ```scala val range: Int => List = unfold[Int]( predicate = state => state > 0, update = state => (state, state - 1) ) ``` ```scala mkString(range(3)) // res32: String = 3 :: 2 :: 1 :: nil ``` --- ## Key takeaways Generative recursion is generalised by: -- * parameterising the predicate. -- * parameterising the state update. -- * ... knowing the structure of your type. --- class: center, middle # Generalised unfolds --- ## Generalised unfolds ```scala 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 } ``` --- ## Generalised unfolds .center[] --- ## Simplifying `predicate` and `update` .center[] --- ## Simplifying `predicate` and `update` .center[] --- ## Simplifying `predicate` and `update` ```scala 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 } ``` --- ## Simplifying `predicate` and `update` ```scala val op: String => Option[(Int, String)] = state => { if(predicate(state)) Some(update(state)) else None } ``` --- ## Simplifying `predicate` and `update` ```scala val `op`: String => Option[(Int, String)] = state => { if(predicate(state)) Some(update(state)) else None } ``` --- ## Simplifying `predicate` and `update` .diff-rm[ ```scala val op: String => Option[(Int, String)] = state => { * if(`predicate(state)`) Some(update(state)) else None } ``` ] --- ## Simplifying `predicate` and `update` .diff-add[ ```scala val op: String => Option[(Int, String)] = state => { * if(`state.nonEmpty`) Some(update(state)) else None } ``` ] --- ## Simplifying `predicate` and `update` ```scala val op: String => Option[(Int, String)] = state => { if(state.nonEmpty) `Some(update(state))` else None } ``` --- ## Simplifying `predicate` and `update` .diff-rm[ ```scala val op: String => Option[(Int, String)] = state => { * if(state.nonEmpty) Some(`update(state)`) else None } ``` ] --- ## Simplifying `predicate` and `update` .diff-add[ ```scala val op: String => Option[(Int, String)] = state => { * if(state.nonEmpty) Some(`(state.head.toInt, state.tail)`) else None } ``` ] --- ## Simplifying `predicate` and `update` ```scala val op: String => Option[(Int, String)] = state => { if(state.nonEmpty) Some((state.head.toInt, state.tail)) else `None` } ``` --- ## Simplifying `predicate` and `update` .diff-rm[ ```scala *val op: String => `Option[(Int, String)]` = state => { if(state.nonEmpty) Some((state.head.toInt, state.tail)) else None } ``` ] --- ## Simplifying `predicate` and `update` .diff-add[ ```scala *val op: String => `ListF[String]` = state => { if(state.nonEmpty) Some((state.head.toInt, state.tail)) else None } ``` ] --- ## Simplifying `predicate` and `update` ```scala val op: String => ListF[String] = state => { if(state.nonEmpty) Some((state.head.toInt, state.tail)) else None } ``` --- ## Simplifying `predicate` and `update` .diff-rm[ ```scala 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 } ``` ] --- ## Simplifying `predicate` and `update` .diff-add[ ```scala 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 } ``` ] --- ## Simplifying `predicate` and `update` .diff-rm[ ```scala 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 } ``` ] --- ## Simplifying `predicate` and `update` .diff-add[ ```scala 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 } ``` ] --- ## Simplifying `predicate` and `update` ```scala 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 } ``` --- ## Simplifying `predicate` and `update` ```scala 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 } ``` --- ## Simplifying `predicate` and `update` ```scala 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 } ``` --- ## Simplifying `predicate` and `update` ```scala 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 } ``` --- ## Simplifying `predicate` and `update` ```scala 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 } ``` --- ## Simplifying `predicate` and `update` ```scala 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 } ``` ```scala mkString(unfold(op)("cata")) // res33: String = 99 :: 97 :: 116 :: 97 :: nil ``` --- ## Simplifying `predicate` and `update` .center[] --- ## Simplifying `predicate` and `update` .center[] --- ## Abstracting over structure .center[] --- ## Abstracting over structure ```scala 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 } ``` --- ## Abstracting over structure ```scala val embed: Option[(Int, List)] => List = { case Some((head, tail)) => Cons(head, tail) case None => Nil } ``` --- ## Abstracting over structure ```scala val `embed`: Option[(Int, List)] => List = { case Some((head, tail)) => Cons(head, tail) case None => Nil } ``` --- ## Abstracting over structure ```scala val embed: Option[(Int, List)] => List = { case `Some((head, tail))` => Cons(head, tail) case None => Nil } ``` --- ## Abstracting over structure ```scala val embed: Option[(Int, List)] => List = { case Some((head, tail)) => `Cons(head, tail)` case None => Nil } ``` --- ## Abstracting over structure ```scala val embed: Option[(Int, List)] => List = { case Some((head, tail)) => Cons(head, tail) case `None` => Nil } ``` --- ## Abstracting over structure ```scala val embed: Option[(Int, List)] => List = { case Some((head, tail)) => Cons(head, tail) case None => `Nil` } ``` --- ## Abstracting over structure .diff-rm[ ```scala *val embed: `Option[(Int, List)]` => List = { case Some((head, tail)) => Cons(head, tail) case None => Nil } ``` ] --- ## Abstracting over structure .diff-add[ ```scala *val embed: `ListF[List]` => List = { case Some((head, tail)) => Cons(head, tail) case None => Nil } ``` ] --- ## Abstracting over structure ```scala val embed: ListF[List] => List = { case Some((head, tail)) => Cons(head, tail) case None => Nil } ``` --- ## Abstracting over structure ```scala 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 } ``` --- ## Abstracting over structure .diff-add[ ```scala 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 } ``` ] --- ## Abstracting over structure .diff-rm[ ```scala 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 } ``` ] --- ## Abstracting over structure .diff-add[ ```scala 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 } ``` ] --- ## Abstracting over structure .diff-rm[ ```scala 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 } ``` ] --- ## Abstracting over structure .diff-add[ ```scala 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 } ``` ] --- ## Abstracting over structure ```scala 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 } ``` --- ## Abstracting over structure .diff-rm[ ```scala 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 } ``` ] --- ## Abstracting over structure .diff-add[ ```scala 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 } ``` ] --- ## Abstracting over structure ```scala 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 } ``` ```scala mkString(unfold(op, embed)("cata")) // res34: String = 99 :: 97 :: 116 :: 97 :: nil ``` --- ## Abstracting over structure .center[] --- ## Abstracting over structure .center[] --- ## Using Functor .center[] --- ## Using Functor .center[] --- ## Using Functor ```scala 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 } ``` --- ## Using Functor ```scala 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 } ``` --- ## Using Functor ```scala 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 } ``` --- ## Using Functor ```scala 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 } ``` --- ## Using Functor ```scala 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 } ``` --- ## Using Functor .diff-rm[ ```scala 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 } ``` ] --- ## Using Functor .diff-add[ ```scala def unfold[A]( op : A => ListF[A], embed: ListF[List] => List ): A => List = { def loop(state: A): List = * `embed(map(op(state), loop))` loop } ``` ] --- ## Using Functor ```scala def unfold[A]( op : A => ListF[A], embed: ListF[List] => List ): A => List = { def loop(state: A): List = embed(map(op(state), loop)) loop } ``` ```scala mkString(unfold(op, embed)("cata")) // res35: String = 99 :: 97 :: 116 :: 97 :: nil ``` --- ## Using Functor .center[] --- ## Using Functor .center[] --- ## Abstracting over `ListF` .center[] --- ## Abstracting over `ListF` ```scala def unfold[A]( op : A => `ListF`[A], embed: `ListF`[List] => List ): A => List = { def loop(state: A): List = embed(map(op(state), loop)) loop } ``` --- ## Abstracting over `ListF` ```scala def unfold[A]( op : A => ListF[A], embed: ListF[List] => List ): A => List = { def loop(state: A): List = embed(`map`(op(state), loop)) loop } ``` --- ## Abstracting over `ListF` .diff-add[ ```scala *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 } ``` ] --- ## Abstracting over `ListF` .diff-rm[ ```scala 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 } ``` ] --- ## Abstracting over `ListF` .diff-add[ ```scala 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 } ``` ] --- ## Abstracting over `ListF` ```scala 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 } ``` ```scala mkString(unfold(op, embed).apply("cata")) // res36: String = 99 :: 97 :: 116 :: 97 :: nil ``` --- ## Abstracting over `ListF` .center[] --- ## Abstracting over `ListF` .center[] --- ## Abstracting over `List` .center[] --- ## Abstracting over `List` ```scala 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 } ``` --- ## Abstracting over `List` .diff-add[ ```scala *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 } ``` ] --- ## Abstracting over `List` .diff-rm[ ```scala 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 } ``` ] --- ## Abstracting over `List` .diff-add[ ```scala 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 } ``` ] --- ## Abstracting over `List` ```scala 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 } ``` ```scala mkString(unfold(op, embed).apply("cata")) // res37: String = 99 :: 97 :: 116 :: 97 :: nil ``` --- ## Abstracting over `List` .center[] --- ## Abstracting over `List` .center[] --- ## Abstracting over `List` .center[] --- ## Naming things .diff-rm[ ```scala *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 } ``` ] --- ## Naming things .diff-add[ ```scala *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 } ``` ] --- ## Naming things .diff-rm[ ```scala 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 } ``` ] --- ## Naming things .diff-add[ ```scala 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 } ``` ] --- ## Naming things ```scala 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 } ``` ```scala mkString(ana(op, embed).apply("cata")) // res38: String = 99 :: 97 :: 116 :: 97 :: nil ``` --- ## Naming things .center[] --- ## Naming things .center[] --- ## Naming things .center[] --- ## `range` as an ana ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(i > 0) Some((i, i - 1)) else None } val range: Int => List = ana(rangeCoAlgebra, embed) ``` --- ## `range` as an ana ```scala val `rangeCoAlgebra`: Int => ListF[Int] = i => { if(i > 0) Some((i, i - 1)) else None } val range: Int => List = ana(rangeCoAlgebra, embed) ``` --- ## `range` as an ana ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(`i > 0`) Some((i, i - 1)) else None } val range: Int => List = ana(rangeCoAlgebra, embed) ``` --- ## `range` as an ana ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(i > 0) `Some((i, i - 1))` else None } val range: Int => List = ana(rangeCoAlgebra, embed) ``` --- ## `range` as an ana ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(i > 0) Some((i, i - 1)) else `None` } val range: Int => List = ana(rangeCoAlgebra, embed) ``` --- ## `range` as an ana ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(i > 0) Some((i, i - 1)) else None } val range: Int => List = `ana(rangeCoAlgebra, embed)` ``` --- ## `range` as an ana ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(i > 0) Some((i, i - 1)) else None } val range: Int => List = ana(rangeCoAlgebra, embed) ``` ```scala mkString(range(3)) // res39: String = 3 :: 2 :: 1 :: nil ``` --- ## 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... --- class: center, middle # Generalised generalised folds! --- ## `cata` and `ana` .center[] --- ## `cata` and `ana` .center[] --- ## `cata` and `ana` .center[] --- ## Duality of `cata` and `ana` .center[] --- ## Duality of `cata` and `ana` .center[] --- ## Duality of `cata` and `ana` .center[] --- ## Duality of `cata` and `ana` .center[] --- ## Duality of `cata` and `ana` .center[] --- ## Composing `cata` and `ana` .center[] --- ## Composing `cata` and `ana` .center[] --- ## Composing `cata` and `ana` .center[] --- ## Composing `cata` and `ana` ```scala val factorial: Int => Int = range andThen product ``` --- ## Composing `cata` and `ana` ```scala val `factorial`: Int => Int = range andThen product ``` --- ## Composing `cata` and `ana` ```scala val factorial: Int => Int = `range` andThen product ``` --- ## Composing `cata` and `ana` ```scala val factorial: Int => Int = range andThen `product` ``` --- ## Composing `cata` and `ana` ```scala val factorial: Int => Int = range andThen product ``` ```scala factorial(3) // res40: Int = 6 ``` --- ## Composing `cata` and `ana` ```scala val showRange: Int => String = range andThen mkString ``` --- ## Composing `cata` and `ana` ```scala val `showRange`: Int => String = range andThen mkString ``` --- ## Composing `cata` and `ana` ```scala val showRange: Int => String = `range` andThen mkString ``` --- ## Composing `cata` and `ana` ```scala val showRange: Int => String = range andThen `mkString` ``` --- ## Composing `cata` and `ana` ```scala val showRange: Int => String = range andThen mkString ``` ```scala showRange(3) // res41: String = 3 :: 2 :: 1 :: nil ``` --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` ```scala 3 ``` --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` ```scala 3 // rangeCoAlgebra ``` ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(i > 0) Some((i, i - 1)) else None } ``` --- ## Simplifying `ana andThen cata` ```scala ​`3` // rangeCoAlgebra ``` ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(`i > 0`) Some((i, i - 1)) else None } ``` --- ## Simplifying `ana andThen cata` ```scala ​`Some`((3, 2)) // rangeCoAlgebra ``` ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(i > 0) `Some`((i, i - 1)) else None } ``` --- ## Simplifying `ana andThen cata` ```scala Some((`3`, 2)) // rangeCoAlgebra ``` ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(i > 0) Some((`i`, i - 1)) else None } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, `2`)) // rangeCoAlgebra ``` ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(i > 0) Some((i, `i - 1`)) else None } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, `2`)) // rangeCoAlgebra ``` ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(`i > 0`) Some((i, i - 1)) else None } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, `Some`((2, 1))) // rangeCoAlgebra ``` ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(i > 0) `Some`((i, i - 1)) else None } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((`2`, 1))) // rangeCoAlgebra ``` ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(i > 0) Some((`i`, i - 1)) else None } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, `1`))) // rangeCoAlgebra ``` ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(i > 0) Some((i, `i - 1`)) else None } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, `1`))) // rangeCoAlgebra ``` ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(`i > 0`) Some((i, i - 1)) else None } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, `Some`((1, 0))))) // rangeCoAlgebra ``` ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(i > 0) `Some`((i, i - 1)) else None } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, Some((`1`, 0))))) // rangeCoAlgebra ``` ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(i > 0) Some((`i`, i - 1)) else None } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, Some((1, `0`))))) // rangeCoAlgebra ``` ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(i > 0) Some((i, `i - 1`)) else None } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, Some((1, `0`))))) // rangeCoAlgebra ``` ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(`i > 0`) Some((i, i - 1)) else None } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, Some((1, `None`))))) // rangeCoAlgebra ``` ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(i > 0) Some((i, i - 1)) else `None` } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra ``` ```scala val rangeCoAlgebra: Int => ListF[Int] = i => { if(i > 0) Some((i, i - 1)) else None } ``` --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra ​ // embed ``` ```scala val embed: ListF[List] => List = { case Some((head, tail)) => Cons(head, tail) case None => Nil } ``` --- ## Simplifying `ana andThen cata` ```scala ​`Some`((3, `Some`((2, `Some`((1, None))))) // rangeCoAlgebra ​ // embed ``` ```scala val embed: ListF[List] => List = { case `Some`((head, tail)) => Cons(head, tail) case None => Nil } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra ​`Cons`( `Cons`( `Cons`( ))) // embed ``` ```scala val embed: ListF[List] => List = { case Some((head, tail)) => `Cons`(head, tail) case None => Nil } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, Some((1, `None`))))) // rangeCoAlgebra Cons( Cons( Cons( ))) // embed ``` ```scala val embed: ListF[List] => List = { case Some((head, tail)) => Cons(head, tail) case `None` => Nil } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra Cons( Cons( Cons( `Nil` ))) // embed ``` ```scala val embed: ListF[List] => List = { case Some((head, tail)) => Cons(head, tail) case None => `Nil` } ``` --- ## Simplifying `ana andThen cata` ```scala Some((`3`, Some((`2`, Some((`1`, None))))) // rangeCoAlgebra Cons( Cons( Cons( Nil ))) // embed ``` ```scala val embed: ListF[List] => List = { case Some((`head`, tail)) => Cons(head, tail) case None => Nil } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra Cons( `3`, Cons( `2`, Cons( `1`, Nil ))) // embed ``` ```scala val embed: ListF[List] => List = { case Some((head, tail)) => Cons(`head`, tail) case None => Nil } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra Cons( 3, Cons( 2, Cons( 1, Nil ))) // embed ``` ```scala val embed: ListF[List] => List = { case Some((head, tail)) => Cons(head, tail) case None => Nil } ``` --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra Cons( 3, Cons( 2, Cons( 1, Nil ))) // embed // project ``` ```scala val project: List => ListF[List] = { case Cons(head, tail) => Some((head, tail)) case Nil => None } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra ​`Cons`( 3, `Cons`( 2, `Cons`( 1, Nil ))) // embed // project ``` ```scala val project: List => ListF[List] = { case `Cons`(head, tail) => Some((head, tail)) case Nil => None } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra Cons( 3, Cons( 2, Cons( 1, Nil ))) // embed ​`Some`(( `Some`(( `Some`(( ))))) // project ``` ```scala val project: List => ListF[List] = { case Cons(head, tail) => `Some`((head, tail)) case Nil => None } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra Cons( 3, Cons( 2, Cons( 1, `Nil` ))) // embed Some(( Some(( Some(( ))))) // project ``` ```scala val project: List => ListF[List] = { case Cons(head, tail) => Some((head, tail)) case `Nil` => None } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra Cons( 3, Cons( 2, Cons( 1, Nil ))) // embed Some(( Some(( Some(( `None`))))) // project ``` ```scala val project: List => ListF[List] = { case Cons(head, tail) => Some((head, tail)) case Nil => `None` } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra Cons( `3`, Cons( `2`, Cons( `1`, Nil ))) // embed Some(( Some(( Some(( `None`))))) // project ``` ```scala val project: List => ListF[List] = { case Cons(`head`, tail) => Some((head, tail)) case Nil => None } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra Cons( 3, Cons( 2, Cons( 1, Nil ))) // embed Some((`3`, Some((`2`, Some((`1`, None))))) // project ``` ```scala val project: List => ListF[List] = { case Cons(head, tail) => Some((`head`, tail)) case Nil => None } ``` --- ## Simplifying `ana andThen cata` ```scala Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra Cons( 3, Cons( 2, Cons( 1, Nil ))) // embed Some((3, Some((2, Some((1, None))))) // project ``` ```scala val project: List => ListF[List] = { case Cons(head, tail) => Some((head, tail)) case Nil => None } ``` --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` ```scala 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 ``` ```scala val mkStringAlgebra: ListF[String] => String = { case Some((head, tailResult)) => step(head, tailResult) case None => base } ``` --- ## Simplifying `ana andThen cata` ```scala 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 ``` ```scala val mkStringAlgebra: ListF[String] => String = { case `Some`((head, tailResult)) => step(head, tailResult) case None => base } ``` --- ## Simplifying `ana andThen cata` ```scala 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 ``` ```scala val mkStringAlgebra: ListF[String] => String = { case Some((head, tailResult)) => `step`(head, tailResult) case None => base } ``` --- ## Simplifying `ana andThen cata` ```scala 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 ``` ```scala val mkStringAlgebra: ListF[String] => String = { case Some((head, tailResult)) => step(head, tailResult) case `None` => base } ``` --- ## Simplifying `ana andThen cata` ```scala 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 ``` ```scala val mkStringAlgebra: ListF[String] => String = { case Some((head, tailResult)) => step(head, tailResult) case None => `base` } ``` --- ## Simplifying `ana andThen cata` ```scala 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 ``` ```scala val mkStringAlgebra: ListF[String] => String = { case Some((`head`, tailResult)) => step(head, tailResult) case None => base } ``` --- ## Simplifying `ana andThen cata` ```scala 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 ``` ```scala val mkStringAlgebra: ListF[String] => String = { case Some((head, tailResult)) => step(`head`, tailResult) case None => base } ``` --- ## Simplifying `ana andThen cata` ```scala 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 ``` ```scala val mkStringAlgebra: ListF[String] => String = { case Some((head, tailResult)) => step(head, tailResult) case None => base } ``` --- ## Simplifying `ana andThen cata` ```scala ​`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 ``` --- ## Simplifying `ana andThen cata` .diff-rm[ ```scala 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 ``` ] --- ## Simplifying `ana andThen cata` .diff-rm[ ```scala 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 ``` ] --- ## Simplifying `ana andThen cata` .diff-rm[ ```scala Some((3, Some((2, Some((1, None))))) // rangeCoAlgebra step( 3, step( 2, step( 1, base))) // mkStringAlgebra ``` ] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` .center[] --- ## Simplifying `ana andThen cata` ```scala 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 } ``` --- ## Simplifying `ana andThen cata` .diff-rm[ ```scala 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 } ``` ] --- ## Simplifying `ana andThen cata` .diff-add[ ```scala 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 } ``` ] --- ## Simplifying `ana andThen cata` ```scala 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 } ``` --- ## Simplifying `ana andThen cata` ```scala def showRange: Int => String = ana(rangeCoAlgebra, mkStringAlgebra) ``` --- ## Simplifying `ana andThen cata` ```scala def `showRange`: Int => String = ana(rangeCoAlgebra, mkStringAlgebra) ``` --- ## Simplifying `ana andThen cata` ```scala def showRange: Int => String = `ana`(rangeCoAlgebra, mkStringAlgebra) ``` --- ## Simplifying `ana andThen cata` ```scala def showRange: Int => String = ana(`rangeCoAlgebra`, mkStringAlgebra) ``` --- ## Simplifying `ana andThen cata` ```scala def showRange: Int => String = ana(rangeCoAlgebra, `mkStringAlgebra`) ``` --- ## Simplifying `ana andThen cata` ```scala def showRange: Int => String = ana(rangeCoAlgebra, mkStringAlgebra) ``` ```scala showRange(3) // res42: String = 3 :: 2 :: 1 :: nil ``` --- ## Naming things .diff-rm[ ```scala *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 } ``` ] --- ## Naming things .diff-add[ ```scala *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 } ``` ] --- ## Naming things ```scala 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 } ``` --- ## A magic trick .diff-rm[ ```scala 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 } ``` ] --- ## A magic trick .diff-add[ ```scala 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 } ``` ] --- ## A magic trick .diff-rm[ ```scala 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 } ``` ] --- ## A magic trick .diff-rm[ ```scala 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 } ``` ] --- ## A magic trick .diff-rm[ ```scala 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 } ``` ] --- ## A magic trick .diff-add[ ```scala 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 } ``` ] --- ## A magic trick ```scala 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 } ``` --- ## A magic trick ```scala 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 } ``` --- ## Key takeaways * catamorphisms and anamorphisms are duals of each other. -- * they're also the same thing. -- * yes, this gives me a headache too. --- class: center, middle name: closing # In closing --- ## 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. --- class: center, middle name: questions # Questions? Nicolas Rinaudo • [@NicolasRinaudo] • [Besedo] [@NicolasRinaudo]:https://twitter.com/NicolasRinaudo [Besedo]:https://twitter.com/besedo_official