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

the answer this question suggests fold method on option in scala catamoprhism. wikipedia catamophism "the unique homomorphism initial algebra other algebra. concept has been applied functional programming folds". seems fair, leads me initial algebra initial object in category of f-algebras.

so if fold on option catamophism there needs functor f, create category of f-algebras option initial object. can't figure out functor be.

for lists of type a functor f f[x] = 1 + * x. makes sense because list recursive data type, if x list[a] above reads list of type a either empty list (1), or (+) pair (*) of a , list[a]. option isn't recursive. option[a] 1 + a (nothing or a). don't see functor is.

just clear realize option functor, in takes a option[a], done lists different, a fixed , functor used describe how recursively construct data type.

on related note, if not catamorphism shouldn't called fold, leads confusion.

well, comments in right track. i'm beginner have misconceptions. yes, whole point able model recursive types, think nothing precludes "non-recursive" f-algebra. since initial algebra "least fixed point" solution equation x ~= f x. in case of option, solution trivial, there's no recursion involved :)

other examples of initial algebras:

list[x] = 1 + * x represent list = nil | cons list

tree[x] = + * x * x represent tree = leaf | node tree tree

in same way:

option[x] = 1 + represent option = none | a

the justification existence of "constant" functor pretty easy, how represent tree's node? in fact, algebraically model (simple) recursive datatypes need following functors:

• u (unit, represents empty)
• k (constant, captures value)
• i (identity, represent recursive position)
• * (product)
• + (coproduct)

a reference found functional generic programming

shameless plug: i'm playing concepts in code in scala-reggen