Catamorphism in F#

Question

I'm reading the wikipedia article about catamorphisms and for the moment I was able to reproduce the Haskell examples in F# except for this part :

type Algebra f a = f a -> a -- the generic f-algebras

newtype Fix f = Iso { invIso :: f (Fix f) } -- gives us the initial algebra for the functor f

cata :: Functor f => Algebra f a -> (Fix f -> a) -- catamorphism from Fix f to a
cata alg = alg . fmap (cata alg) . invIso -- note that invIso and alg map in opposite directions

Is this possible to do in F#?

Disservice

You can define it for a particular datatype (e.g. List.fold) but not generically as in your quoted example. – Impale

This needs higher kinds: roughly, the ability to define T f = f Bool, where f : *->*. You can do that in Haskell or Scala, but I don't know if F# allows that. – Latona

@chi: It doesn't, outside of a defunctionalization-based encoding. – Augite

Answer 1

If you're thinking of expressing truly generic folds over arbitrary container types, a'la recursion schemes, directly within the F# (or CLR for that matter) type system - you're out of luck. Too much of the required machinery is missing in the language - most crucially higher kinded types.

HKT's can however be encoded in F# using a technique called defunctionalization. There is an F# library based on the concepts from this paper - Higher. In fact, it already implements fix, cata/ana/hylomorphisms and algebras as proofs of concept. I don't have a good gauge of how well that works though, both in terms of performance and ease of use.

Other than that, you can implement folds specialized for your containers by hand, obviating the need for HKT's. There's a classic by now series of blog posts on implementing catamorphisms here. It's well worth reading - beside folds it also goes in-depth into programming in continuation-passing style.

Augite

Thank you. The material looks very nice and I will go through it. Thanks. – Disservice