Tree Folds

August 02, 2020

In Sec­tion 3.5 of Func­tion­al Pro­gram­ming in Scala, trees were intro­duced as an exam­ple of an alge­bra­ic data type. One of the exer­cis­es involved imple­ment­ing func­tions to com­pute the size, max­i­mum, and depth of a tree using fold­ing.

I came up with the fol­low­ing imple­men­ta­tion. f was the func­tion to be run when merg­ing inter­nal nodes, and g would be the usual fold func­tion that would be run on each visit to a child node, accu­mu­lat­ing each node’s value into the accu­mu­la­tor.

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 Sec­tion 10.5, trees were revis­it­ed in the con­text of monoids, this time involv­ing the imple­men­ta­tion an Foldable[Tree] instance. I noticed how the type argu­ments for Foldable didn’t have an equiv­a­lent of f for merg­ing the inter­nal nodes, and won­dered if it was still pos­si­ble to imple­ment the three func­tions 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 pos­si­ble 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 pos­si­ble, at least not with just Foldable. To quote this great Stack Over­flow answer almost ver­ba­tim:

To answer the first ques­tion: Data.Fold­able is not enough to com­pute the depth of the tree. The min­i­mum com­plete def­i­n­i­tion of Fold­able is foldr, which always has the fol­low­ing seman­tics…

In other words, a Fold­able instance is fully char­ac­ter­ized by how it behaves on a list pro­jec­tion of the input (ie toList), which will throw away the depth infor­ma­tion of a tree.

Other ways of ver­i­fy­ing this idea involve the fact that Fold­able depends on a monoid instance which has to be asso­cia­tive or the fact that the var­i­ous fold func­tions see the ele­ments one by one in some par­tic­u­lar order with no other infor­ma­tion, which nec­es­sar­i­ly throws out the actual tree struc­ture. (There has to be more than one tree with the same set of ele­ments in the same rel­a­tive order.)