39 people like it.

LazyList

A LazyList implementation with tail recursive enumeration.

 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: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57: 
58: 
59: 
60: 
61: 
62: 
63: 
64: 
65: 
66: 
67: 
68: 
69: 
70: 
71: 
72: 
73: 
74: 
75: 
76: 
77: 
78: 
79: 
open System.Collections
open System.Collections.Generic

// LazyList dataType + Monoid Structure
type LazyList<'T> =   Empty
                    | Cons of 'T * (unit -> LazyList<'T>)
                    | Delay of (unit -> LazyList<'T>)
                    | Combine of LazyList<'T> * LazyList<'T> with
        interface IEnumerable<'T> with
            member self.GetEnumerator() =
                // tail-recursive enumeration 
                let rec toSeq stack = 
                    match stack with
                    | [] -> Seq.empty
                    | head :: tail ->
                        match head with
                        | Empty -> toSeq tail
                        | Cons (value, rest) -> seq { yield value; yield! toSeq <| rest () :: tail }
                        | Delay f -> toSeq <| f () :: tail
                        | Combine (first, second) -> toSeq <| first :: second :: tail
                (toSeq [self]).GetEnumerator() 
        interface IEnumerable with 
            member self.GetEnumerator() = (self :> IEnumerable<'T>).GetEnumerator() :> _ 

// Monoid Comprehension
type LazyListBuilder() = 
    member self.Yield value = Cons (value, fun () -> Empty)
    member self.YieldFrom value = value
    member self.Combine(first, second) = Combine (first, second) 
    member self.Delay f = Delay f
    member self.Zero() = Empty

let lazyList = new LazyListBuilder()


// Example
#time
type Tree<'T> = Empty | Branch of 'T * Tree<'T> * Tree<'T>

let rec createBalancedTree n = 
    if n <= 0 then Empty
    else Branch (n, createBalancedTree (n - 1), createBalancedTree (n - 1))

let rec createLeftSpinedTree n acc = 
    if n <= 0 then acc
    else createLeftSpinedTree (n - 1) (Branch (n, acc, Empty))

let tree = createBalancedTree 20
let leftSpinedTree = createLeftSpinedTree 100000 Empty

// Seq test
let rec flattenToSeq tree =
    match tree with
    | Empty -> Seq.empty
    | Branch (value, left, right) -> 
        seq { yield value; yield! flattenToSeq left; yield! flattenToSeq right }

tree
|> flattenToSeq
|> Seq.length // check time

leftSpinedTree
|> flattenToSeq
|> Seq.length // stack-overflow

// LazyList test
let rec flattenToLazyList tree =
    match tree with
    | Empty -> LazyList.Empty 
    | Branch (value, left, right) -> 
        lazyList { yield value; yield! flattenToLazyList left; yield! flattenToLazyList right }

tree
|> flattenToLazyList
|> Seq.length // check time

leftSpinedTree
|> flattenToLazyList
|> Seq.length // check time
namespace System
namespace System.Collections
namespace System.Collections.Generic
type LazyList<'T> =
  | Empty
  | Cons of 'T * (unit -> LazyList<'T>)
  | Delay of (unit -> LazyList<'T>)
  | Combine of LazyList<'T> * LazyList<'T>
  interface IEnumerable
  interface IEnumerable<'T>

Full name: Script.LazyList<_>
union case LazyList.Empty: LazyList<'T>
union case LazyList.Cons: 'T * (unit -> LazyList<'T>) -> LazyList<'T>
type unit = Unit

Full name: Microsoft.FSharp.Core.unit
union case LazyList.Delay: (unit -> LazyList<'T>) -> LazyList<'T>
union case LazyList.Combine: LazyList<'T> * LazyList<'T> -> LazyList<'T>
Multiple items
type IEnumerable =
  member GetEnumerator : unit -> IEnumerator

Full name: System.Collections.IEnumerable

--------------------
type IEnumerable<'T> =
  member GetEnumerator : unit -> IEnumerator<'T>

Full name: System.Collections.Generic.IEnumerable<_>
val self : LazyList<'T>
override LazyList.GetEnumerator : unit -> IEnumerator<'T>

Full name: Script.LazyList`1.GetEnumerator
val toSeq : (LazyList<'a> list -> seq<'a>)
val stack : LazyList<'a> list
module Seq

from Microsoft.FSharp.Collections
val empty<'T> : seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.empty
val head : LazyList<'a>
val tail : LazyList<'a> list
val value : 'a
val rest : (unit -> LazyList<'a>)
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

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

--------------------
type seq<'T> = IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
val f : (unit -> LazyList<'a>)
val first : LazyList<'a>
val second : LazyList<'a>
override LazyList.GetEnumerator : unit -> IEnumerator

Full name: Script.LazyList`1.GetEnumerator
Multiple items
type LazyListBuilder =
  new : unit -> LazyListBuilder
  member Combine : first:LazyList<'c> * second:LazyList<'c> -> LazyList<'c>
  member Delay : f:(unit -> LazyList<'b>) -> LazyList<'b>
  member Yield : value:'e -> LazyList<'e>
  member YieldFrom : value:'d -> 'd
  member Zero : unit -> LazyList<'a>

Full name: Script.LazyListBuilder

--------------------
new : unit -> LazyListBuilder
val self : LazyListBuilder
member LazyListBuilder.Yield : value:'e -> LazyList<'e>

Full name: Script.LazyListBuilder.Yield
val value : 'e
member LazyListBuilder.YieldFrom : value:'d -> 'd

Full name: Script.LazyListBuilder.YieldFrom
val value : 'd
member LazyListBuilder.Combine : first:LazyList<'c> * second:LazyList<'c> -> LazyList<'c>

Full name: Script.LazyListBuilder.Combine
val first : LazyList<'c>
val second : LazyList<'c>
member LazyListBuilder.Delay : f:(unit -> LazyList<'b>) -> LazyList<'b>

Full name: Script.LazyListBuilder.Delay
val f : (unit -> LazyList<'b>)
member LazyListBuilder.Zero : unit -> LazyList<'a>

Full name: Script.LazyListBuilder.Zero
val lazyList : LazyListBuilder

Full name: Script.lazyList
type Tree<'T> =
  | Empty
  | Branch of 'T * Tree<'T> * Tree<'T>

Full name: Script.Tree<_>
union case Tree.Empty: Tree<'T>
union case Tree.Branch: 'T * Tree<'T> * Tree<'T> -> Tree<'T>
val createBalancedTree : n:int -> Tree<int>

Full name: Script.createBalancedTree
val n : int
val createLeftSpinedTree : n:int -> acc:Tree<int> -> Tree<int>

Full name: Script.createLeftSpinedTree
val acc : Tree<int>
val tree : Tree<int>

Full name: Script.tree
val leftSpinedTree : Tree<int>

Full name: Script.leftSpinedTree
val flattenToSeq : tree:Tree<'a> -> seq<'a>

Full name: Script.flattenToSeq
val tree : Tree<'a>
val left : Tree<'a>
val right : Tree<'a>
val length : source:seq<'T> -> int

Full name: Microsoft.FSharp.Collections.Seq.length
val flattenToLazyList : tree:Tree<'a> -> LazyList<'a>

Full name: Script.flattenToLazyList

More information

Link:http://fssnip.net/1O
Posted:6 years ago
Author:Nick Palladinos
Tags: lazylist