16 people like it.
Like the snippet!

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

Raw view Test code New version

More information

Link:	http://fssnip.net/1U
Posted:	13 years ago
Author:	Dmitri Pavlenkov
Tags:	factorial , recursive , inline , fix , languageprimitives