Skip to content

Instantly share code, notes, and snippets.

@tonymorris
Created January 22, 2015 03:55
Show Gist options
  • Save tonymorris/0e5f0c672c3d3394baee to your computer and use it in GitHub Desktop.
Save tonymorris/0e5f0c672c3d3394baee to your computer and use it in GitHub Desktop.
Rose-tree in Scala, demonstrating comonad implementation
case class Tree[A](root: A, forest: List[Tree[A]]) {
def map[B](f: A => B): Tree[B] =
coflatMap(t => f(t.copoint))
// categorical dual to canonical "flatMap"
def coflatMap[B](f: Tree[A] => B): Tree[B] = {
import Tree.unfoldTree
unfoldTree(this, (a: Tree[A]) => (f(a), a.forest))
}
// categorical dual to canonical "flatten"
def duplicate: Tree[Tree[A]] =
coflatMap(identity)
// identity for coflatMap
def copoint: A =
root
}
object Tree {
// caution: mutual recursion
def unfoldForest[A, B](x: List[A], f: A => (B, List[A])): List[Tree[B]] =
x map (unfoldTree(_, f))
// caution: mutual recursion
def unfoldTree[A, B](x: A, f: A => (B, List[A])): Tree[B] =
f(x) match {
case (b, as) => Tree(b, unfoldForest(as, f))
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment