9 people like it.

GC Friendly Fixpoint

Fast and GC friendly fixpoint combinator.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 

#time

let rec Y f x = f (Y f) x

let Y' f x = 
    let r = ref Unchecked.defaultof<'a -> 'b>
    r := (fun x -> f !r x)
    f !r  x

let iter f x = if x = 100000000 then x else f (x + 1)

// Real: 00:00:01.504, CPU: 00:00:01.497, GC gen0: 572, gen1: 1, gen2: 0
Y iter 1
// Real: 00:00:00.769, CPU: 00:00:00.780, GC gen0: 0, gen1: 0, gen2: 0
Y' iter 1
val Y : f:(('a -> 'b) -> 'a -> 'b) -> x:'a -> 'b

Full name: Script.Y
val f : (('a -> 'b) -> 'a -> 'b)
val x : 'a
val Y' : f:(('a -> 'b) -> 'a -> 'b) -> x:'a -> 'b

Full name: Script.Y'
val r : ('a -> 'b) ref
Multiple items
val ref : value:'T -> 'T ref

Full name: Microsoft.FSharp.Core.Operators.ref

--------------------
type 'T ref = Ref<'T>

Full name: Microsoft.FSharp.Core.ref<_>
module Unchecked

from Microsoft.FSharp.Core.Operators
val defaultof<'T> : 'T

Full name: Microsoft.FSharp.Core.Operators.Unchecked.defaultof
val iter : f:(int -> int) -> x:int -> int

Full name: Script.iter
val f : (int -> int)
val x : int
Raw view Test code New version

More information

Link:http://fssnip.net/gS
Posted:11 years ago
Author:Nick Palladinos
Tags: fixpoint

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.