scalacategory-theoryscala-optioncatamorphismrecursion-schemes# In what way is Scala's Option fold a catamorphism?

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.

Solution

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

- Spark scala Dataframe : How can i apply custom type to an existing dataframe?
- In Akka Typed Event Sourcing is it common to use a single db (the same event journal) for multiple typed persistent entities?
- How to setup and run scala-spark in intellij?
- Fastparse runs out of memory for simple rules
- Scala test eventually configuration for all implementations?
- Haskell do-notation has no equivalent for-comprehension in Scala?
- Check if a key exists in play.api.libs.json.Json
- Akka Source from Iterator with blocking actions
- What's the difference between join and cogroup in Apache Spark
- Any workaround for JSONPATH wildcard not supported in Spark SQL
- What is "Call By Name"?
- How can I escape special symbols in scala string at runtime?
- Create FunctionK instance with anonymous function
- Can I create empty Tuple or String in Scala?
- Distinct on an array in scala returns an empty string
- Checking structural equality of pass by name parameters
- Maven package works but Intellij's build fails
- Getting java.lang.IllegalArgumentException while creating docker Image which has Gatling
- Given `() => IO[T]`, can I obtain `IO[() => T]`?
- Scala 3: Unexpected Successful Compilation when Using Variable Before Assignment
- document.write not working in html
- In ZIO how to make a Schedule which repeats tries while multiple conditions are met counting tries for each condition individually
- Match case in Scala with tail
- Play Framework SLF4J Error Wehn Starting Server
- Generate right schema and documentation with Tapir and sealed traits
- How do I enable continuations in Scala?
- Scala method does not exit after if statement
- 'tee' operation on Scala's option type?
- How to define an identity function using placeholders in Scala?
- Spark save(write) parquet only one file