Ok so let's look at a recursive data type.
Rob Norris • @tpolecat
• Gemini Observatory
Ok so let's look at a recursive data type.
A recursive data type for professors and their Ph.D. students.
case class Prof( name: String, year: Int, students: List[Prof])
A recursive data type for professors and their Ph.D. students.
case class Prof( name: String, year: Int, students: List[Prof])
Natural SQL representation:
CREATE TABLE prof ( id INTEGER IDENTITY, parent INTEGER NULL, name VARCHAR NOT NULL, year INTEGER NOT NULL, FOREIGN KEY(parent) REFERENCES prof(id) )
A recursive data type for professors and their Ph.D. students.
case class Prof( id : Int @@ Prof, name: String, year: Int, students: List[Prof])
Natural SQL representation.
CREATE TABLE prof ( id INTEGER IDENTITY, parent INTEGER NULL, name VARCHAR NOT NULL, year INTEGER NOT NULL, FOREIGN KEY(parent) REFERENCES prof(id) )
Int
.A recursive data type for professors and their Ph.D. students.
case class Prof( id : Int, name: String, year: Int, students: List[Prof])
A recursive data type for professors and their Ph.D. students.
case class Prof( id : Option[Int], name: String, year: Int, students: List[Prof])
And this encoding is irritating in all three cases, so I don't like it.
So a way to make the id less invasive is to externalize it.
A recursive data type for professors and their Ph.D. students.
case class Prof( name: String, year: Int, students: List[Prof])type IdProf = (Int, Prof)
A recursive data type for professors and their Ph.D. students.
case class Prof( name: String, year: Int, students: List[(Int, Prof)])type IdProf = (Int, Prof)
So let's try something else. Let's parameterize it on the child type.
A recursive data type for professors and their Ph.D. students.
case class ProfF[A]( name: String, year: Int, students: List[A])
type Prof = ProfF[ProfF]type IdProf = (Int, ProfF[(Int, ProfF)])
ProfF
just to distinguish it from our old Prof
, so now we can just say ...A recursive data type for professors and their Ph.D. students.
case class ProfF[A]( name: String, year: Int, students: List[A])
type Prof = ProfF[ProfF[ProfF[ProfF[ProfF[ProfF[ProfF[ProfF[ProfF[ProfF[ProfF[ProfF[ProfF[ProfF[ProfF[ProfF[ProfF[type IdProf = (Int, ProfF[(Int, ProfF[(Int, ProfF[(Int, ProfF[(Int, ProfF[(Int, ProfF[(Int, ProfF[(Int, ProfF[(Int,
A recursive data type for professors and their Ph.D. students.
case class ProfF[A]( name: String, year: Int, students: List[A])
type Prof = ProfF[Prof]type IdProf = (Int, ProfF[IdProf])
A recursive data type for professors and their Ph.D. students.
case class ProfF[A]( name: String, year: Int, students: List[A])
case class Prof(value: ProfF[Prof])case class IdProf(id: Int, value: ProfF[IdProf])
ProfF
, and depending on how we wrap it we can represent just the pure data or the data annotated with database ids.A recursive data type for professors and their Ph.D. students.
case class ProfF[A]( name: String, year: Int, students: List[A])
case class Prof[F[_]](value: F[Prof])case class IdProf[F[_]](id: Int, value: F[IdProf])
Prof
needs a type argument, which is ... F
right?A recursive data type for professors and their Ph.D. students.
case class ProfF[A]( name: String, year: Int, students: List[A])
case class Prof[F[_]](value: F[Prof[F]])case class IdProf[F[_]](id: Int, value: F[IdProf[F]])
Int
so let's factor that out too.A recursive data type for professors and their Ph.D. students.
case class ProfF[A]( name: String, year: Int, students: List[A])
case class Prof[F[_]](value: F[Prof[F]])case class IdProf[F[_], A](id: A, value: F[IdProf[F, A]])
A
to the type argument here since IdProf
now has two type parameters.F
recursive, and the second can make any F
recursive and annotate each value with some arbitrary label.A recursive data type for professors and their Ph.D. students.
case class ProfF[A]( name: String, year: Int, students: List[A])
case class Fix[F[_]](unfix: F[Fix[F]])case class Cofree[F[_], A](head: A, tail: F[Cofree[F, A]])
Cofree
(sometimes called the cofree comonad) is the dual of the Free
monad, which everyone spent the last few years talking about at Scala conferences. Cofree is an A and an F[Cofree[F, A]]
and Free is an A
or an F[Free[F,A]]
. So that's how they're related and that's where the name comes from.and i'll also say that both free and cofree are really just special cases of Fix
, and I think Greg Pfiel will have something to say about that in the talk that's coming up next.
but this illustrates what I mean about pushing on code. if you push hard enough sometimes it disappears entirely, because:
Cofree
and neither provides Fix
.Prof
and ProfF
trivially.A recursive data type for professors and their Ph.D. students.
case class ProfF[A]( name: String, year: Int, students: List[A])
case class Fix[F[_]](unfix: F[Fix[F]])case class Cofree[F[_], A](head: A, tail: F[Cofree[F, A]])
Annotated and un-annotated ProfF
trees.
type Prof = Fix[ProfF]type IdProf = Cofree[ProfF, Int]
case class Prof(name: String, year: Int, students: List[Prof])val p: Prof = Prof("Hilbert", 1885, List( Prof("Ackermann", 1925, Nil), Prof("Curry", 1930, Nil), Prof("Weyl", 1908, List( Prof("Mac Lane", 1934, List( Prof("Howard", 1956, Nil), Prof("Awodey", 1997, Nil) )) )) ))
case class ProfF[A](name: String, year: Int, students: List[A])type Prof = Fix[ProfF]val p: Prof = Fix(ProfF("Hilbert", 1885, List( Fix(ProfF("Ackermann", 1925, Nil)), Fix(ProfF("Curry", 1930,Nil)), Fix(ProfF("Weyl", 1908, List( Fix(ProfF("Mac Lane", 1934, List( Fix(ProfF("Howard", 1956, Nil)), Fix(ProfF("Awodey", 1997, Nil)) )))) ))) ))
Fix
. It's identical in structure but there's an extra Fix
constructor wrapped around the ProfF
constructor.case class ProfF[A](name: String, year: Int, students: List[A])type IdProf = Cofree[ProfF, Int]val p: IdProf = Cofree(1, ProfF("Hilbert", 1885, List( Cofree(2, ProfF("Ackermann", 1925, Nil)), Cofree(3, ProfF("Curry", 1930,Nil)), Cofree(4, ProfF("Weyl", 1908, List( Cofree(5, ProfF("Mac Lane", 1934, List( Cofree(6, ProfF("Howard", 1956, Nil)), Cofree(7, ProfF("Awodey", 1997, Nil)) )))) ))) ))
Cofree
version, which also has an annotation (an Int
in this case) associated with each node.Ok, so before we get back to our database problem I want to take a detour and show you an example of programming with these types in a totally pure context, without worrying about IO effects.
So we're going to write some parsers.
case class ProfF[A](name: String, year: Int, students: List[A])val data = """|Simeon Denis Poisson, 1800 | Gustav Peter Lejeune Dirichlet, 1827 | Rudolf Otto Sigismund Lipschitz, 1853 | C. Felix (Christian) Klein, 1868 | William Edward Story, 1875 | Solomon Lefschetz, 1911 | Albert William Tucker, 1932 | Marvin Lee Minsky, 1954 | Gerald Jay Sussman, 1973 | Guy Lewis Steele, 1980 | Philip Lee Wadler, 1984 | C. L. Ferdinand (Carl Louis) Lindemann, 1873 | David Hilbert, 1885 | Wilhelm Ackermann, 1925 | Haskell Curry, 1930 | Hermann Weyl, 1908 | Saunders Mac Lane, 1934 | Steven Awodey, 1997 | William Howard, 1956 |""".stripMargin
So, here's some sample data that we want to parse into our fixpoint types. You may recognize some of these names.
def prof(n: Int): Parser[Fix[ProfF]] = for { _ <- manyN(n, char(' ')) // skip 'n' spaces name <- stringOf(notChar(',')) // read up to a comma _ <- token(char(',')) // skip comma and following space year <- int // read an int _ <- char('\n') // skip a newline ss <- many(prof(n + 2)) // recursively read more at indent + 2 } yield Fix(ProfF(name, year, ss))
atto
which is a parsing library I work on but it would look the same with Li Haoyi's Fastparse or pretty much any monadic parser combinator library.def prof(n: Int): Parser[Fix[ProfF]] = for { _ <- manyN(n, char(' ')) // skip 'n' spaces name <- stringOf(notChar(',')) // read up to a comma _ <- token(char(',')) // skip comma and following space year <- int // read an int _ <- char('\n') // skip a newline ss <- many(prof(n + 2)) // recursively read more at indent + 2 } yield Fix(ProfF(name, year, ss))
scala> prof(0).parseOnly(data).optionres7: Option[Fix[ProfF]] = Some(Fix(ProfF(Simeon Denis Poisson, 1800, «1»)))
toString
for Fix
isn't that great so I'll call a utility method that prints out the tree. I'm not going to show it to you but it's in the example code.scala> prof(0).parseOnly(data).option.foreach(drawFix)ProfF(Simeon Denis Poisson, 1800, «1») ProfF(Gustav Peter Lejeune Dirichlet, 1827, «1») ProfF(Rudolf Otto Sigismund Lipschitz, 1853, «1») ProfF(C. Felix (Christian) Klein, 1868, «2») ProfF(William Edward Story, 1875, «1») ProfF(Solomon Lefschetz, 1911, «1») ProfF(Albert William Tucker, 1932, «1») ProfF(Marvin Lee Minsky, 1954, «1») ProfF(Gerald Jay Sussman, 1973, «1») ProfF(Guy Lewis Steele, 1980, «1») ProfF(Philip Lee Wadler, 1984, «0») ProfF(C. L. Ferdinand (Carl Louis) Lindemann, 1873, «1») ProfF(David Hilbert, 1885, «3») ProfF(Wilhelm Ackermann, 1925, «0») ProfF(Haskell Curry, 1930, «0») ProfF(Hermann Weyl, 1908, «1») ProfF(Saunders Mac Lane, 1934, «2») ProfF(Steven Awodey, 1997, «0») ProfF(William Howard, 1956, «0»)
Cofree
.def prof(n: Int): Parser[Fix[ProfF]] = for { _ <- manyN(n, char(' ')) // skip 'n' spaces name <- stringOf(notChar(',')) // read up to a comma _ <- token(char(',')) // skip comma and following space year <- int // read an int _ <- char('\n') // skip a newline ss <- many(prof(n + 2)) // recursively read more at indent + 2 } yield Fix(ProfF(name, year, ss))
Fix
parser ...def posProf(n: Int): Parser[Cofree[ProfF, (Int, Int)]] = for { p0 <- pos _ <- manyN(n, char(' ')) // skip 'n' spaces name <- stringOf(notChar(',')) // read up to a comma _ <- token(char(',')) // skip comma and following space year <- int // read an int _ <- char('\n') // skip a newline ss <- many(posProf(n + 2)) // recursively read more at indent + 2 p1 <- pos } yield Cofree((p0, p1), ProfF(name, year, ss))
Cofree
, and what we're doing here is annotating each ProfF
with the starting and ending parse positions.def posProf(n: Int): Parser[Cofree[ProfF, (Int, Int)]] = for { p0 <- pos _ <- manyN(n, char(' ')) // skip 'n' spaces name <- stringOf(notChar(',')) // read up to a comma _ <- token(char(',')) // skip comma and following space year <- int // read an int _ <- char('\n') // skip a newline ss <- many(posProf(n + 2)) // recursively read more at indent + 2 p1 <- pos } yield Cofree((p0, p1), ProfF(name, year, ss))
scala> posProf(0).parseOnly(data).optionres9: Option[Cofree[ProfF,(Int, Int)]] = Some(Cofree((0,713),ProfF(Simeon Denis Poisson, 1800, «1»)))
toString
scala> posProf(0).parseOnly(data).option.foreach(drawCofree)(0,713) :< ProfF(Simeon Denis Poisson, 1800, «1») (27,713) :< ProfF(Gustav Peter Lejeune Dirichlet, 1827, «1») (66,713) :< ProfF(Rudolf Otto Sigismund Lipschitz, 1853, «1») (108,713) :< ProfF(C. Felix (Christian) Klein, 1868, «2») (147,420) :< ProfF(William Edward Story, 1875, «1») (182,420) :< ProfF(Solomon Lefschetz, 1911, «1») (216,420) :< ProfF(Albert William Tucker, 1932, «1») (256,420) :< ProfF(Marvin Lee Minsky, 1954, «1») (294,420) :< ProfF(Gerald Jay Sussman, 1973, «1») (335,420) :< ProfF(Guy Lewis Steele, 1980, «1») (376,420) :< ProfF(Philip Lee Wadler, 1984, «0») (420,713) :< ProfF(C. L. Ferdinand (Carl Louis) Lindemann, 1873, «1») (473,713) :< ProfF(David Hilbert, 1885, «3») (503,539) :< ProfF(Wilhelm Ackermann, 1925, «0») (539,571) :< ProfF(Haskell Curry, 1930, «0») (571,713) :< ProfF(Hermann Weyl, 1908, «1») (602,713) :< ProfF(Saunders Mac Lane, 1934, «2») (640,676) :< ProfF(Steven Awodey, 1997, «0») (676,713) :< ProfF(William Howard, 1956, «0»)
Cofree
was for database IDs but we can use that slot for anything. Without any changes to our API we now have a representation with source positions.And you can see how this can be really useful for something like a computer language, because your recursive data type is an AST that you might want to annotate with source positions, types, strictness analysis, any number of things, and by encoding your data types this way you get that ability for free, which is really nice.
Ok, so back to our database problem.
case class ProfF[A](name: String, year: Int, students: List[A])
ProfF
is a functor. This means we can map over it.
implicit val PersonFunctor: Functor[ProfF] = new Functor[ProfF] { def map[A, B](fa: ProfF[A])(f: A => B): ProfF[B] = fa.copy(students = fa.students.map(f)) }
Thus.
scala> val ps = ProfF("Bob", 1976, List("foo", "bar"))ps: ProfF[String] = ProfF(Bob,1976,List(foo, bar))scala> ps.map(s => s.length)res11: ProfF[Int] = ProfF(Bob,1976,List(3, 3))
.map
on List
and we're done.case class ProfF[A](name: String, year: Int, students: List[A])
ProfF
is a traversable functor. This means we can sequence it.
implicit val PersonTraverse: Traverse[ProfF] = new Traverse[ProfF] { def traverseImpl[G[_]: Applicative, A, B](fa: ProfF[A])(f: A => G[B]): G[ProfF[B]] = fa.students.traverse(f).map(ss => fa.copy(students = ss)) }
Thus.
scala> val p = ProfF("Bob", 1975, List(Option(1), Option(2)))p: ProfF[Option[Int]] = ProfF(Bob,1975,List(Some(1), Some(2)))scala> p.sequenceres12: Option[ProfF[Int]] = Some(ProfF(Bob,1975,List(1, 2)))
ProfF
is also a traversable functor. This means we can turn a ProfF[F[A]]
into a F[ProfF[A]]
if F
is an applicative functor. We can flip the type constructors, which is what the example illustrates. Look at the types.traverse
on List
for most of the work because List
is also a traversable functor.Because "map and then sequence" is so common, we also have traverse
which does them in one step. You can define one in terms of the other but they have this relationship:
fa.map(f).sequence <~> fa.traverse(f) // (1) definition of traverse
And we can find another identity by equational reasoning.
fa <~> fa.map(identity) // (2) the functor lawfa.sequence <~> fa.map(identity).sequence // by (2) abovefa.sequence <~> fa.traverse(identity) // by (1) above
So when you're working with traversable functors it's nice to know both of those substitutions.
<~>
we mean "the same thing" ... you can freely substitute one for the other.Doobie is a pure functional (i.e., side-effect free) JDBC library for Scala. See tpolecat/doobie
for doc, presentations, etc.
// a transactor abstracts over connection pools and io-effect typesval xa = DriverManagerTransactor[IO]("org.h2.Driver", "jdbc:h2:mem:test;DB_CLOSE_DELAY=-1", "sa", "")// a program to create the schemaval create: ConnectionIO[Int] = sql""" CREATE TABLE prof ( id INTEGER IDENTITY, parent INTEGER NULL, name VARCHAR NOT NULL, year INTEGER NOT NULL, FOREIGN KEY(parent) REFERENCES prof(id) ); """.update.run
Let's init the database.
scala> create.transact(xa).unsafePerformIOres16: Int = 0scala> sql"select id from prof".query[Int].list.transact(xa).unsafePerformIOres17: List[Int] = List()
IO
or Task
and run it ("at the end of the world" as we say).def insertNode(op: Option[Int], p: ProfF[_]): ConnectionIO[Int] = sql""" INSERT INTO prof (parent, name, year) VALUES ($op, ${p.name}, ${p.year}) """.update.withUniqueGeneratedKeys("id")
prof
table and yields the generated id.def insertNode(op: Option[Int], p: ProfF[_]): ConnectionIO[Int] = sql""" INSERT INTO prof (parent, name, year) VALUES ($op, ${p.name}, ${p.year}) """.update.withUniqueGeneratedKeys("id")def insertTree(fp: Fix[ProfF], op: Option[Int]): ConnectionIO[Cofree[ProfF, Int]] = for { h <- insertNode(op, fp.unfix) // ConnectionIO[Int] t <- fp.unfix // ProfF[Fix[ProfF]] .map(insertTree(_, Some(h))) // ProfF[ConnectionIO[Cofree[ProfF, Int]]] .sequence // ConnectionIO[ProfF[Cofree[ProfF, Int]]] } yield Cofree(h, t)
Fix[ProfF]
into the database, and yield another tree with the same structure but annotated with database ids. Which is what we wanted to do..map
and then .sequence
is .traverse
so let's simplify thatdef insertNode(op: Option[Int], p: ProfF[_]): ConnectionIO[Int] = sql""" INSERT INTO prof (parent, name, year) VALUES ($op, ${p.name}, ${p.year}) """.update.withUniqueGeneratedKeys("id")def insertTree(fp: Fix[ProfF], op: Option[Int]): ConnectionIO[Cofree[ProfF, Int]] = for { h <- insertNode(op, fp.unfix) t <- fp.unfix .traverse(insertTree(_, Some(h))) // same as map + sequence } yield Cofree(h, t)
def insertNode(op: Option[Int], p: ProfF[_]): ConnectionIO[Int] = sql""" INSERT INTO prof (parent, name, year) VALUES ($op, ${p.name}, ${p.year}) """.update.withUniqueGeneratedKeys("id")def insertTree(fp: Fix[ProfF], op: Option[Int]): ConnectionIO[Cofree[ProfF, Int]] = for { h <- insertNode(op, fp.unfix) t <- fp.unfix.traverse(insertTree(_, Some(h))) } yield Cofree(h, t)
insertTree
operation can be generalized but the Option
type makes it a little messy so we're just going to leave it as-is.scala> val p = prof(0).parseOnly(data).option.get // yolop: Fix[ProfF] = Fix(ProfF(Simeon Denis Poisson, 1800, «1»))scala> val io = insertTree(p, None).transact(xa).flatMap(c => ioDrawCofree(c))io: scalaz.effect.IO[Unit] = scalaz.effect.IOFunctions$$anon$6@57653a55scala> io.unsafePerformIO1 :< ProfF(Simeon Denis Poisson, 1800, «1») 2 :< ProfF(Gustav Peter Lejeune Dirichlet, 1827, «1») 3 :< ProfF(Rudolf Otto Sigismund Lipschitz, 1853, «1») 4 :< ProfF(C. Felix (Christian) Klein, 1868, «2») 5 :< ProfF(William Edward Story, 1875, «1») 6 :< ProfF(Solomon Lefschetz, 1911, «1») 7 :< ProfF(Albert William Tucker, 1932, «1») 8 :< ProfF(Marvin Lee Minsky, 1954, «1») 9 :< ProfF(Gerald Jay Sussman, 1973, «1») 10 :< ProfF(Guy Lewis Steele, 1980, «1») 11 :< ProfF(Philip Lee Wadler, 1984, «0») 12 :< ProfF(C. L. Ferdinand (Carl Louis) Lindemann, 1873, «1») 13 :< ProfF(David Hilbert, 1885, «3») 14 :< ProfF(Wilhelm Ackermann, 1925, «0») 15 :< ProfF(Haskell Curry, 1930, «0») 16 :< ProfF(Hermann Weyl, 1908, «1») 17 :< ProfF(Saunders Mac Lane, 1934, «2») 18 :< ProfF(Steven Awodey, 1997, «0») 19 :< ProfF(William Howard, 1956, «0»)
ioDrawCofree
which is the same printing code, just in IO
so it doesn't side-effect.scala> io.unsafePerformIO20 :< ProfF(Simeon Denis Poisson, 1800, «1») 21 :< ProfF(Gustav Peter Lejeune Dirichlet, 1827, «1») 22 :< ProfF(Rudolf Otto Sigismund Lipschitz, 1853, «1») 23 :< ProfF(C. Felix (Christian) Klein, 1868, «2») 24 :< ProfF(William Edward Story, 1875, «1») 25 :< ProfF(Solomon Lefschetz, 1911, «1») 26 :< ProfF(Albert William Tucker, 1932, «1») 27 :< ProfF(Marvin Lee Minsky, 1954, «1») 28 :< ProfF(Gerald Jay Sussman, 1973, «1») 29 :< ProfF(Guy Lewis Steele, 1980, «1») 30 :< ProfF(Philip Lee Wadler, 1984, «0») 31 :< ProfF(C. L. Ferdinand (Carl Louis) Lindemann, 1873, «1») 32 :< ProfF(David Hilbert, 1885, «3») 33 :< ProfF(Wilhelm Ackermann, 1925, «0») 34 :< ProfF(Haskell Curry, 1930, «0») 35 :< ProfF(Hermann Weyl, 1908, «1») 36 :< ProfF(Saunders Mac Lane, 1934, «2») 37 :< ProfF(Steven Awodey, 1997, «0») 38 :< ProfF(William Howard, 1956, «0»)
def readNode(id: Int): ConnectionIO[ProfF[Int]] = for { d <- sql"SELECT name, year FROM prof WHERE id = $id".query[(String, Int)].unique ss <- sql"SELECT id FROM prof WHERE parent = $id".query[Int].list } yield ProfF(d._1, d._2, ss)
ProfF[Inf]
... no what does that mean? It's a ProfF
whose children are database ids. So instead of object references we have database references.def readNode(id: Int): ConnectionIO[ProfF[Int]] = for { d <- sql"SELECT name, year FROM prof WHERE id = $id".query[(String, Int)].unique ss <- sql"SELECT id FROM prof WHERE parent = $id".query[Int].list } yield ProfF(d._1, d._2, ss)def readTree(id: Int): ConnectionIO[Cofree[ProfF, Int]] = readNode(id).flatMap { pi => pi.map(readTree) // ProfF[ConnectionIO[Cofree[ProfF, Int]]] .sequence // ConnectionIO[ProfF[Cofree[ProfF, Int]]] .map(Cofree(id, _)) // ConnectionIO[Cofree[ProfF, Int]] }
.map
and then .sequence
is ...def readNode(id: Int): ConnectionIO[ProfF[Int]] = for { d <- sql"SELECT name, year FROM prof WHERE id = $id".query[(String, Int)].unique ss <- sql"SELECT id FROM prof WHERE parent = $id".query[Int].list } yield ProfF(d._1, d._2, ss)def readTree(id: Int): ConnectionIO[Cofree[ProfF, Int]] = readNode(id).flatMap { pi => pi.traverse(readTree) .map(Cofree(id, _)) }
def readNode(id: Int): ConnectionIO[ProfF[Int]] = for { d <- sql"SELECT name, year FROM prof WHERE id = $id".query[(String, Int)].unique ss <- sql"SELECT id FROM prof WHERE parent = $id".query[Int].list } yield ProfF(d._1, d._2, ss)def readTree(id: Int): ConnectionIO[Cofree[ProfF, Int]] = readNode(id).flatMap(_.traverse(readTree).map(Cofree(id, _)))
readTree
method more closely and see if we can generalize it.// our original method for reading a treedef readTree(id: Int): ConnectionIO[Cofree[ProfF, Int]] = readNode(id).flatMap(_.traverse(readTree).map(Cofree(id, _)))
readNode
.// factor out the function we're callingdef readTree(id: Int)(f: Int => ConnectionIO[ProfF[Int]]): ConnectionIO[Cofree[ProfF, Int]] = f(id).flatMap(_.traverse(readTree(_)(f)).map(Cofree(id, _)))
f
gives us a ConnectionIO
but all we're doing with it is calling .flatMap
and then .map
, so it should work with any monad. Let's factor that out.// factor out the monaddef readTree[M[_]: Monad](id: Int)(f: Int => M[ProfF[Int]]): M[Cofree[ProfF, Int]] = f(id).flatMap(_.traverse(readTree(_)(f)).map(Cofree(id, _)))
M
of ProfF[Int]
but the only thing we're doing with the ProfF
it is calling .traverse
, so it should work with any traversable functor. Let's factor that out.// factor out the traversable functordef readTree[M[_]: Monad, F[_]: Traverse](id: Int)(f: Int => M[F[Int]]): M[Cofree[F, Int]] = f(id).flatMap(_.traverse(readTree(_)(f)).map(Cofree(id, _)))
Int
but passing it as an argument so let's factor that out too.// factor out the Intdef readTree[M[_]: Monad, F[_]: Traverse, A](a: A)(f: A => M[F[A]]): M[Cofree[F, A]] = f(a).flatMap(_.traverse(readTree(_)(f)).map(Cofree(a, _)))
// we now have a generic monadic unfold into cofreedef unfoldCM[M[_]: Monad, F[_]: Traverse, A](a: A)(f: A => M[F[A]]): M[Cofree[F, A]] = f(a).flatMap(_.traverse(unfoldCM(_)(f)).map(Cofree(a, _)))
A
's in the F
, forever, or until there are no more A
s; in this case it means we're at the leaves of the tree.// we now have a generic monadic unfold into cofreedef unfoldCM[M[_]: Monad, F[_]: Traverse, A](a: A)(f: A => M[F[A]]): M[Cofree[F, A]] = f(a).flatMap(_.traverse(unfoldCM(_)(f)).map(Cofree(a, _)))// and we can define readTree in terms of itdef readTree(id: Int): ConnectionIO[Cofree[ProfF, Int]] = unfoldCM(id)(readNode)
readTree
method is trivial.Let's read Hilbert's sub-tree (id = 32).
scala> val io = readTree(32).transact(xa).flatMap(c => ioDrawCofree(c))io: scalaz.effect.IO[Unit] = scalaz.effect.IOFunctions$$anon$6@5ff635a8scala> io.unsafePerformIO32 :< ProfF(David Hilbert, 1885, «3») 33 :< ProfF(Wilhelm Ackermann, 1925, «0») 34 :< ProfF(Haskell Curry, 1930, «0») 35 :< ProfF(Hermann Weyl, 1908, «1») 36 :< ProfF(Saunders Mac Lane, 1934, «2») 37 :< ProfF(Steven Awodey, 1997, «0») 38 :< ProfF(William Howard, 1956, «0»)
Fix
and Cofree
popped out of our model naturally just by pushing a little bit; it's not a contrived example, the question of what to do with database IDs is a real thing we think about.ProfF
.And hopefully you all survived. And if not I have bad news for you because Greg Pfiel is up next and he's going to be talking about using recursion schemes in a much more general and more powerful way.
sooooo, that's it.
Code and slides at tpolecat/cofree
on GitHub
Ok so let's look at a recursive data type.
Keyboard shortcuts
↑, ←, Pg Up, k | Go to previous slide |
↓, →, Pg Dn, Space, j | Go to next slide |
Home | Go to first slide |
End | Go to last slide |
b / m / f | Toggle blackout / mirrored / fullscreen mode |
c | Clone slideshow |
p | Toggle presenter mode |
t | Restart the presentation timer |
?, h | Toggle this help |
Esc | Back to slideshow |