4 people like it.

Lazy fixed-point and Infinite Streams

Examples of Infinite Streams defined using a lazy fixed-point combinator.

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

let force (value : Lazy<_>) = value.Force()

// Infinite Stream
type Stream<'T> = Cons of 'T * Lazy<Stream<'T>>
let head (Cons (h, _)) = h
let tail (Cons (_, t)) = force t 

// Lazy fixed-point
let fix : (Lazy<'T> -> 'T) -> Lazy<'T> = fun f ->
    let rec x = lazy (f x) in x 

// Examples  
let ones = fix (fun x -> Cons (1, x))
let map f = fix (fun f' x -> Cons (f (head x), lazy(force f' (tail x)))  )
let nats = fix (fun x -> Cons (1, lazy ( (force (map ((+) 1))) (force x)  )))
val force : value:Lazy<'a> -> 'a

Full name: Script.force
val value : Lazy<'a>
Multiple items
active recognizer Lazy: Lazy<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.( |Lazy| )

--------------------
type Lazy<'T> = System.Lazy<'T>

Full name: Microsoft.FSharp.Control.Lazy<_>
member System.Lazy.Force : unit -> 'T
type Stream<'T> = | Cons of 'T * Lazy<Stream<'T>>

Full name: Script.Stream<_>
union case Stream.Cons: 'T * Lazy<Stream<'T>> -> Stream<'T>
val head : Stream<'a> -> 'a

Full name: Script.head
val h : 'a
val tail : Stream<'a> -> Stream<'a>

Full name: Script.tail
val t : Lazy<Stream<'a>>
val fix : f:(Lazy<'T> -> 'T) -> Lazy<'T>

Full name: Script.fix
val f : (Lazy<'T> -> 'T)
val x : Lazy<'T>
val ones : Lazy<Stream<int>>

Full name: Script.ones
val x : Lazy<Stream<int>>
val map : f:('a -> 'b) -> Lazy<(Stream<'a> -> Stream<'b>)>

Full name: Script.map
val f : ('a -> 'b)
val f' : Lazy<(Stream<'a> -> Stream<'b>)>
val x : Stream<'a>
val nats : Lazy<Stream<int>>

Full name: Script.nats
Raw view Test code New version

More information

Link:http://fssnip.net/sD
Posted:9 years ago
Author:Nick Palladinos
Tags: streams , fixed-point

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.