What's the relation of fold on Option, Either etc and fold on Traversable?

Question

Scalaz provides a method named fold for various ADTs such as Boolean, Option[_], Validation[_, _], Either[_, _] etc. This method basically takes functions corresponding to all possible cases for that given ADT. In other words, a pattern match shown below:

x match {
  case Case1(a, b, c) => f(a, b, c)
  case Case2(a, b) => g(a, b)
  .
  .
  case CaseN => z
}

is equivalent to:

x.fold(f, g, ..., z)

Some examples:

scala> (9 == 8).fold("foo", "bar")
res0: java.lang.String = bar

scala> 5.some.fold(2 *, 2)
res1: Int = 10

scala> 5.left[String].fold(2 +, "[" +)
res2: Any = 7

scala> 5.fail[String].fold(2 +, "[" +)
res6: Any = 7

At the same time, there is an operation with the same name for the Traversable[_] types, which traverses over the collection performing certain operation on its elements, and accumulating the result value. For example,

scala> List(2, 90, 11).foldLeft("Contents: ")(_ + _.toString + " ")
res9: java.lang.String = "Contents: 2 90 11 "

scala> List(2, 90, 11).fold(0)(_ + _)
res10: Int = 103

scala> List(2, 90, 11).fold(1)(_ * _)
res11: Int = 1980

Why are these two operations identified with the same name - fold/catamorphism? I fail to see any similarities/relation between the two. What am I missing?

Folse

Answer 1

I think the problem you are having is that you see these things based on their implementation, not their types. Consider this simple representation of types:

List[A] = Nil 
        | Cons head: A tail: List[A]

Option[A] = None
          | Some el: A

Now, let's consider Option's fold:

fold[B] = (noneCase: => B, someCase: A => B) => B

So, on Option, it reduces every possible case to some value in B, and return that. Now, let's see the same thing for List:

fold[B] = (nilCase: => B, consCase: (A, List[A]) => B) => B

Note, however, that we have a recursive call there, on List[A]. We have to fold that somehow, but we know fold[B] on a List[A] will always return B, so we can rewrite it like this:

fold[B] = (nilCase: => B, consCase: (A, B) => B) => B

In other words, we replaced List[A] by B, because folding it will always return a B, given the type signature of fold. Now, let's see Scala's (use case) type signature for foldRight:

foldRight[B](z: B)(f: (A, B) ⇒ B): B

Say, does that remind you of something?

Karmenkarna

Oh, so it has to be applied recursively! Makes sense, thanks. – Folse

The Wikipedia page on "catamorphism" says, "In functional programming, a catamorphism is a generalization of the folds on lists known from functional programming to arbitrary algebraic data types that can be described as initial algebras." It then points to Erik Meijer's paper “Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire”. I think I should read that paper to get a better understanding of the topic. – Folse

@missingfaktor, at the end of the wikipedia page there is 6 part blog on catamorphism that seems very accessible. I'm reading it right now. It's F# but I'm sure that won't be a problem for you. – Seemly

@huynhjl: Oh, I initially missed that. Thanks for pointing me to it! – Folse

Answer 2

If you think of "folding" as "condensing all the values in a container through an operation, with a seed value", and you think of an Option as a container that can can have at most one value, then this starts to make sense.

In fact, foldLeft has the same signature and gives you exactly the same results if you use it on an empty list vs None, and on a list with only one element vs Some:

scala> val opt : Option[Int] = Some(10)
opt: Option[Int] = Some(10)

scala> val lst : List[Int] = List(10)
lst: List[Int] = List(10)

scala> opt.foldLeft(1)((a, b) => a + b)
res11: Int = 11

scala> lst.foldLeft(1)((a, b) => a + b)
res12: Int = 11

fold is also defined on both List and Option in the Scala standard library, with the same signature (I believe they both inherit it from a trait, in fact). And again, you get the same results on a singleton list as on Some:

scala> opt.fold(1)((a, b) => a * b)
res25: Int = 10

scala> lst.fold(1)((a, b) => a * b)
res26: Int = 10

I'm not 100% sure about the fold from Scalaz on Option/Either/etc, you raise a good point there. It seems to have quite a different signature and operation from the "folding" I'm used to.

Samaniego