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?

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?