Lecture 12 — Sequences and laziness

1 · Eager evaluation

List processing in several steps

Suppose that writing to the console represents an expensive computation. Consider the following program.

let listResult =
  [1 .. 10]
  |> List.map    (fun x -> printfn "map1: %d" x;   x + 1)
  |> List.filter (fun x -> printfn "filter: %d" x; x % 2 = 0)
  |> List.map    (fun x -> printfn "map2: %d" x;   x * 2)
  |> List.truncate 3
map1: 1
map1: 2
map1: 3
map1: 4
map1: 5
map1: 6
map1: 7
map1: 8
map1: 9
map1: 10
filter: 2
filter: 3
filter: 4
filter: 5
filter: 6
filter: 7
filter: 8
filter: 9
filter: 10
filter: 11
map2: 2
map2: 4
map2: 6
map2: 8
map2: 10
[4; 8; 12]

Which elements of the original list were needed to compute the result? The prefix of the first five elements.

If we start with a longer list, say [1 .. 20], then we would perform even more unnecessary work.

let listAll =
  [1 .. 20]
  |> List.map    (fun x -> printfn "map1: %d" x;   x + 1)
  |> List.filter (fun x -> printfn "filter: %d" x; x % 2 = 0)
  |> List.map    (fun x -> printfn "map2: %d" x;   x * 2)
  |> List.truncate 3
map1: 1
map1: 2
map1: 3
map1: 4
map1: 5
map1: 6
map1: 7
map1: 8
map1: 9
map1: 10
map1: 11
map1: 12
map1: 13
map1: 14
map1: 15
map1: 16
map1: 17
map1: 18
map1: 19
map1: 20
filter: 2
filter: 3
filter: 4
filter: 5
filter: 6
filter: 7
filter: 8
filter: 9
filter: 10
filter: 11
filter: 12
filter: 13
filter: 14
filter: 15
filter: 16
filter: 17
filter: 18
filter: 19
filter: 20
filter: 21
map2: 2
map2: 4
map2: 6
map2: 8
map2: 10
map2: 12
map2: 14
map2: 16
map2: 18
map2: 20
[4; 8; 12]

List.truncate 3 now discards even more elements.

We have structured our program as a pipeline of list processing steps. This helps with readability. However, we see that there is a danger of doing more work than necessary because of eager evaluation.

Today we are going to look at ways to overcome this: build programs by composing smaller programs but avoid doing unnecessary work.

Folding

We can do the map, filter, and map steps as a single fold over the input list:

let foldResult =
  [1 .. 10]
  |> List.fold (fun (c, r) x ->
                 printfn "fold: %d" x
                 let x' = x + 1 // map
                 // truncate and filter
                 if c < 3 && x' % 2 = 0 then
                   printfn "true: %d" x'
                   let x'' = x' * 2 // map
                   (c + 1, x'' :: r)
                 else
                   (c, r))
               (0, [])
  |> snd
  |> List.rev
fold: 1
true: 2
fold: 2
fold: 3
true: 4
fold: 4
fold: 5
true: 6
fold: 6
fold: 7
fold: 8
fold: 9
fold: 10
[4; 8; 12]

We fold over the list once (and then reverse the result) and the true-branch is evaluated at most three times. This is better, but the code is now less clear.

2 · Sequences

The type 'a seq (of sequences of elements of type 'a) is an alias for IEnumerable<'a>, which is an interface.

Do not think of sequences as data structures: a sequence with values of type 'a is a "gadget" from which we can ask for the next element. There might not be a next element. A sequence might be infinite, in which case there is always a next element.

Our original example again, but now using the operations of the Seq module:

let seqResult =
  [1 .. 10]
  |> Seq.map    (fun x -> printfn "map1: %d" x;   x + 1)
  |> Seq.filter (fun x -> printfn "filter: %d" x; x % 2 = 0)
  |> Seq.map    (fun x -> printfn "map2: %d" x;   x * 2)
  |> Seq.truncate 3
  |> Seq.toList // force the sequence
map1: 1
filter: 2
map2: 2
map1: 2
filter: 3
map1: 3
filter: 4
map2: 4
map1: 4
filter: 5
map1: 5
filter: 6
map2: 6
[4; 8; 12]

The input is still a list, but we work with operations from the Seq module. The final result is the same as before except that it is computed differently (as we can see from the output).

3 · A sequence describes how to compute an element

A value of type int list is a list of integers and these integers are kept in memory. A value of type int seq is a description of how to compute a sequence of integers (when asked to). The fact that we have a value xs : int seq does not mean that any of the integers have been computed.

Asking for the next element (or i-th element) of a sequence triggers the necessary computation to compute that element. This does not mean that this element gets stored somewhere.

The sequence of even non-negative integers:

let evenNums : int seq =
  Seq.initInfinite (fun i -> printfn "evenNums: %d" i
                             i * 2)

Evaluating this definition does not print anything (no elements are actually computed). Asking for a particular element (say, the element at index 5) triggers a computation and prints something to the console.

let item5 = Seq.item 5 evenNums
evenNums: 5
10

Truncating the sequence does not print anything either:

let first10 = Seq.truncate 10 evenNums

Converting it to a list does:

let first10List = first10 |> Seq.toList
evenNums: 0
evenNums: 1
evenNums: 2
evenNums: 3
evenNums: 4
evenNums: 5
evenNums: 6
evenNums: 7
evenNums: 8
evenNums: 9
[0; 2; 4; 6; 8; 10; 12; 14; 16; 18]

Seq.item asks for the element at some position in the sequence. It forces the computation of that element. Similarly, Seq.toList forces the computation of all of the elements in the sequence, to convert the sequence to a list. Note that evenNums: 5 is printed again although we already computed it before.

Infinite vs finite

As sequences can be infinite (there is always a next element), we should not convert arbitrary sequences to lists. For example, what is the result of evaluating the following?

Seq.toList evenNums

Note that the printing step of the REPL for an unnamed sequence prints the beginning of the sequence (and thus forces the computation of those elements).

> Seq.initInfinite (fun i -> printfn "evenNums: %d" i
                             i * 2);;
evenNums: 0
evenNums: 1
evenNums: 2
evenNums: 3
evenNums: 4
val it: int seq = seq [0; 2; 4; 6; ...]

Evaluating the expression itself does not force anything; for example, evaluating the following prints nothing:

let evenNums' =
  Seq.initInfinite (fun i -> printfn "evenNums: %d" i
                             i * 2)

4 · Computing an element

Our example again, but now we start with an infinite sequence:

let res =
  Seq.initInfinite (fun i -> printfn "init: %d" i; i)
  |> Seq.map    (fun x -> printfn "map1: %d" x;   x + 1)
  |> Seq.filter (fun x -> printfn "filter: %d" x; x % 2 = 0)
  |> Seq.map    (fun x -> printfn "map2: %d" x;   x * 2)
  |> Seq.truncate 3
  |> Seq.toList // force the sequence
init: 0
map1: 0
filter: 1
init: 1
map1: 1
filter: 2
map2: 2
init: 2
map1: 2
filter: 3
init: 3
map1: 3
filter: 4
map2: 4
init: 4
map1: 4
filter: 5
init: 5
map1: 5
filter: 6
map2: 6
[4; 8; 12]

Note that we convert the sequence to a list after the truncation when we have a finite sequence.

The last "init" step that is printed is init: 5. Why?

Reading bottom to top (outside-in)

Seq.toList forces the computation of every element of the sequence that is given to it as the argument. That sequence is:

Seq.initInfinite (fun i -> printfn "init: %d" i; i)
|> Seq.map    (fun x -> printfn "map1: %d" x;   x + 1)
|> Seq.filter (fun x -> printfn "filter: %d" x; x % 2 = 0)
|> Seq.map    (fun x -> printfn "map2: %d" x;   x * 2)
|> Seq.truncate 3

Seq.toList asks for the elements of this sequence one-by-one. The first element of this sequence is the first element of the sequence given to Seq.truncate 3 as argument:

Seq.initInfinite (fun i -> printfn "init: %d" i; i)
|> Seq.map    (fun x -> printfn "map1: %d" x;   x + 1)
|> Seq.filter (fun x -> printfn "filter: %d" x; x % 2 = 0)
|> Seq.map    (fun x -> printfn "map2: %d" x;   x * 2)

The first element of this sequence is x * 2, where x is the first element of the sequence:

Seq.initInfinite (fun i -> printfn "init: %d" i; i)
|> Seq.map    (fun x -> printfn "map1: %d" x;   x + 1)
|> Seq.filter (fun x -> printfn "filter: %d" x; x % 2 = 0)

The first element of this sequence is the first even element of the sequence:

Seq.initInfinite (fun i -> printfn "init: %d" i; i)
|> Seq.map (fun x -> printfn "map1: %d" x; x + 1)

If the first element of this sequence is not even, then filter asks for the next element until it gets an even one. The first element of this sequence is indeed odd, as the first element of the sequence

Seq.initInfinite (fun i -> printfn "init: %d" i; i)

is 0 (which is even).

When Seq.toList has received 3 elements from the truncated sequence and then asks for the next element, the truncated sequence responds that there are no more elements. Importantly, the truncated sequence does not ask the original sequence whether there are more elements.

With sequences we can write a program as a composition of small programs (a pipeline of sequence (list) processing steps, for example) that only computes as much as is necessary (for the part of the result that is required).

Not a data structure

Note that if we ask for the element at, say, index 1 of a sequence:

let res' =
  Seq.initInfinite (fun i -> printfn "init: %d" i; i)
  |> Seq.map    (fun x -> printfn "map1: %d" x;   x + 1)
  |> Seq.filter (fun x -> printfn "filter: %d" x; x % 2 = 0)
  |> Seq.map    (fun x -> printfn "map2: %d" x;   x * 2)

let item1 = Seq.item 1 res'
init: 0
map1: 0
filter: 1
init: 1
map1: 1
filter: 2
map2: 2
init: 2
map1: 2
filter: 3
init: 3
map1: 3
filter: 4
map2: 4
8

and then ask for the same element again:

let item1Again = Seq.item 1 res'
init: 0
map1: 0
filter: 1
init: 1
map1: 1
filter: 2
map2: 2
init: 2
map1: 2
filter: 3
init: 3
map1: 3
filter: 4
map2: 4
8

we see that everything is recomputed. A sequence is not a data structure that stores its values somewhere. It is a description of how to compute the elements (when asked to).

5 · Same elements, different computation

Two sequences of even numbers

Even though two sequences may seem to be the same (they have the same elements), the way the elements are computed can be different:

let s1 = Seq.initInfinite (fun i ->
           printfn "s1: %d" i
           i * 2)

let s2 = Seq.unfold (fun i ->
           printfn "s2: %d" i
           Some (i * 2, i + 1)) 0

let s1First10 = Seq.truncate 10 s1 |> Seq.toList
s1: 0
s1: 1
s1: 2
s1: 3
s1: 4
s1: 5
s1: 6
s1: 7
s1: 8
s1: 9
[0; 2; 4; 6; 8; 10; 12; 14; 16; 18]
let s2First10 = Seq.truncate 10 s2 |> Seq.toList
s2: 0
s2: 1
s2: 2
s2: 3
s2: 4
s2: 5
s2: 6
s2: 7
s2: 8
s2: 9
[0; 2; 4; 6; 8; 10; 12; 14; 16; 18]

s1 and s2 agree on the first ten elements (and print the same messages to the console).

Let's compare how the element at index 5 is computed for these two sequences:

let s1Item5 = Seq.item 5 s1
s1: 5
10
let s2Item5 = Seq.item 5 s2
s2: 0
s2: 1
s2: 2
s2: 3
s2: 4
s2: 5
10

What is Seq.initInfinite?

Any function f : int -> X can be seen as a sequence of values of type X. The element at index 0 is f 0, the element at index 1 is f 1, the element at index 2 is f 2, and so on:

Seq.item n (Seq.initInfinite f)  is  f n

To compute the element at index 5 of s1, we do not need to compute the prefix.

What is Seq.unfold?

Suppose we have the following two functions and a value:

obs  : S -> X
next : S -> S
s    : S

We can view these three things as a sequence of values of type X. Think of the type S as representing the internal state necessary for computing the current element of the sequence. obs computes the current element from the given state; next computes the next state from the current state. For <s, obs, next> the element at

index 0:  obs s
index 1:  obs (next s)
index 2:  obs (next (next s))
...
let s = (0, 1)
let obs (x, y) = x
let next (x, y) = (y, x + y)

let observed =
  [ obs s
    obs (next s)
    obs (next (next s))
    obs (next (next (next s)))
    obs (next (next (next (next s))))
    obs (next (next (next (next (next s)))))
    obs (next (next (next (next (next (next s)))))) ]
[0; 1; 1; 2; 3; 5; 8]

Seq.unfold provides a convenient way to produce a sequence in this stateful manner:

Seq.unfold : (S -> (X * S) option) -> S -> X seq

The option type is used to indicate the (possible) end of the sequence.

What are the elements of the sequence Seq.unfold f s? There are two cases:

let unfolded =
  Seq.unfold (fun s -> Some (obs s, next s)) (0, 1)
  |> Seq.truncate 10
  |> Seq.toList
[0; 1; 1; 2; 3; 5; 8; 13; 21; 34]

6 · Enumerators

Recall that 'a seq is an alias for IEnumerable<'a> and an enumerable is just a factory of enumerators. This means that we can also define a sequence by constructing an enumerator.

This approach is more verbose ("low-level") but might be necessary when the Seq module does not provide the operations we need.

An enumerator essentially consists of three parts corresponding to:

  1. What is the current element?
  2. Is there a next element?
  3. Move to the next element.

In .NET, 2. and 3. are combined into a single method that moves further and returns a Boolean saying whether that move was valid.

open System.Collections
open System.Collections.Generic

let evenEnumerator () : IEnumerator<int> =
  let mutable i = -1
  { new IEnumerator<int> with
      member _.Current =
        printfn "Current: %d" i
        i * 2
    interface IEnumerator with
      member _.Current = box (i * 2) // int wrapped in Object
      member _.MoveNext () =
        printfn "MoveNext"
        i <- i + 1
        true
      member _.Reset () = i <- -1
    interface System.IDisposable with
      member _.Dispose () = printfn "Dispose" }

Why is Current implemented twice? IEnumerator<'T> extends the older, non-generic IEnumerator (from before .NET had generics) and IDisposable. It adds only a typed Current : 'T; MoveNext and Reset come from IEnumerator, which also has its own Current : obj. Implementing IEnumerator<int> means implementing all three interfaces, each member in its own interface's section. The Seq functions use the typed Current: it is the one that prints below. For the same reason s3 further down implements GetEnumerator twice.

Driving an enumerator by hand

We can walk an enumerator ourselves: take two elements, and later continue where we stopped:

let e = evenEnumerator ()

let firstTwo =
  [ for _ in 1 .. 2 do
      e.MoveNext () |> ignore
      e.Current ]
MoveNext
Current: 0
MoveNext
Current: 1
[0; 2]
let nextTwo =
  [ for _ in 1 .. 2 do
      e.MoveNext () |> ignore
      e.Current ]
MoveNext
Current: 2
MoveNext
Current: 3
[4; 6]
e.Dispose ()
Dispose

A new enumerator for every consumer

The sequence only hands out new enumerators:

let s3 =
  { new IEnumerable<int> with
      member _.GetEnumerator () =
        printfn "GetEnumerator"
        evenEnumerator ()
    interface IEnumerable with
      member _.GetEnumerator () =
        evenEnumerator () }

How is the element at index 5 computed?

let s3Item5 = Seq.item 5 s3
GetEnumerator
MoveNext
MoveNext
MoveNext
MoveNext
MoveNext
MoveNext
Current: 5
Dispose
10

Seq.item asks for a new enumerator, moves it six times (enumerator starts off by pointing to "before" the first element), reads Current once and then disposes. Asking another item (invoking Seq.item) starts again by asking for a new enumerator, which is why everything was recomputed in Section 4.

Seq.truncate 3 does not ask for a fourth element:

let s3First3 = s3 |> Seq.truncate 3 |> Seq.toList
GetEnumerator
MoveNext
Current: 0
MoveNext
Current: 1
MoveNext
Current: 2
Dispose
[0; 2; 4]

Seq.skip gives the same elements as nextTwo, but it cannot continue an earlier walk: it starts a new enumeration from the beginning:

let skipped =
  s3
  |> Seq.skip 2
  |> Seq.truncate 2
  |> Seq.toList
GetEnumerator
MoveNext
MoveNext
MoveNext
Current: 2
MoveNext
Current: 3
Dispose
[4; 6]

Seq.filter from an enumerator

The IEnumerable part is always the same: it is a factory of enumerators.

let fromEnumerator (make : unit -> IEnumerator<'a>) : 'a seq =
  { new IEnumerable<'a> with
      member _.GetEnumerator () = make ()
    interface IEnumerable with
      member _.GetEnumerator () = make () }

We can define sequence operations by working with the enumerator underlying the sequence. For example, for a filtered sequence we need to drive the underlying enumerator until we get an element that satisfies the predicate. (MoveNext keeps moving the source until the predicate holds, and its Current is the source's Current):

let myFilter (p : 'a -> bool) (xs : 'a seq) : 'a seq =
  fromEnumerator (fun () ->
    let source = xs.GetEnumerator ()
    { new IEnumerator<'a> with
        member _.Current = source.Current
      interface IEnumerator with
        member _.Current = box source.Current
        member _.MoveNext () =
          let mutable found = false
          while not found && source.MoveNext () do
            found <- p source.Current
          found
        member _.Reset () = source.Reset ()
      interface System.IDisposable with
        member _.Dispose () = source.Dispose () })

A source that prints each element it produces:

let numbers =
  Seq.initInfinite (fun i -> printfn "produce %d" i; i)
  |> Seq.truncate 6

let filteredOwn =
  numbers
  |> myFilter (fun x -> x % 2 = 0)
  |> Seq.truncate 2
  |> Seq.toList
produce 0
produce 1
produce 2
[0; 2]

Seq.filter does the same work:

let filteredLib =
  numbers
  |> Seq.filter (fun x -> x % 2 = 0)
  |> Seq.truncate 2
  |> Seq.toList
produce 0
produce 1
produce 2
[0; 2]

Consecutive pairs

Combining Seq functions can do more work than one enumerator. Pairs of consecutive elements of a sequence, built from Seq.zip and Seq.tail:

let pairsZip = Seq.zip numbers (Seq.tail numbers) |> Seq.toList
produce 0
produce 0
produce 1
produce 1
produce 2
produce 2
produce 3
produce 3
produce 4
produce 4
produce 5
produce 5
[(0, 1); (1, 2); (2, 3); (3, 4); (4, 5)]

Seq.zip walks numbers and Seq.tail numbers (ask the enumerator of numbers and of Seq.tail numbers) so every element is produced twice. fibs in section 10 is defined the same way, from Seq.zip fibs (Seq.tail fibs).

We can define a function that walks a sequence and keeps track of the previous element.

let myPairwise (xs : 'a seq) : ('a * 'a) seq =
  fromEnumerator (fun () ->
    let source = xs.GetEnumerator ()
    let mutable previous = None
    let mutable pair = None
    { new IEnumerator<'a * 'a> with
        member _.Current = Option.get pair
      interface IEnumerator with
        member _.Current = box (Option.get pair)
        member _.MoveNext () =
          if Option.isNone previous && source.MoveNext () then
            previous <- Some source.Current
          match previous with
          | Some x when source.MoveNext () ->
              let y = source.Current
              pair <- Some (x, y)
              previous <- Some y
              true
          | _ -> false
        member _.Reset () =
          source.Reset ()
          previous <- None
          pair <- None
      interface System.IDisposable with
        member _.Dispose () = source.Dispose () })

let pairsOwn = myPairwise numbers |> Seq.toList
produce 0
produce 1
produce 2
produce 3
produce 4
produce 5
[(0, 1); (1, 2); (2, 3); (3, 4); (4, 5)]

This is what Seq.pairwise (section 8) does.

7 · The Seq module

Some functions of the Seq module

seq : 'a seq -> 'a seq

Seq.init         // int -> (int -> 'a) -> 'a seq
Seq.initInfinite // (int -> 'a) -> 'a seq

Seq.unfold       // ('a -> ('b * 'a) option) -> 'a -> 'b seq

Seq.toList  // 'a seq -> 'a list
Seq.toArray // 'a seq -> 'a array

Seq.empty     // 'a seq
Seq.singleton // 'a -> 'a seq
Seq.append    // 'a seq -> 'a seq -> 'a seq

Seq.item    // int -> 'a seq -> 'a
Seq.tryItem // int -> 'a seq -> 'a option

Seq.skip      // int          -> 'a seq -> 'a seq
Seq.skipWhile // ('a -> bool) -> 'a seq -> 'a seq
Seq.take      // int          -> 'a seq -> 'a seq
Seq.takeWhile // ('a -> bool) -> 'a seq -> 'a seq

Seq.truncate  // int -> 'a seq -> 'a seq

Seq.map     // ('a -> 'b)        -> 'a seq -> 'b seq
Seq.filter  // ('a -> bool)      -> 'a seq -> 'a seq
Seq.collect // ('a -> #('c seq)) -> 'a seq -> 'c seq

Seq.fold // ('a -> 'b -> 'a) -> 'a -> 'b seq -> 'a
Seq.scan // ('a -> 'b -> 'a) -> 'a -> 'b seq -> 'a seq

Seq.cache // 'a seq -> 'a seq

Seq.delay // (unit -> 'a seq) -> 'a seq

seq views a collection (here a list) as a sequence:

let xs = [1 .. 5]

let xsSeq : int seq = seq xs

Seq.cache

let nats =
  Seq.initInfinite (fun i -> printfn "%d" i; i)

let natsItems =
  [ Seq.item 3 nats
    Seq.item 5 nats
    Seq.item 3 nats ]
3
5
3
[3; 5; 3]
let cachedNats = Seq.cache nats

let cachedNatsItems =
  [ Seq.item 3 cachedNats
    Seq.item 5 cachedNats
    Seq.item 3 cachedNats ]
0
1
2
3
4
5
[3; 5; 3]

8 · Example: square roots

Newton's method

Given a positive number \(a\), find a number \(x\) such that \(x \cdot x = a\). Equivalently, find a root of the function \(f(x) = x \cdot x - a\).

Let \(x_0\) be an initial guess for the value of \(x\). Under certain assumptions, a better approximation of \(x\) is (Newton's method):

\[ x_1 = x_0 - \frac{f(x_0)}{f'(x_0)} \]

By iterating this step,

\[ x_{n+1} = \frac{1}{2}\left(x_n + \frac{a}{x_n}\right) \]

we get a sequence approximating the square root of \(a\):

let roots a =
  // the "state" xn is the current approximation
  let step a xn = (xn + a / xn) / 2.0

  // our initial guess is 1.0
  Seq.unfold (fun xn -> Some (xn, step a xn)) 1.0

The first ten approximations:

let roots10 =
  roots 10.0
  |> Seq.truncate 10
  |> Seq.toList
[1.0; 5.5; 3.659090909; 3.196005082; 3.162455623; 3.162277665; 3.16227766;
 3.16227766; 3.16227766; 3.16227766]

A good enough approximation

Seq.pairwise pairs each element with the next one:

let pairs = Seq.pairwise (seq [1 .. 5]) |> Seq.toList
[(1, 2); (2, 3); (3, 4); (4, 5)]

The first approximation that differs from the one before it by at most 0.01:

let root10 =
  roots 10.0
  |> Seq.pairwise
  |> Seq.skipWhile (fun (r1, r2) -> abs (r1 - r2) > 0.01)
  |> Seq.head
  |> snd
3.162277665

Using sequences allows us to define the approximation itself and the choice of a good enough approximation independently. The user of the sequence of approximations controls how many approximations are actually computed. We just say how to compute the next one (when that is necessary).

9 · Sequence expressions

seq { … }

Sequence expressions are computation expressions (introduced in Lecture 11) for describing sequences. We can think of a sequence defined using sequence expressions as a program that, when asked for the next element, executes up to the next yield and then suspends execution.

seq { seqexp } generates a sequence:

let s123a =
  seq {
    yield 1
    yield 2
    yield 3
  }

let s123b =
  seq {
    yield 1
    yield! seq [2; 3]
  }

let s123c =
  seq {
    yield! seq [1; 2]
    yield 3
  }

let s123abc = [ Seq.toList s123a; Seq.toList s123b; Seq.toList s123c ]
[[1; 2; 3]; [1; 2; 3]; [1; 2; 3]]

A sequence inside a sequence

A sequence that prints when its elements are computed, inside another sequence:

let three =
  Seq.init 3 (fun x -> printfn "%d" x; x)

let s123d =
  seq {
    yield -1
    yield! three
    yield 3
    yield 4
  }

let s123dItems =
  [ Seq.item 0 s123d
    Seq.item 1 s123d
    Seq.item 2 s123d
    Seq.item 3 s123d
    Seq.item 4 s123d
    Seq.item 5 s123d ]
0
0
1
0
1
2
0
1
2
0
1
2
[-1; 0; 1; 2; 3; 4]

There are only six elements; asking for the element at index 6 throws:

> Seq.item 6 s123d;;
0
1
2
System.ArgumentException: The input sequence has an insufficient number of elements.
seq was short by 1 element (Parameter 'index')

Converting the whole sequence to a list:

let s123dList = Seq.toList s123d
0
1
2
[-1; 0; 1; 2; 3; 4]

You can sometimes omit yield (but not yield!):

let s123e =
  seq {
    1
    2
    3
  }

let s123eList = Seq.toList s123e
[1; 2; 3]

One after the other

seqexp1 followed by seqexp2:

let ex1 =
  seq {
    printfn "a"
    yield 1
    printfn "b"
    yield 2
    printfn "c"
    yield 3
    printfn "d"
  }

let ex1First = Seq.truncate 1 ex1 |> Seq.toList
a
[1]
let ex1All = Seq.toList ex1
a
b
c
d
[1; 2; 3]

let, for and if

let pat = exp followed by seqexp:

let seqLet =
  seq {
    let r = 3
    yield! [0 .. r]
  }
  |> Seq.toList
[0; 1; 2; 3]

for pat in exp do seqexp:

let seqFor =
  seq {
    for x in [1 .. 3] do
      yield! [x; x - 1]
  }
  |> Seq.toList
[1; 0; 2; 1; 3; 2]

if exp then seqexp and if exp then seqexp else seqexp:

let seqIf =
  seq {
    let r = 4

    if r % 2 = 0 then // filtering
      yield r

    if r % 3 = 0 then
      yield 3
    else
      yield! [11; 22; 33]
  }
  |> Seq.toList
[4; 11; 22; 33]

A recursive sequence

let rec from i =
  seq {
    yield i
    yield! from (i + 1)
  }

let from5 =
  from 5
  |> Seq.truncate 10
  |> Seq.toList
[5; 6; 7; 8; 9; 10; 11; 12; 13; 14]

We can do the same thing without sequence expressions, but we have to be careful. This is not good; fromBad 0 will loop:

let rec fromBad i =
  Seq.append (Seq.singleton i) (fromBad (i + 1))

Why? Running it:

> fromBad 0;;
Stack overflow.
Repeated 261507 times:
--------------------------------
   at FSI_0002.fromBad(Int32)
--------------------------------

The arguments to Seq.append, as to any other function, are evaluated before the body: when evaluating fromBad 0, we need to evaluate fromBad 1 before the append, and so on. The recursive calls fill the stack.

Seq.delay

If we want to define from like this, we need to use Seq.delay:

let rec from' i =
  Seq.delay (fun () ->
    printfn "delay"
    Seq.append (Seq.singleton i) (from' (i + 1)))

let rec from'' i =
  Seq.append (Seq.singleton i)
             (Seq.delay (fun () ->
                printfn "delay"
                from'' (i + 1)))

let from5' =
  from' 5
  |> Seq.truncate 10
  |> Seq.toList
delay
delay
delay
delay
delay
delay
delay
delay
delay
delay
[5; 6; 7; 8; 9; 10; 11; 12; 13; 14]

When is "delay" printed?

let f5' = from' 5
let f5'Item1 = Seq.item 1 f5'
delay
delay
6
let f5'' = from'' 5
let f5''Item1 = Seq.item 1 f5''
delay
6

10 · Fibonacci numbers

The value fibs defined below is recursive. F# checks such recursive references to a value at runtime and warns about them (FS0040); the directive silences this warning.

#nowarn "40"

let rec fibs =
  seq {
    printfn "fibs"
    yield 0
    yield 1
    let zipped = Seq.zip fibs (Seq.tail fibs)
    yield! Seq.map (fun (x, y) -> x + y) zipped
  }

How is fibs computed?

fibs: 0, 1, 1, 2, 3,
tail: 1, 1, 2, 3,
====================
next: 1, 2, 3,

This one prints too much because zipping fibs with its tail walks fibs twice at each step.

let fibs10 =
  fibs
  |> Seq.take 10
  |> Seq.toList
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
fibs
[0; 1; 1; 2; 3; 5; 8; 13; 21; 34]

The right way to do this would be to use Seq.pairwise instead of zipping fibs with its tail (which walks fibs twice, at each step).

Caching also helps (imagine that yield 0 in this example is very expensive).

let rec fibs' = Seq.cache (
  seq {
    printfn "fibs"
    yield 0
    yield 1
    let ps = Seq.pairwise fibs'
    yield! Seq.map (fun (x, y) -> x + y) ps
  })

let fibs10' =
  fibs'
  |> Seq.take 10
  |> Seq.toList
fibs
[0; 1; 1; 2; 3; 5; 8; 13; 21; 34]

11 · The sieve of Eratosthenes

The sieve

let rec fromN i =
  seq {
    // printfn "from: %d" i
    yield i
    yield! fromN (i + 1)
  }

let sift a sq =
  Seq.filter (fun n -> // printfn "sift %d %d" a n
                       n % a <> 0)
             sq

// sift 2 (fromN 2)
// sift 3 (fromN 2)

let rec sieve sq =
  seq {
    let p = Seq.head sq
    printfn "sieve: %d" p
    yield p
    yield! sieve (sift p (Seq.tail sq))
  }

let primes = sieve (Seq.cache (fromN 2))

let nthPrime n = Seq.item n primes

let nthPrimes =
  [ nthPrime 3
    nthPrime 10
    nthPrime 5 ]
sieve: 2
sieve: 3
sieve: 5
sieve: 7
sieve: 2
sieve: 3
sieve: 5
sieve: 7
sieve: 11
sieve: 13
sieve: 17
sieve: 19
sieve: 23
sieve: 29
sieve: 31
sieve: 2
sieve: 3
sieve: 5
sieve: 7
sieve: 11
sieve: 13
[7; 31; 13]

It matters what you cache

let primes' = Seq.cache primes
let nthPrime' n = Seq.item n primes'

let nthPrimes' =
  [ nthPrime' 5
    nthPrime' 10
    nthPrime' 5 ] // cached
sieve: 2
sieve: 3
sieve: 5
sieve: 7
sieve: 11
sieve: 13
sieve: 17
sieve: 19
sieve: 23
sieve: 29
sieve: 31
[13; 31; 13]
let nthPrime'' n =
  Seq.item n (Seq.cache primes)

let nthPrimes'' =
  [ nthPrime'' 5
    nthPrime'' 10
    nthPrime'' 5 ] // not cached
sieve: 2
sieve: 3
sieve: 5
sieve: 7
sieve: 11
sieve: 13
sieve: 2
sieve: 3
sieve: 5
sieve: 7
sieve: 11
sieve: 13
sieve: 17
sieve: 19
sieve: 23
sieve: 29
sieve: 31
sieve: 2
sieve: 3
sieve: 5
sieve: 7
sieve: 11
sieve: 13
[13; 31; 13]

Why is nthPrime'' recomputing the values although we use Seq.cache in its definition? Each call of nthPrime'' evaluates Seq.cache primes again and so creates a new, empty cache, which is gone after the call. primes' is one cache, created once and shared by every call of nthPrime'.

12 · Lazy values

What does it mean for a program to compute a result lazily? The result is computed only when explicitly asked for. The program returns what is essentially a "placeholder"; when the actual result is requested, it is computed and stored in the placeholder.

F# is eager (or strict) by default. Haskell is lazy.

let example x y =
  printfn "example"
  if x = 0
  then printfn "then"; y + 1
  else printfn "else"; x + 1

let exampleResult = example (printfn "x"; 1) (printfn "y"; 2)
x
y
example
else
2

The expression printfn "y"; 2 was evaluated before the function body. Its result was not needed, as we ended up in the else-branch.

Lazy<'T>

In F# there is an operator lazy that postpones the evaluation of the expression it is applied to until the result is needed.

If e : T, then lazy e : Lazy<T>.

The expression e under the lazy is evaluated when the result is requested.

let lz = printfn "This part is not lazy"
         lazy (printfn "Lazy part!"; 1)
This part is not lazy

Request the result of lz:

let lzValue = lz.Value
Lazy part!
1

Asking for the value again. This time nothing is printed:

let lzValue2 = lz.Value
1

We can request the result also with lz.Force ().

Our example again

let example2 (x : Lazy<int>) (y : Lazy<int>) : int =
  printfn "example"
  if x.Value = 0
  then printfn "then"; y.Value + 1
  else printfn "else"; x.Value + 1

let example2Result =
  example2 (printfn "x"; lazy (printfn "lazy-x"; 1))
           (printfn "y"; lazy (printfn "lazy-y"; 2))
x
y
example
lazy-x
else
2

"lazy-x" is printed once, although we ask for the value of x twice in the body of example2. "lazy-y" is not printed at all, as the value is not needed.

A lazy result

A slightly different example, where the result is also lazy:

let example3 (x : Lazy<int>) (y : Lazy<int>) : Lazy<int> =
  printfn "example"
  lazy (if x.Value = 0
        then printfn "then"; y.Value + 1
        else printfn "else"; x.Value + 1)

let lz2 = example3 (printfn "x"; lazy (printfn "lazy-x"; 1))
                   (printfn "y"; lazy (printfn "lazy-y"; 2))
x
y
example
let lz2Value = lz2.Value
lazy-x
else
2

What is a lazy value?

We can delay evaluation with anonymous functions taking a "dummy" argument:

type LazyInt = unit -> int

let force (l : LazyInt) : int = l ()

Compare these:

let lx : LazyInt =
  printfn "x"; fun () -> printfn "lazy-x"; 1

let ly : Lazy<int> =
  printfn "y"; lazy (printfn "lazy-y"; 1)
x
y

"lazy-x" is evaluated every time we force lx:

let lxTwice = [ force lx; force lx ]
lazy-x
lazy-x
[1; 1]
let lyTwice = [ ly.Value; ly.Value ]
lazy-y
[1; 1]

It turns out that LazyInt is not really like Lazy<int> because it does not store the computed value and recomputes it every time. It looks more like an int seq that has exactly one element.

Thread safety

What about concurrent accesses of lz.Value? How many times is the result computed? What if computing the result raises an exception? A Lazy<'T> is created with one of three modes:

open System.Threading

let exec =
  Lazy<int> ((fun () -> 1), LazyThreadSafetyMode.ExecutionAndPublication)

let pubOnly =
  Lazy<int> ((fun () -> 1), LazyThreadSafetyMode.PublicationOnly)

let noSafety =
  Lazy<int> ((fun () -> 1), LazyThreadSafetyMode.None)

13 · Lazy lists

Laziness in a data structure

Laziness in data structures: as an example we consider lists that are a little bit lazy. A value of type 'a llist is either LNil or LCons; the head and the tail of LCons are both (independently) lazy.

type 'a llist =
  | LNil
  | LCons of Lazy<'a> * Lazy<'a llist>

let l1 : int llist =
  LCons (lazy (printfn "l1-head"; 1),
         lazy (printfn "l1-tail"
               LCons (lazy (printfn "l2-head"; 2),
                      lazy (printfn "l2-tail"; LNil))))

printfn "%A" l1
LCons (Value is not created., Value is not created.)

Forcing the values

let l1Match =
  match l1 with
  | LNil -> "nil"
  | LCons (h, t) -> "tail"
"tail"
let l1Head =
  match l1 with
  | LNil -> "nil"
  | LCons (h, t) ->
      $"first element: %d{h.Value}" // h is forced
l1-head
"first element: 1"

Now l1 is a bit different:

printfn "%A" l1
LCons (1, Value is not created.)
let l1Tail =
  match l1 with
  | LNil -> "nil"
  | LCons (h, t) -> $"tail is: %A{t.Value}" // t is forced
l1-tail
"tail is: LCons (Value is not created., Value is not created.)"

Now l1 is a bit different again:

printfn "%A" l1
LCons (1, LCons (Value is not created., Value is not created.))

Operations

let rec ldown (n : int) : int llist =
  printfn "ldown %d" n
  match n with
  | 0 -> LCons (lazy 0, lazy LNil)
  | n -> LCons (lazy n, lazy ldown (n - 1))

let ls = ldown 5
ldown 5
printfn "%A" ls
LCons (Value is not created., Value is not created.)
let rec lmap (f : 'a -> 'b) (ls : 'a llist) : 'b llist =
  match ls with
  | LNil -> LNil
  | LCons (h, t) -> LCons (lazy f h.Value,
                           lazy lmap f t.Value)

let r1 = lmap (fun x -> printfn "lmap %d" x; x * 2) ls

printfn "%A" r1
LCons (Value is not created., Value is not created.)

Truncating and forcing

Truncate a lazy list to length n:

let rec ltrunc' (n : int) (ls : Lazy<'a llist>) : 'a llist =
  match n with
  | 0 -> LNil
  | n ->
      match ls.Value with
      | LNil -> LNil
      | LCons (h, t) ->
          LCons (h, lazy ltrunc' (n - 1) t)

let ltrunc (n : int) (ls : 'a llist) : 'a llist =
  ltrunc' n (lazy ls)

let t2 = ltrunc 2 r1

printfn "%A" t2
LCons (Value is not created., Value is not created.)
let rec toList (ls : 'a llist) : 'a list =
  match ls with
  | LNil         -> []
  | LCons (h, t) ->
      h.Value :: toList t.Value

let down5 =
  ldown 5
  |> toList
ldown 5
ldown 4
ldown 3
ldown 2
ldown 1
ldown 0
[5; 4; 3; 2; 1; 0]

Who decides what is computed?

Create a lazy list:

let ll5 = ldown 5
ldown 5

Compute a new lazy list:

let ltr =
  ll5
  |> lmap (fun x -> printfn "lmap %d" x; x * 2)
  |> ltrunc 2

Force the ldown (in ll5), lmap and ltrunc (in ltr) operations by converting the result ltr to a standard list:

let ltrList = toList ltr
lmap 5
ldown 4
lmap 4
[10; 8]

What is ll5 now?

printfn "%A" ll5
LCons (5, LCons (4, Value is not created.))

Converting ltr again to a list does not cause recomputation:

let ltrListAgain = toList ltr
[10; 8]

Similarly to what we saw with sequences, something later in the program, namely ltrunc 2, determined how something earlier in the program, ldown and lmap, should compute.

Filtering

lfilter forces the tail until it finds an element that satisfies p.

let rec lfilter (p : 'a -> bool) (ls : 'a llist) : 'a llist =
  match ls with
  | LNil         -> LNil
  | LCons (h, t) ->
      if p h.Value
      then LCons (h, lazy (lfilter p t.Value))
      else lfilter p t.Value

Back to our example

let input = ldown 10

let lpipeline =
  input
  |> lmap    (fun x -> printfn "lmap1: %d" x;   x + 1)
  |> lfilter (fun x -> printfn "lfilter: %d" x; x % 2 = 0)
  |> lmap    (fun x -> printfn "lmap2: %d" x;   x * 2)
  |> ltrunc 3
  |> toList
ldown 10
lmap1: 10
lfilter: 11
ldown 9
lmap1: 9
lfilter: 10
lmap2: 10
ldown 8
lmap1: 8
lfilter: 9
ldown 7
lmap1: 7
lfilter: 8
lmap2: 8
ldown 6
lmap1: 6
lfilter: 7
ldown 5
lmap1: 5
lfilter: 6
lmap2: 6
[20; 16; 12]

How does it compare to using sequences instead of lazy lists? How much of the input list was computed?

printfn "%A" input
LCons
  (10,
   LCons (9, LCons (8, LCons (7, LCons (6, LCons (5, Value is not created.))))))

Infinite lazy lists

The lazy list n, n + 1, n + 2, ...:

let rec lfrom (n : int) : int llist =
  LCons (lazy n, lazy lfrom (n + 1))

let rec lappend (xs : 'a llist)
                (ys : 'a llist) : 'a llist =
  match xs with
  | LNil         -> ys
  | LCons (h, t) ->
      LCons (h, lazy (lappend t.Value ys))

let lsngl (x : 'a) : 'a llist =
  LCons (lazy x, lazy LNil)

Append the singleton 0 to the end of the list 1, 2, 3, ..., then take the first 10 elements:

let appended =
  lappend (lfrom 1) (lsngl 0)
  |> ltrunc 10
  |> toList
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10]

We might expect that appending something to the end of an infinite list does not work, because we cannot reach the end of the infinite list. Since lappend is sufficiently lazy, this is fine.

Fibonacci numbers again

let rec lzipWith (f : 'a -> 'b -> 'c)
                 (xs : 'a llist) (ys : 'b llist) : 'c llist =
  match xs, ys with
  | LNil, LNil -> LNil
  | LCons (h1, t1), LCons (h2, t2) ->
      LCons (lazy f h1.Value h2.Value,
             lazy lzipWith f t1.Value t2.Value)
  | _, _ -> LNil

let ltail (ls : 'a llist) : 'a llist =
  match ls with
  | LNil         -> LNil
  | LCons (h, t) -> t.Value

let rec lfibs =
  LCons (lazy 0,
         lazy (LCons (lazy 1,
                      lazy lzipWith (+) lfibs (ltail lfibs))))

let lfibs10 =
  lfibs
  |> ltrunc 10
  |> toList
[0; 1; 1; 2; 3; 5; 8; 13; 21; 34]
printfn "%A" lfibs
LCons
  (0,
   LCons
  (1,
   LCons
  (1,
   LCons
  (2,
   LCons
  (3,
   LCons (5, LCons (8, LCons (13, LCons (21, LCons (34, Value is not created.))))))))))

lfibs is a lazy list that is infinite: if we ask for the next value in the list, it will compute it. Unlike with sequences, a forced tail of a lazy list stays in memory as a cons cell. Similarly, we need to be careful not to do something like this:

toList lfibs

This is fine:

let lfibs100 = toList (ltrunc 100 lfibs)
[0; 1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; 144; 233; 377; 610; 987; 1597; 2584;
 4181; 6765; 10946; 17711; 28657; 46368; 75025; 121393; 196418; 317811; 514229;
 832040; 1346269; 2178309; 3524578; 5702887; 9227465; 14930352; 24157817;
 39088169; 63245986; 102334155; 165580141; 267914296; 433494437; 701408733;
 1134903170; 1836311903; -1323752223; 512559680; -811192543; -298632863;
 -1109825406; -1408458269; 1776683621; 368225352; 2144908973; -1781832971;
 363076002; -1418756969; -1055680967; 1820529360; 764848393; -1709589543;
 -944741150; 1640636603; 695895453; -1958435240; -1262539787; 1073992269;
 -188547518; 885444751; 696897233; 1582341984; -2015728079; -433386095;
 1845853122; 1412467027; -1036647147; 375819880; -660827267; -285007387;
 -945834654; -1230842041; 2118290601; 887448560; -1289228135; -401779575;
 -1691007710; -2092787285; 511172301; -1581614984; -1070442683; 1642909629;
 572466946; -2079590721; -1507123775; 708252800; -798870975; -90618175;
 -889489150]

From the element at index 47 on, the numbers are wrong: they no longer fit in an int, and int addition wraps around silently.

14 · Lazy initialisation

The init function for arrays:

let doubles = Array.init 10 (fun i -> i * 2)
[|0; 2; 4; 6; 8; 10; 12; 14; 16; 18|]

A table of lazy values

An array of Lazy<int> values, each a (lazy) constant or computed from values at smaller indices in the same array:

let rec lazyTbl : Lazy<int> array =
  function
  | 0 -> lazy 0
  | 1 -> lazy 1
  | i when i % 2 = 0 -> lazy (1 + lazyTbl[i - 2].Value)
  | i                -> lazy (2 * lazyTbl[i - 2].Value)
  |> Array.init 10

printfn "%A" lazyTbl
[|Value is not created.; Value is not created.; Value is not created.;
  Value is not created.; Value is not created.; Value is not created.;
  Value is not created.; Value is not created.; Value is not created.;
  Value is not created.|]
printfn "%A" lazyTbl[7]
Value is not created.
let entry7Value = lazyTbl[7].Value
8

Some other entries in the table were also computed:

printfn "%A" lazyTbl
[|Value is not created.; 1; Value is not created.; 2; Value is not created.; 4;
  Value is not created.; 8; Value is not created.; Value is not created.|]

We did not need to first initialise the table with some special values (e.g. -1) and then go over the table again to compute certain entries.

15 · Puzzle: is lmap tail recursive?

lmap and map

let rec lmap (f : 'a -> 'b) (ls : 'a llist)  : 'b llist =
  match ls with
  | LNil -> LNil
  | LCons (h, t) -> LCons (lazy f h.Value,
                           lazy lmap f t.Value)

Let's compare it with map for ordinary lists in the same style. Is it tail recursive?

let rec map f xs =
  match xs with
  | []      -> []
  | x :: xs -> f x :: map f xs

ldown without the printfn. Is it tail recursive?

let rec ldown' (n : int) : int llist =
  match n with
  | 0 -> LCons (lazy 0, lazy LNil)
  | n -> LCons (lazy n, lazy ldown' (n - 1))

Force a lazy list:

let toList' (ls : 'a llist) : 'a list =
  let rec go (ls : 'a llist) (acc : 'a list) =
    match ls with
    | LNil         -> List.rev acc
    | LCons (h, t) -> go t.Value (h.Value :: acc)

  go ls []

Which one handles a larger list?

Build a large lazy list, and an ordinary list with the same elements:

let ls1 = ldown' 10_000

let xs1 = [10_000 .. -1 .. 0]

lmap over the large lazy list and force it; map (not tail recursively) over the large list:

let ls2 = ls1 |> lmap ((*) 2) |> toList'

let xs2 = map ((*) 2) xs1

let lengths = (List.length ls2, List.length xs2)
(10001, 10001)

Both work. Now increase the number of elements. With 1 000 000 elements:

> let ls1 = ldown' 1_000_000;;
> let xs1 = [1_000_000 .. -1 .. 0];;
> let ls2 = ls1 |> lmap (( * ) 2) |> toList';;
> List.length ls2;;
val it: int = 1000001

> let xs2 = map (( * ) 2) xs1;;
Stack overflow.
Repeated 130777 times:
--------------------------------
   at FSI_0002.map[[System.Int32, …],[System.Int32, …]](…)
--------------------------------

Which one of these, lmap or map, can handle a larger list? Why?

Summary

Reading and next week

Next week: events and asynchronous computations.

val listResult: int list
Multiple items
module List from Microsoft.FSharp.Collections

--------------------
type List<'T> = | op_Nil | op_ColonColon of Head: 'T * Tail: 'T list interface IReadOnlyList<'T> interface IReadOnlyCollection<'T> interface IEnumerable interface IEnumerable<'T> member GetReverseIndex: rank: int * offset: int -> int member GetSlice: startIndex: int option * endIndex: int option -> 'T list static member Cons: head: 'T * tail: 'T list -> 'T list member Head: 'T member IsEmpty: bool member Item: index: int -> 'T with get ...
val map: mapping: ('T -> 'U) -> list: 'T list -> 'U list
val x: int
val printfn: format: Printf.TextWriterFormat<'T> -> 'T
val filter: predicate: ('T -> bool) -> list: 'T list -> 'T list
val truncate: count: int -> list: 'T list -> 'T list
val listAll: int list
val foldResult: int list
val fold<'T,'State> : folder: ('State -> 'T -> 'State) -> state: 'State -> list: 'T list -> 'State
val c: int
val r: int list
val x': int
val x'': int
val snd: tuple: ('T1 * 'T2) -> 'T2
val rev: list: 'T list -> 'T list
val seqResult: int list
module Seq from Microsoft.FSharp.Collections
val map: mapping: ('T -> 'U) -> source: 'T seq -> 'U seq
val filter: predicate: ('T -> bool) -> source: 'T seq -> 'T seq
val truncate: count: int -> source: 'T seq -> 'T seq
val toList: source: 'T seq -> 'T list
val evenNums: int seq
Multiple items
val int: value: 'T -> int (requires member op_Explicit)

--------------------
type int = int32

--------------------
type int<'Measure> = int
Multiple items
val seq: sequence: 'T seq -> 'T seq

--------------------
type 'T seq = System.Collections.Generic.IEnumerable<'T>
val initInfinite: initializer: (int -> 'T) -> 'T seq
val i: int
val item5: int
val item: index: int -> source: 'T seq -> 'T
val first10: int seq
val first10List: int list
val evenNums': int seq
val res: int list
val res': int seq
val item1: int
val item1Again: int
val s1: int seq
val s2: int seq
val unfold: generator: ('State -> ('T * 'State) option) -> state: 'State -> 'T seq
union case Option.Some: Value: 'T -> Option<'T>
val s1First10: int list
val s2First10: int list
val s1Item5: int
val s2Item5: int
val s: int * int
val obs: x: 'a * y: 'b -> 'a
val x: 'a
val y: 'b
val next: x: int * y: int -> int * int
val y: int
val observed: int list
val unfolded: int list
namespace System
namespace System.Collections
namespace System.Collections.Generic
val evenEnumerator: unit -> IEnumerator<int>
Multiple items
type IEnumerator = override MoveNext: unit -> bool override Reset: unit -> unit member Current: obj
<summary>Supports a simple iteration over a non-generic collection.</summary>

--------------------
type IEnumerator<'T (allows ref struct)> = inherit IEnumerator inherit IDisposable member Current: 'T
<summary>Supports a simple iteration over a generic collection.</summary>
<typeparam name="T">The type of objects to enumerate.</typeparam>
val mutable i: int
val box: value: 'T -> objnull
type IDisposable = override Dispose: unit -> unit
<summary>Provides a mechanism for releasing unmanaged resources.</summary>
val e: IEnumerator<int>
val firstTwo: int list
IEnumerator.MoveNext() : bool
val ignore: value: 'T -> unit
property IEnumerator.Current: int with get
<summary>Gets the element in the collection at the current position of the enumerator.</summary>
<returns>The element in the collection at the current position of the enumerator.</returns>
val nextTwo: int list
System.IDisposable.Dispose() : unit
val s3: IEnumerable<int>
Multiple items
type IEnumerable = override GetEnumerator: unit -> IEnumerator
<summary>Exposes an enumerator, which supports a simple iteration over a non-generic collection.</summary>

--------------------
type IEnumerable<'T (allows ref struct)> = inherit IEnumerable override GetEnumerator: unit -> IEnumerator<'T>
<summary>Exposes the enumerator, which supports a simple iteration over a collection of a specified type.</summary>
<typeparam name="T">The type of objects to enumerate.</typeparam>
val s3Item5: int
val s3First3: int list
val skipped: int list
val skip: count: int -> source: 'T seq -> 'T seq
val fromEnumerator: make: (unit -> IEnumerator<'a>) -> 'a seq
val make: (unit -> IEnumerator<'a>)
type unit = Unit
'a
Multiple items
val seq: sequence: 'T seq -> 'T seq

--------------------
type 'T seq = IEnumerable<'T>
val myFilter: p: ('a -> bool) -> xs: 'a seq -> 'a seq
val p: ('a -> bool)
type bool = System.Boolean
val xs: 'a seq
val source: IEnumerator<'a>
IEnumerable.GetEnumerator() : IEnumerator<'a>
property IEnumerator.Current: 'a with get
<summary>Gets the element in the collection at the current position of the enumerator.</summary>
<returns>The element in the collection at the current position of the enumerator.</returns>
val mutable found: bool
IEnumerator.Reset() : unit
val numbers: int seq
val filteredOwn: int list
val filteredLib: int list
val pairsZip: (int * int) list
val zip: source1: 'T1 seq -> source2: 'T2 seq -> ('T1 * 'T2) seq
val tail: source: 'T seq -> 'T seq
val myPairwise: xs: 'a seq -> ('a * 'a) seq
val mutable previous: 'a option
union case Option.None: Option<'T>
val mutable pair: ('a * 'a) option
module Option from Microsoft.FSharp.Core
val get: option: 'T option -> 'T
val isNone: option: 'T option -> bool
val y: 'a
val pairsOwn: (int * int) list
val xs: int list
val xsSeq: int seq
val nats: int seq
val natsItems: int list
val cachedNats: int seq
val cache: source: 'T seq -> 'T seq
val cachedNatsItems: int list
val roots: a: float -> float seq
val a: float
val step: a: float -> xn: float -> float
val xn: float
val roots10: float list
val pairs: (int * int) list
val pairwise: source: 'T seq -> ('T * 'T) seq
val root10: float
val skipWhile: predicate: ('T -> bool) -> source: 'T seq -> 'T seq
val r1: float
val r2: float
val abs: value: 'T -> 'T (requires member Abs)
val head: source: 'T seq -> 'T
val s123a: int seq
val s123b: int seq
val s123c: int seq
val s123abc: int list list
val three: int seq
val init: count: int -> initializer: (int -> 'T) -> 'T seq
val s123d: int seq
val s123dItems: int list
val s123dList: int list
val s123e: int seq
val s123eList: int list
val ex1: int seq
val ex1First: int list
val ex1All: int list
val seqLet: int list
val r: int
val seqFor: int list
val seqIf: int list
val from: i: int -> int seq
val from5: int list
val fromBad: i: int -> int seq
val append: source1: 'T seq -> source2: 'T seq -> 'T seq
val singleton: value: 'T -> 'T seq
val from': i: int -> int seq
val delay: generator: (unit -> 'T seq) -> 'T seq
val from'': i: int -> int seq
val from5': int list
val f5': int seq
val f5'Item1: int
val f5'': int seq
val f5''Item1: int
val fibs: int seq
val zipped: (int * int) seq
val fibs10: int list
val take: count: int -> source: 'T seq -> 'T seq
val fibs': int seq
val ps: (int * int) seq
val fibs10': int list
val fromN: i: int -> int seq
val sift: a: int -> sq: int seq -> int seq
val a: int
val sq: int seq
val n: int
val sieve: sq: int seq -> int seq
val p: int
val primes: int seq
val nthPrime: n: int -> int
val nthPrimes: int list
val primes': int seq
val nthPrime': n: int -> int
val nthPrimes': int list
val nthPrime'': n: int -> int
val nthPrimes'': int list
val example: x: int -> y: int -> int
val exampleResult: int
val lz: Lazy<int>
val lzValue: int
property System.Lazy.Value: int with get
val lzValue2: int
val example2: x: Lazy<int> -> y: Lazy<int> -> int
val x: Lazy<int>
Multiple items
active recognizer Lazy: Lazy<'T> -> 'T

--------------------
type Lazy<'T> = System.Lazy<'T>
val y: Lazy<int>
val example2Result: int
val example3: x: Lazy<int> -> y: Lazy<int> -> Lazy<int>
val lz2: Lazy<int>
val lz2Value: int
type LazyInt = unit -> int
val force: l: LazyInt -> int
val l: LazyInt
val lx: LazyInt
val ly: Lazy<int>
val lxTwice: int list
val lyTwice: int list
namespace System.Threading
val exec: Lazy<int>
type LazyThreadSafetyMode = | None = 0 | PublicationOnly = 1 | ExecutionAndPublication = 2
<summary>Specifies how a <see cref="T:System.Lazy`1" /> instance synchronizes access among multiple threads.</summary>
field LazyThreadSafetyMode.ExecutionAndPublication: LazyThreadSafetyMode = 2
val pubOnly: Lazy<int>
field LazyThreadSafetyMode.PublicationOnly: LazyThreadSafetyMode = 1
val noSafety: Lazy<int>
field LazyThreadSafetyMode.None: LazyThreadSafetyMode = 0
type 'a llist = | LNil | LCons of Lazy<'a> * Lazy<'a llist>
val l1: int llist
union case llist.LCons: Lazy<'a> * Lazy<'a llist> -> 'a llist
union case llist.LNil: 'a llist
val l1Match: string
val h: Lazy<int>
val t: Lazy<int llist>
val l1Head: string
val l1Tail: string
property System.Lazy.Value: int llist with get
val ldown: n: int -> int llist
val ls: int llist
val lmap: f: ('a -> 'b) -> ls: 'a llist -> 'b llist
val f: ('a -> 'b)
'b
val ls: 'a llist
val h: Lazy<'a>
val t: Lazy<'a llist>
property System.Lazy.Value: 'a with get
property System.Lazy.Value: 'a llist with get
val r1: int llist
val ltrunc': n: int -> ls: Lazy<'a llist> -> 'a llist
val ls: Lazy<'a llist>
val ltrunc: n: int -> ls: 'a llist -> 'a llist
val t2: int llist
val toList: ls: 'a llist -> 'a list
type 'T list = List<'T>
val down5: int list
val ll5: int llist
val ltr: int llist
val ltrList: int list
val ltrListAgain: int list
val lfilter: p: ('a -> bool) -> ls: 'a llist -> 'a llist
val input: int llist
val lpipeline: int list
val lfrom: n: int -> int llist
val lappend: xs: 'a llist -> ys: 'a llist -> 'a llist
val xs: 'a llist
val ys: 'a llist
val lsngl: x: 'a -> 'a llist
val appended: int list
val lzipWith: f: ('a -> 'b -> 'c) -> xs: 'a llist -> ys: 'b llist -> 'c llist
val f: ('a -> 'b -> 'c)
'c
val ys: 'b llist
val h1: Lazy<'a>
val t1: Lazy<'a llist>
val h2: Lazy<'b>
val t2: Lazy<'b llist>
property System.Lazy.Value: 'b with get
property System.Lazy.Value: 'b llist with get
val ltail: ls: 'a llist -> 'a llist
val lfibs: int llist
val lfibs10: int list
val lfibs100: int list
val doubles: int array
module Array from Microsoft.FSharp.Collections
val init: count: int -> initializer: (int -> 'T) -> 'T array
val lazyTbl: Lazy<int> array
type 'T array = 'T array
val entry7Value: int
val map: f: ('a -> 'b) -> xs: 'a list -> 'b list
val xs: 'a list
val ldown': n: int -> int llist
val toList': ls: 'a llist -> 'a list
val go: ls: 'a llist -> acc: 'a list -> 'a list
val acc: 'a list
Multiple items
type List<'T> = interface ICollection<'T> interface seq<'T> interface IEnumerable interface IList<'T> interface IReadOnlyCollection<'T> interface IReadOnlyList<'T> interface ICollection interface IList new: unit -> unit + 2 overloads member Add: item: 'T -> unit ...
<summary>Represents a strongly typed list of objects that can be accessed by index. Provides methods to search, sort, and manipulate lists.</summary>
<typeparam name="T">The type of elements in the list.</typeparam>


--------------------
List() : List<'T>
List(collection: 'T seq) : List<'T>
List(capacity: int) : List<'T>
val ls1: int llist
val xs1: int list
val ls2: int list
val xs2: int list
val lengths: int * int
val length: list: 'T list -> int