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
|
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
|
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
|
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
|
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
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?
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
|
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
|
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
|
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
let s2Item5 = Seq.item 5 s2
s2: 0
s2: 1
s2: 2
s2: 3
s2: 4
s2: 5
|
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)))))) ]
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:
f s evaluates to None: there are no elements in this sequence;
-
f s evaluates to Some (x, s'): the first element of the sequence
is x, and the rest of the sequence is Seq.unfold f s'.
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:
- What is the current element?
- Is there a next element?
- 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
|
let nextTwo =
[ for _ in 1 .. 2 do
e.MoveNext () |> ignore
e.Current ]
MoveNext
Current: 2
MoveNext
Current: 3
|
e.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
|
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
|
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
|
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
|
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
|
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 ]
let cachedNats = Seq.cache nats
let cachedNatsItems =
[ Seq.item 3 cachedNats
Seq.item 5 cachedNats
Seq.item 3 cachedNats ]
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
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:
yield x adds x to the generated sequence;
yield! xs adds the elements of xs one by one to the 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 ]
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
You can sometimes omit yield (but not yield!):
let s123e =
seq {
1
2
3
}
let s123eList = Seq.toList s123e
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
let ex1All = Seq.toList ex1
let, for and if
let pat = exp followed by seqexp:
let seqLet =
seq {
let r = 3
yield! [0 .. r]
}
|> Seq.toList
for pat in exp do seqexp:
let seqFor =
seq {
for x in [1 .. 3] do
yield! [x; x - 1]
}
|> Seq.toList
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
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'
let f5'' = from'' 5
let f5''Item1 = Seq.item 1 f5''
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
[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
|
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
|
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
|
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)
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)
Request the result of lz:
let lzValue = lz.Value
Asking for the value again. This time nothing is printed:
let lzValue2 = lz.Value
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))
"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))
let lz2Value = lz2.Value
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)
"lazy-x" is evaluated every time we force lx:
let lxTwice = [ force lx; force lx ]
let lyTwice = [ ly.Value; ly.Value ]
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"
let l1Head =
match l1 with
| LNil -> "nil"
| LCons (h, t) ->
$"first element: %d{h.Value}" // h is forced
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
"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
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
|
Who decides what is computed?
Create a lazy list:
let ll5 = 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
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
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
|
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:
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]
let entry7Value = lazyTbl[7].Value
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)
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
-
A sequence is a description of how to compute values (not a data
structure; does not store computed values).
-
A lazy list is a data structure whose construction has been
suspended.
- Sequences and lazy lists both compute elements on demand (pull-based).
- Allow us to construct programs by composing smaller programs; only compute what is necessary (on demand).
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