How does the Scala Option add up catamorphism?

Question

The answer to this suggests that the fold method in Option in Scala is catastrophic. From Wikipedia, catamophism is “the only homomorphism from the original algebra to some other algebra. This concept applies to functional programming as folds,” so this is true, but it leads me to the original algebra as the source object in the F-algebra category.

So, if addition to Option is really Catamanism, then there must be some F functor to create a category of F-algebras, where Option will be the original object. I can’t understand what this functor will be like.

For lists of type A 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 means that a list of type A is either an empty list ( 1 ) or ( + ) a pair ( * ) A and a List[A] . But the option is not recursive. Option[A] will be just 1 + A (Nothing or A ). So I don’t see where the functor works.

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

In the corresponding note, if it is not a catamorphism, it probably should not be called a fold, as this leads to some confusion .

Answer 1

Well, the comments are on the right track. I'm just a beginner, so I probably have some misconceptions. Yes, the whole point is to model recursive types, but I think that nothing excludes the "non-recursive" F-algebra. Since the original algebra is the solution of the least fixed point for the equation X ~ = F X. In the case of Options, the solution is trivial, since there is no recursion :)

Other examples of source algebras:

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

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

Similar:

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

Justifying the existence of a "persistent" functor is pretty simple, how do you imagine a node tree? In fact, for algebraic models of (simple) recursive data types, you only need the following functors:

• U (Unit, represents empty)
• K (constant, fix value)
• i (Identity, indicate a recursive position)
• * (product)
• + (coproduct)

Good link I found Functional General Programming

Shameless plugin: I play with these concepts in scala-reggen code