-
-
Save giuliohome/d5d7c4171812e15e903ff173fb967139 to your computer and use it in GitHub Desktop.
Factorial using a Hylomorphism in F#
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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