Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Factorial using a Hylomorphism in F#
type List<'i,'r> = Nil | Cons of 'i*'r
type FixList<'i> = FixList of List<'i,FixList<'i>>
let rec fmap (f : 'a -> 'b) (l : List<'i,'a>) : List<'i,'b> =
match l with
| Nil -> Nil
| Cons (x, tail) -> Cons (x, f tail)
// you can express hylo directly without using ana and cata (by either following the
// types or insert/replace the definitions of ana/cata)
// if you do this in a point-free style (inj >> fmap (hylo inter inj) >> inter) it
// will fail with an StackOverflow-Exception
// I falsley attributed that to strict-evaluation itself, which turned out to be wrong
// as @giuliohome_2017 remarked the shorter version should indeed work - and so it does,
// once you abandon point-free style
let rec hylo (inter : List<'i,'a> -> 'a) (inj : 'a -> List<'i,'a>) (x : 'a) =
inj x
|> fmap (hylo inter inj)
|> inter
let hyloFact =
let upTo n = if n <= 0 then Nil else Cons (n, n-1)
let prod = function Nil -> 1 | Cons (n,acc) -> n * acc
hylo prod upTo
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.