7

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.

Community
  • 1
  • 1
Patrick
  • 201
  • 1
  • 6
  • What's the basis for your assumption that `F` _has_ to be recursive? Lots of algebraic data types aren't. In any case you could always "cheat" and write something like `F[X] = 1 + Const A X`. – Travis Brown May 18 '14 at 18:45
  • Is `F[X] = 1 + Const A X` the same as the functor as `F[X] = 1 + A`? (The functor that sends every type to Option[A].) I suppose that works, but it is so trivial that I assumed there would be more going on. Under this F, any F-algebra is just a type B with a map from Option[A] to B. An then the initialness just says given a type B and a map from Option[A] to B, there exists a unique map from Option[A] to B. http://homepages.inf.ed.ac.uk/wadler/papers/free-rectypes/free-rectypes.txt (linked from the wikipedia) also implies the point of initial F-algebras is for recursive data types. – Patrick May 18 '14 at 19:08
  • 2
    Furthermore, If you allow constant Functors, then for any type `T`, you can consider the functor `F[X] = T`. Then an F-algebra is simply a type `B` together with a map `g` from `T` to `B`. `T` is immediately the initial algebra, and the catamoprhism is simply applying `g` to objects of type `T`. Which seems to be what is happening, since Option[A] is a coproduct of `A` and `Nothing`, and map from `Option[A]` to `B` splits into a map from `A` to `B` and a map from `Nothing` to B, which fits with the type signature of `fold` on `Option`. – Patrick May 19 '14 at 13:59

1 Answers1

2

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

GClaramunt
  • 3,148
  • 1
  • 21
  • 35