16 people like it.

# Inline factorial samples with fix point

While reading Tomas Petricek's master thesis, came across FIX operator implementation. Decided to experiment with various implementations of factorial.

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: ``` ``````let rec fix f x = f (fix f) x let inline factf1 n = let loop = fix (fun f x -> if x<=LanguagePrimitives.GenericOne then LanguagePrimitives.GenericOne else x * (f (x - LanguagePrimitives.GenericOne))) loop n let rec fix2 f a b = f (fix2 f) a b let inline factf2 n = let loop = fix2 (fun f acc n -> if n<=LanguagePrimitives.GenericOne then acc else f (n*acc) (n-LanguagePrimitives.GenericOne)) loop LanguagePrimitives.GenericOne n let inline facti n = let rec loop acc n = if n<=LanguagePrimitives.GenericOne then acc else loop (n*acc) (n-LanguagePrimitives.GenericOne) loop LanguagePrimitives.GenericOne n (* It seems there's little difference performance-wise. Still, tail-recursive implementation is faster than CPS. > [1I..2000I] |> List.iter (factf1 >> ignore);; Real: 00:00:04.603, CPU: 00:00:04.586, GC gen0: 480, gen1: 1, gen2: 0 val it : unit = () > [1I..2000I] |> List.iter (factf2 >> ignore);; Real: 00:00:04.868, CPU: 00:00:04.851, GC gen0: 556, gen1: 1, gen2: 0 val it : unit = () > [1I..2000I] |> List.iter (facti >> ignore);; Real: 00:00:04.043, CPU: 00:00:04.024, GC gen0: 548, gen1: 0, gen2: 0 val it : unit = () > *) ``````
val fix : f:(('a -> 'b) -> 'a -> 'b) -> x:'a -> 'b

Full name: Script.fix
val f : (('a -> 'b) -> 'a -> 'b)
val x : 'a
val factf1 : n:'a -> 'b (requires member ( * ) and member get_One and member ( - ) and comparison and member get_One and member get_One)

Full name: Script.factf1
val n : 'a (requires member ( * ) and member get_One and member ( - ) and comparison and member get_One and member get_One)
val loop : ('a -> 'b) (requires member ( * ) and member get_One and member ( - ) and comparison and member get_One and member get_One)
val f : ('a -> 'b) (requires member ( * ) and member get_One and member ( - ) and comparison and member get_One and member get_One)
val x : 'a (requires member ( * ) and member get_One and member ( - ) and comparison and member get_One and member get_One)
module LanguagePrimitives

from Microsoft.FSharp.Core
val GenericOne<'T (requires member get_One)> : 'T (requires member get_One)

Full name: Microsoft.FSharp.Core.LanguagePrimitives.GenericOne
val fix2 : f:(('a -> 'b -> 'c) -> 'a -> 'b -> 'c) -> a:'a -> b:'b -> 'c

Full name: Script.fix2
val f : (('a -> 'b -> 'c) -> 'a -> 'b -> 'c)
val a : 'a
val b : 'b
val factf2 : n:'a -> 'b (requires member ( * ) and member get_One and member ( - ) and comparison and member get_One and member get_One)

Full name: Script.factf2
val loop : ('b -> 'a -> 'b) (requires member get_One and member ( * ) and member get_One and member ( - ) and comparison and member get_One)
val f : ('b -> 'a -> 'b) (requires member get_One and member ( * ) and member get_One and member ( - ) and comparison and member get_One)
val acc : 'b (requires member get_One and member ( * ) and member get_One and member ( - ) and comparison and member get_One)
val facti : n:'a -> 'b (requires member ( * ) and member get_One and member ( - ) and comparison and member get_One and member get_One)

Full name: Script.facti