Tree Folds

In Section 3.5 of Functional Programming in Scala, trees were introduced as an example of an algebraic data type. One of the exercises involved implementing functions to compute the size, maximum, and depth of a tree using folding.

I came up with the following implementation. f was the function to be run when merging internal nodes, and g would be the usual fold function that would be run on each visit to a child node, accumulating each node’s value into the accumulator.

sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]
 
object Tree {
  def fold[A,B](tree: Tree[A], b: B)(f: (B, B) => B)(g: (A, B) => B): B = tree match {
    case Leaf(a) => g(a, b)
    case Branch(left, right) => f(fold(left, b)(f)(g), fold(right, b)(f)(g))
  }
  def sizeFold[A](tree: Tree[A]): Int =
    fold(tree, 0)(_ + _ + 1)((_, _) => 1)
  def maximumFold(tree: Tree[Int]): Int =
    fold(tree, Int.MinValue)(_ max _)(_ max _)
  def depthFold[A](tree: Tree[A]): Int =
    fold(tree, 0)((x,y) => (x max y) + 1)((_, _) => 0)
}

In Section 10.5, trees were revisited in the context of monoids, this time involving the implementation an Foldable[Tree] instance. I noticed how the type arguments for Foldable didn’t have an equivalent of f for merging the internal nodes, and wondered if it was still possible to implement the three functions above with Foldable[Tree]. I made it as far as size and maximum, but was stuck at depth. Since Foldable seems to only care about the leaves of the tree, was it even possible to tell what the depth of the tree was?

trait Monoid[A] {
  def op(a: A, b: A): A
  def zero: A
}
 
trait Foldable[F[_]] {
  def foldRight[A,B](as: F[A])(z: B)(f: (A,B) => B): B
  def foldLeft[A,B](as: F[A])(z: B)(f: (B,A) => B): B
  def foldMap[A,B](as: F[A])(f: A => B)(mb: Monoid[B]): B
  def concatenate[A](as: F[A])(m: Monoid[A]): A =
    foldLeft(as)(m.zero)(m.op)
}
 
object FoldableTree extends Foldable[Tree] {
  def foldRight[A,B](as: Tree[A])(z: B)(f: (A,B) => B): B = as match {
    case Leaf(a) => f(a,z)
    case Branch(x,y) =>
      foldRight(y)(foldRight(x)(z)(f))(f)
  }
  def foldLeft[A,B](as: Tree[A])(z: B)(f: (B,A) => B): B = as match {
    case Leaf(a) => f(z,a)
    case Branch(x,y) =>
      foldLeft(y)(foldLeft(x)(z)(f))(f)
  }
  def foldMap[A,B](as: Tree[A])(f: A => B)(mb: Monoid[B]): B = as match {
    case Leaf(a) => f(a)
    case Branch(x,y) => mb.op(foldMap(x)(f)(mb), foldMap(y)(f)(mb))
  }
 
  def sizeFold[A](as: Tree[A]): Int =
    foldRight(as)(0)((a, b) => b + 1)
 
  def maximumFold(as: Tree[Int]): Int =
    foldRight(as)(Int.MinValue)(_ max _)
}

Turns out, it really isn’t possible, at least not with just Foldable. To quote this great Stack Overflow answer almost verbatim:

To answer the first question: Data.Foldable is not enough to compute the depth of the tree. The minimum complete definition of Foldable is foldr, which always has the following semantics…

In other words, a Foldable instance is fully characterized by how it behaves on a list projection of the input (ie toList), which will throw away the depth information of a tree.

Other ways of verifying this idea involve the fact that Foldable depends on a monoid instance which has to be associative or the fact that the various fold functions see the elements one by one in some particular order with no other information, which necessarily throws out the actual tree structure. (There has to be more than one tree with the same set of elements in the same relative order.)