In what way is Scala's Option fold a catamorphism?

Question

The answer to this question suggests that the fold method on Option in Scala is a catamoprhism. From the wikipedia a catamophism is "the unique homomorphism from an initial algebra into some other algebra. The concept has been applied to functional programming as folds". So that seems fair, but leads me to an initial algebra as the initial object in the category of F-algebras.

So if the fold on Option is really a catamophism there needs to be some functor F, to create the category of F-algebras where Option would be the initial object. I can't figure out what this functor would be.

For Lists of type A the functor F is F[X] = 1 + A * X. This makes sense because List is a recursive data type, so if X is List[A] then the above reads that a list of type A is either the empty list (1), or (+) a pair (*) of an A and a List[A]. But Option isn't recursive. Option[A] would just be 1 + A (Nothing or an A). So I don't see where the functor is.

Just to be clear I realize that Option is already a functor, in that it takes A to Option[A], but what is done for lists is different, the A is fixed and the functor is used to describe how to recursively construct the data type.

On a related note, if it is not a catamorphism it probably shouldn't be called a fold, as that leads to some confusion.

Answer 1

Well, the comments are in the right track. I'm just a beginner so I probably have some misconceptions. Yes, the whole point is to be able to model recursive types, but I think nothing precludes a "non-recursive" F-algebra. Since the initial algebra is the "least fixed point" solution to the equation X ~= F X. In the case of Option, the solution is trivial, as there's no recursion involved :)

Other examples of initial algebras:

List[X] = 1 + A * X to represent list = Nil | Cons a list

Tree[X] = A + A * X * X to represent tree = Leaf a | Node a tree tree

In the same way:

Option[X] = 1 + A to represent option = None | Some a

The justification for the existence of a "constant" functor is pretty easy, how do you represent a tree's node? In fact, to algebraically model (simple) recursive datatypes you need only the following functors:

• U (Unit, represents empty)
• K (Constant, captures a value)
• I (Identity, represent the recursive position)
• * (product)
• + (coproduct)

A good reference I found is Functional Generic Programming

Shameless plug: I'm playing with those concepts in code in scala-reggen