Fork me on GitHub

All

Code Snippet:

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
type 'a ListLazy = Cons of 'a * 'a ListLazy Lazy | Nil

module List =
  module Lazy =
    let single h = Cons(h, lazy (Nil))
    let cons h l = Cons(h, lazy (l))
    let head = function | Nil -> failwith "empty list" | Cons(h,_) -> h
    let tail = function | Nil -> failwith "empty list" | Cons(_,t) -> t.Force()
    let rec iter f = function
      | Nil -> () | Cons(h,t) -> f h; iter f (t.Force())
    let rec map f = function
      | Nil -> Nil | Cons(h,t) -> Cons(f h, lazy (map f (t.Force())))
    let rec fold f init = function
      | Nil -> init | Cons(h,t) -> fold f (f init h) (t.Force())
    let rec foldBack f init = function
      | Nil -> init | Cons(h,t) -> f h (lazy (foldBack f init (t.Force())))
    let rec unfold f init = f init |> function
      | None -> Nil | Some(a,s) -> Cons (a, lazy (unfold f s))
    let rec reduce f = function
      | Nil -> failwith "empty list" | Cons(h,t) -> fold f h (t.Force())
    let rec reduceBack f = function
      | Nil -> failwith "empty list" | Cons(h,t) -> foldBack f h (t.Force())
    let rec skip n = function
      | Nil -> Nil | Cons(h,t) -> (n = 0I) |> function
        | true  -> cons h (t.Force())
        | false -> skip (n-1I) (t.Force())
    let rec take n = function
      | Nil -> Nil | Cons(h,t) -> (n = 0I) |> function
        | true  -> Nil
        | false -> Cons(h, lazy (take (n-1I) (t.Force())))
    let rec append l1 l2 = l1 |> function
      | Nil -> l2 | Cons(h,t) -> Cons(h, lazy (append (t.Force()) l2))
    let rec concat = function
      | Nil -> Nil | Cons(h,t) -> append h (concat (t.Force()))
    let rec ofList = function
      | [] -> Nil | h :: t -> cons h (ofList t)
    let toList l =
      let rec toList' acc = function
        | Nil -> List.rev acc
        | Cons(h,t) -> toList' (h::acc) (t.Force())
      toList' [] l

Code output:

> 
type 'a ListLazy =
  | Cons of 'a * Lazy<'a ListLazy>
  | Nil
module List = begin
  module Lazy = begin
    val single : h:'a -> 'a ListLazy
    val cons : h:'a -> l:'a ListLazy -> 'a ListLazy
    val head : _arg1:'a ListLazy -> 'a
    val tail : _arg1:'a ListLazy -> 'a ListLazy
    val iter : f:('a -> unit) -> _arg1:'a ListLazy -> unit
    val map : f:('a -> 'b) -> _arg1:'a ListLazy -> 'b ListLazy
    val fold : f:('a -> 'b -> 'a) -> init:'a -> _arg1:'b ListLazy -> 'a
    val foldBack :
      f:('a -> Lazy<'b> -> 'b) -> init:'b -> _arg1:'a ListLazy -> 'b
    val unfold : f:('a -> ('b * 'a) option) -> init:'a -> 'b ListLazy
    val reduce : f:('a -> 'a -> 'a) -> _arg1:'a ListLazy -> 'a
    val reduceBack : f:('a -> Lazy<'a> -> 'a) -> _arg1:'a ListLazy -> 'a
    val skip :
      n:System.Numerics.BigInteger -> _arg1:'a ListLazy -> 'a ListLazy
    val take :
      n:System.Numerics.BigInteger -> _arg1:'a ListLazy -> 'a ListLazy
    val append : l1:'a ListLazy -> l2:'a ListLazy -> 'a ListLazy
    val concat : _arg1:'a ListLazy ListLazy -> 'a ListLazy
    val ofList : _arg1:'a list -> 'a ListLazy
    val toList : l:'a ListLazy -> 'a list
  end
end

Infinite Fibonacci (and squared) sequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
let fib =
  (List.Lazy.single 0I,
   List.Lazy.unfold(fun (a1,a2) -> Some(a1+a2,(a2,a1+a2))) (1I,0I))
  ||> List.Lazy.append

let fibSquared =
  fib |> List.Lazy.foldBack(fun x l -> Cons(x*x,l)) Nil

fib
|> List.Lazy.take 10I
|> List.Lazy.iter(printf "%A ")

fibSquared
|> List.Lazy.take 10I
|> List.Lazy.iter(printf "%A ")
> 
val fib : System.Numerics.BigInteger ListLazy = Cons (0,Value is not created.)
val fibSquared : System.Numerics.BigInteger ListLazy =
  Cons (0,Value is not created.)

> 0 1 1 2 3 5 8 13 21 34 val it : unit = ()
> 0 1 1 4 9 25 64 169 441 1156 val it : unit = ()

Runtime errors when skipping/taking on empty sequences (F# Seq)

1
2
3
4
5
6
fib
|> List.Lazy.take 10I
|> List.Lazy.toList
|> List.toSeq
|> Seq.skip 20 
|> Seq.iter(printf "%A ")
> val it : seq<System.Numerics.BigInteger> =
  Error: The input sequence has an insufficient number of elements.
1
2
3
4
5
6
fib
|> List.Lazy.take 10I
|> List.Lazy.toList
|> List.toSeq
|> Seq.take 20
|> Seq.iter(printf "%A ")
> 0 1 1 2 3 5 8 13 21 34 System.InvalidOperationException: The input sequence has an insufficient number of elements.
  at Microsoft.FSharp.Collections.SeqModule+Take@999[System.Numerics.BigInteger].GenerateNext (IEnumerable`1& next) [0x00000] in <filename unknown>:0 
  at Microsoft.FSharp.Core.CompilerServices.GeneratedSequenceBase`1[System.Numerics.BigInteger].MoveNextImpl () [0x00000] in <filename unknown>:0 
  at Microsoft.FSharp.Core.CompilerServices.GeneratedSequenceBase`1[System.Numerics.BigInteger].System-Collections-IEnumerator-MoveNext () [0x00000] in <filename unknown>:0 
  at Microsoft.FSharp.Collections.SeqModule.Iterate[BigInteger] (Microsoft.FSharp.Core.FSharpFunc`2 action, IEnumerable`1 source) [0x00000] in <filename unknown>:0 
  at <StartupCode$FSI_0047>.$FSI_0047.main@ () [0x00000] in <filename unknown>:0 
  at (wrapper managed-to-native) System.Reflection.MonoMethod:InternalInvoke (System.Reflection.MonoMethod,object,object[],System.Exception&)
  at System.Reflection.MonoMethod.Invoke (System.Object obj, BindingFlags invokeAttr, System.Reflection.Binder binder, System.Object[] parameters, System.Globalization.CultureInfo culture) [0x00000] in <filename unknown>:0 
Stopped due to error

No runtime errors when skipping/taking on empty lists

1
2
3
4
5
6
7
8
9
fib
|> List.Lazy.take 10I
|> List.Lazy.skip 20I // Behave as C# Linq.Enumerable.Skip
|> List.Lazy.iter(printf "%A ")

fib
|> List.Lazy.take 10I
|> List.Lazy.take 20I // Behave as C# Linq.Enumerable.Take (or F# Seq.truncate)
|> List.Lazy.iter(printf "%A ")
> val it : unit = ()
> 0 1 1 2 3 5 8 13 21 34 val it : unit = ()

References:

comments powered by Disqus