Like an onion that would go on forever as we peel off layer after layer, streams are like lazy lists, but without a base case:
type 'a stream =
| Scons of 'a * 'a stream Lazy.t;;
Analysis:
there is no base case, and therefore a stream is like a list that is constructed lazily and that goes on forever; and
Scons is a binary constructor that, given
constructs a stream that starts with v and whose tail is not computed yet.
Matching the binary structure of streams, and the arity of the stream constructor Scons, there are two canonical stream accessors: shd, to fetch their head, and stl, to fetch their tail:
let shd s =
(* shd : 'a stream -> 'a *)
match s with
| Scons (v, _) ->
v;;
let stl s =
(* stl : 'a stream -> 'a stream *)
match s with
| Scons (_, ds) ->
Lazy.force ds;;
More concisely, since there is only one constructor, we can define the two accessors without match-expressions:
let shd (Scons (v, _)) =
(* shd : 'a stream -> 'a *)
v;;
let stl (Scons (_, ds)) =
(* stl : 'a stream -> 'a stream *)
Lazy.force ds;;
Here is a handy function to construct a stream:
let make_stream seed next =
(* make_stream : 'a -> ('a -> 'a) -> 'a stream *)
let rec produce v =
(* produce : 'a -> 'a stream *)
Scons (v, lazy (produce (next v)))
in produce seed;;
Given an initial seed x and a next function f, make_stream essentially yields:
Scons (x,
lazy (Scons (f x,
lazy (Scons (f (f x),
lazy (Scons (f (f (f x)),
lazy (Scons (f (f (f (f x))),
lazy ...)))))))))
In words, it yields
a stream whose head is x and whose tail, when forced, is
a stream whose head is f x and whose tail, when forced, is
a stream whose head is f (f x) and whose tail, when forced, is
a stream whose head is f (f (f x)) and whose tail, when forced, is
a stream whose head is f (f (f (f x))) and whose tail, when forced, is
a stream ...
In actuality though, because OCaml follows call by value, given an initial seed x0 and a next function f, make_stream actually yields:
Scons (x0, lazy (let x1 = f x0
in Scons (x1, lazy (let x2 = f x1
in Scons (x2, lazy (let x3 = f x2
in Scons (x3, lazy (let x4 = f x3
in Scons (x4, lazy ...)))))))))
For a first example, here is the increasing stream of non-negative integers:
let nats = make_stream 0 succ;;
Indeed nats denotes
a stream whose head is 0 and whose tail, when forced, is
a stream whose head is 1 (i.e., the result of applying succ to 0) and whose tail, when forced, is
a stream whose head is 2 (i.e., the result of applying succ to 1) and whose tail, when forced, is
a stream whose head is 3 (i.e., the result of applying succ to 2) and whose tail, when forced, is
a stream whose head is 4 (i.e., the result of applying succ to 3) and whose tail, when forced, is
a stream ...
Concretely:
let test_nats candidate =
match candidate with
| Scons (0, s1) ->
(match Lazy.force s1 with
| Scons (1, s2) ->
(match Lazy.force s2 with
| Scons (2, s3) ->
(match Lazy.force s3 with
| Scons (3, s4) ->
(match Lazy.force s4 with
| Scons (4, s5) ->
true
| _ ->
false)
| _ ->
false)
| _ ->
false)
| _ ->
false)
| _ ->
false;;
In OCaml:
let nats = make_stream 0 succ;;
The implementation passes the unit test:
# test_nats nats;;
- : bool = true
#
Implement the decreasing stream of non-positive integers, unit-test function and all.
This stream denotes
a stream whose head is 0 and whose tail, when forced, is
a stream whose head is -1 and whose tail, when forced, is
a stream whose head is -2 and whose tail, when forced, is
a stream whose head is -3 and whose tail, when forced, is
a stream whose head is -4 and whose tail, when forced, is
a stream ...
Here is the increasing stream of positive integers:
let posints = make_stream 1 succ;;
Indeed posints denotes
a stream whose head is 1 and whose tail, when forced, is
a stream whose head is 2 (i.e., the result of applying succ to 1) and whose tail, when forced, is
a stream whose head is 3 (i.e., the result of applying succ to 2) and whose tail, when forced, is
a stream whose head is 4 (i.e., the result of applying succ to 3) and whose tail, when forced, is
a stream whose head is 5 (i.e., the result of applying succ to 4) and whose tail, when forced, is
a stream ...
Concretely:
let test_posints candidate =
match candidate with
| Scons (1, s2) ->
(match Lazy.force s2 with
| Scons (2, s3) ->
(match Lazy.force s3 with
| Scons (3, s4) ->
(match Lazy.force s4 with
| Scons (4, s5) ->
true
| _ ->
false)
| _ ->
false)
| _ ->
false)
| _ ->
false;;
The implementation passes the unit test:
# test_posints posints
- : bool = true
#
Implement the decreasing stream of negative integers, unit-test function and all.
Here is the increasing stream of even non-negative integers:
let evens = make_stream 0 (fun i -> i + 2);;
Indeed evens denotes
a stream whose head is 0 and whose tail, when forced, is
a stream whose head is 2 (i.e., the result of applying fun i -> i + 2 to 0) and whose tail, when forced, is
a stream whose head is 4 (i.e., the result of applying fun i -> i + 2 to 2) and whose tail, when forced, is
a stream whose head is 6 (i.e., the result of applying fun i -> i + 2 to 4) and whose tail, when forced, is
a stream whose head is 8 (i.e., the result of applying fun i -> i + 2 to 6) and whose tail, when forced, is
a stream ...
Concretely:
let test_evens candidate =
match candidate with
| Scons (0, s1) ->
(match Lazy.force s1 with
| Scons (2, s2) ->
(match Lazy.force s2 with
| Scons (4, s3) ->
(match Lazy.force s3 with
| Scons (6, s4) ->
(match Lazy.force s4 with
| Scons (8, s5) ->
true
| _ ->
false)
| _ ->
false)
| _ ->
false)
| _ ->
false)
| _ ->
false;;
The implementation passes the unit test:
# test_evens evens;;
- : bool = true
#
Implement the increasing stream of even positive integers, unit-test function and all.
Implement the decreasing stream of even non-positive integers, unit-test function and all.
Implement the decreasing stream of even negative integers, unit-test function and all.
Here is the increasing stream of odd positive integers:
let odds = make_stream 1 (fun i -> i + 2);;
Indeed odds denotes
a stream whose head is 1 and whose tail, when forced, is
a stream whose head is 3 (i.e., the result of applying fun i -> i + 2 to 1) and whose tail, when forced, is
a stream whose head is 5 (i.e., the result of applying fun i -> i + 2 to 3) and whose tail, when forced, is
a stream whose head is 7 (i.e., the result of applying fun i -> i + 2 to 5) and whose tail, when forced, is
a stream whose head is 9 (i.e., the result of applying fun i -> i + 2 to 7) and whose tail, when forced, is
a stream ...
Concretely:
let test_odds candidate =
match candidate with
| Scons (1, s1) ->
(match Lazy.force s1 with
| Scons (3, s2) ->
(match Lazy.force s2 with
| Scons (5, s3) ->
(match Lazy.force s3 with
| Scons (7, s4) ->
(match Lazy.force s4 with
| Scons (9, s5) ->
true
| _ ->
false)
| _ ->
false)
| _ ->
false)
| _ ->
false)
| _ ->
false;;
The implementation passes the unit test:
# test_odds odds;;
- : bool = true
#
Implement the decreasing stream of odd negative integers, unit-test function and all.
To merge two streams, we successively peel one layer of each, and construct the resulting stream, recursively:
let rec merge_stream (Scons (v1, s1)) (Scons (v2, s2)) =
(* merge_stream : 'a stream -> 'a stream -> 'a stream *)
Scons (v1,
lazy (Scons (v2,
lazy (merge_stream (Lazy.force s1)
(Lazy.force s2)))));;
Observe how
And indeed we can check that merging evens and odds yields (the beginning of) the stream of natural numbers:
# test_nats (merge_stream evens odds);;
- : bool = true
#
Implement an OCaml function stream_nth that, given a stream and an offset, yields the element in this stream at that offset:
let test_stream_nth_int candidate =
let b0 = (candidate nats 0 = 0)
and b1 = (candidate nats 10 = 10)
and b2 = (candidate evens 10 = 20)
and b3 = (candidate evens 100 = 200)
and b4 = (candidate odds 10 = 21)
and b5 = (candidate odds 100 = 201)
(* etc. *)
in b0 && b1 && b2 && b3 && b4 && b5;;
Explain why this unit-test function makes sense, and flesh it out.
The unit-test function makes sense because of the way these streams have been constructed:
So the unit-test function can be fleshed out with random numbers:
let test_stream_nth_int candidate =
let b0 = (candidate nats 0 = 0)
and b1 = (candidate nats 10 = 10)
and b2 = (candidate evens 10 = 20)
and b3 = (candidate evens 100 = 200)
and b4 = (candidate odds 10 = 21)
and b5 = (candidate odds 100 = 201)
(* new: *)
and b6 = let i = Random.int 1000
in candidate nats i = i
and b7 = let i = Random.int 1000
in candidate evens i = 2 * i
and b8 = let i = Random.int 1000
in candidate odds i = 2 * i + 1
(* etc. *)
in b0 && b1 && b2 && b3 && b4 && b5 && b6 && b7 && b8;;
For the rest, this indexing function is specified inductively over the index n:
base case: n = 0
given a stream Scons (v, s'), indexing it at 0 should yield v
induction step: n = succ n'
given a stream s', and under the induction hypothesis that indexing it at n' yields v', then for any value v, indexing Scons (v, lazy s') at index succ n' should also yield v
In OCaml:
let stream_nth s n =
(* stream_nth : 'a stream -> int -> 'a *)
assert (n >= 0);
let rec loop n (Scons (v, s')) =
if n = 0
then v
else loop (pred n) (Lazy.force s')
in loop n s;;
The implementation passes the unit test:
# test_stream_nth_int stream_nth;;
- : bool = true
#
Implement an OCaml function prefix_stream that, given a stream and an offset, yields a list that is the prefix of this stream prior to this offset:
let test_prefix_stream_int candidate =
let b0 = (candidate nats 0 = [])
and b1 = (candidate nats 5 = [0; 1; 2; 3; 4])
and b2 = (candidate evens 4 = [0; 2; 4; 6])
and b3 = (candidate odds 6 = [1; 3; 5; 7; 9; 11])
(* etc. *)
in b0 && b1 && b2 && b3;;
Explain why this unit-test function makes sense, and flesh it out.
The unit-test function makes sense because of the way these streams have been constructed:
So the unit-test function can be fleshed out with random numbers, using iota, which maps any non-negative integer n to the list of the first n natural numbers (see Section A converse of atoi: iota):
let iota n_init =
(* iota : int -> int list *)
let rec visit n a =
match n with
| 0 ->
a
| _ ->
let n' = pred n
in visit n' (n' :: a)
in visit n_init [];;
let test_prefix_stream_int candidate =
let b0 = (candidate nats 0 = [])
and b1 = (candidate nats 5 = [0; 1; 2; 3; 4])
and b2 = (candidate evens 4 = [0; 2; 4; 6])
and b3 = (candidate odds 6 = [1; 3; 5; 7; 9; 11])
(* new *)
and b4 = let n = Random.int 1000
in candidate nats n = iota n
and b5 = let n = Random.int 1000
in candidate evens n = List.map (fun i -> 2 * i) (iota n)
and b6 = let n = Random.int 1000
in candidate odds n = List.map (fun i -> 2 * i + 1) (iota n)
(* etc. *)
in b0 && b1 && b2 && b3 && b4 && b5 && b6;;
For the rest, this prefixing function is specified inductively over the index n:
base case: n = 0
given a stream s, prefixing it at 0 should yield []
induction step: n = succ n'
given a stream s', and under the induction hypothesis that prefixing it at n' yields vs', then for any value v, prefixing Scons (v, lazy s') at index succ n' should yield v :: vs'
In OCaml:
let prefix_stream s n =
(* prefix_stream : 'a stream -> int -> 'a list *)
assert (n >= 0);
let rec visit n (Scons (v, s')) =
if n = 0
then []
else let ih = visit (pred n) (Lazy.force s')
in v :: ih
in visit n s;;
The implementation passes the unit test:
# test_prefix_stream_int prefix_stream;;
- : bool = true
#
Implement an OCaml function stream_prepend that, given a list and a stream, prepends the elements of this list onto this stream:
let test_stream_prepend_int candidate =
let test vs s vs_s =
let n = List.length vs
in prefix_stream vs_s n = vs
in let b0 = test [] nats nats
and b1 = test [-1] nats (Scons (-1, lazy nats))
and b2 = test [-2; -1] nats (Scons (-2, lazy (Scons (-1, lazy nats))))
and b3 = test [-3; -2; -1] nats (Scons (-3, lazy (Scons (-2, lazy (Scons (-1, lazy nats))))))
in b0 && b1 && b2 && b3;;
Explain why this unit-test function makes sense, and flesh it out.
The point of the unit-test function is to test whether, given a stream vs_s that is the result of prepending a list vs onto a stream s, the prefix of vs_s is vs.
This unit-test function can be expanded to test whether, given a stream vs_s that is the result of prepending a list vs onto a stream s, the prefix of vs_s is vs and then vs_s is continued with the elements of s:
let expanded_test_stream_prepend_int candidate =
let new_test vs s vs_s =
let n = List.length vs
in let x = Random.int 100
in prefix_stream vs_s (n + x) = vs @ prefix_stream s x
in let b0 = new_test [] nats nats
and b1 = new_test [-1] nats (Scons (-1, lazy nats))
and b2 = new_test [-2; -1] nats (Scons (-2, lazy (Scons (-1, lazy nats))))
and b3 = new_test [-3; -2; -1] nats (Scons (-3, lazy (Scons (-2, lazy (Scons (-1, lazy nats))))))
in b0 && b1 && b2 && b3;;
For the rest, this prepending function is specified inductively over the list vs:
base case: vs = []
prepending the empty list to any given stream should yield this stream
induction step: vs = v :: vs'
given a stream s, and under the induction hypothesis that prepending vs' to s yields the stream s', prepending v :: vs' to s should yield Scons (v, lazy ih)
In OCaml:
let stream_prepend vs s =
let rec visit vs s =
match vs with
| [] ->
s
| v :: vs' ->
let ih = visit vs' s
in Scons (v, lazy ih)
in visit vs s;;
The implementation passes both unit tests:
# test_stream_prepend_int stream_prepend;;
- : bool = true
# expanded_test_stream_prepend_int stream_prepend;;
- : bool = true
#
Implement an OCaml function compare_stream_prefixes that, given two streams and an offset n, compares whether the n first successive elements of these two streams are equal:
let test_compare_stream_prefixes candidate =
let b0 = (let n = Random.int 100
in candidate nats nats n = true)
and b1 = (let n = Random.int 100
in candidate evens odds (succ n) = false)
(* etc. *)
in b0 && b1;;
Explain why this unit-test function makes sense, and flesh it out.
Here is a simple implementation:
let compare_stream_prefixes_v0 s1 s2 n =
prefix_stream s1 n = prefix_stream s2 n;;
This implementation passes the unit tests:
# test_compare_stream_prefixes compare_stream_prefixes_v0;;
- : bool = true
#
This implementation constructs two intermediate lists (using prefix_stream) and then compares them. Yours should not construct any intermediate lists.
Implement an OCaml function stream_suffix that, given a stream and an offset, yields a stream that is the suffix of this stream beyond this offset:
let test_stream_suffix_int candidate =
let b0 = (let n = Random.int 100
in prefix_stream (candidate nats 0) n = prefix_stream nats n)
and b1 = (let n = Random.int 100
in prefix_stream (candidate nats 1) n = prefix_stream posints n)
(* etc. *)
in b0 && b1;;
Explain why this unit-test function makes sense, and flesh it out.
Using make_stream, implement a stream that starts with 1, continues with -1, and then with 1, and then with -1, etc.:
let test_one_and_minus_one_star candidate_stream =
(prefix_stream candidate_stream 10 = [1; -1; 1; -1; 1; -1; 1; -1; 1; -1]);;
Using make_stream, implement a stream that starts with 0, continues with 1, and then with 0, and then with 1, etc.:
let test_zero_and_one_star candidate_stream =
(prefix_stream candidate_stream 10 = [0; 1; 0; 1; 0; 1; 0; 1; 0; 1]);;
Using make_stream, implement a stream that starts with 0, continues with -1, and then with 0, and then with -1, etc.:
let test_zero_and_minus_one_star candidate_stream =
(prefix_stream candidate_stream 10 = [0; -1; 0; -1; 0; -1; 0; -1; 0; -1]);;
Using make_stream, implement a stream that starts with 0, continues with -1, and then with 2, and then with -3, etc.:
let test_interleaved_negative_and_positive_nats candidate_stream =
(prefix_stream candidate_stream 10 = [0; -1; 2; -3; 4; -5; 6; -7; 8; -9]);;
Using make_stream, implement a stream that starts with 0, continues with -1, and then with 1, and then with -2, and then with 2, and then with -3, and then with 3, etc.:
let test_interleaved_ints candidate_stream =
(prefix_stream candidate_stream 10 = [0; -1; 1; -2; 2; -3; 3; -4; 4; -5]);;
Implement an OCaml function append_stream that, given two streams, prepends the first to the second and yields the resulting stream.
If you get confused by this exercise, here is a beautiful story to take your mind off things, because sometimes that’s what it takes.
Once upon a time, in a small village far, far away, there was a happy drunkard. He dressed properly, worked dutifully if humbly, and was kind to children and to his neighbors as well as to small animals. Come every evening, he would hit the bottle, and after nursing it until its last drop, he would take a happy stroll on the beach. He was the only drunkard in the village, so he felt a bit lonely at times, but he found both comfort and solace in the serene beauty of the sunset.
That particular evening, he stumbled upon an old copper lamp that was gently rolling on the sand, moved about by the waves. Across the haze (it wasn’t Singapore in the fall and it wasn’t a real haze, he was just, you know, drunk), the happy drunkard picked the lamp and brought it close to his eyes. Who knows, maybe it was an alcohol lamp? Not that it was very clean – there, now you could see some kind of inscription on the side, all the way to the, ah, top, which, ah, was hard to read.
Next thing he knew, the top of the lamp had popped up, he was sitting with his behind in the water, and lo and behold, there was a djinni hovering. A very ebullient djinni too, talking, well, ebulliently about three thousand bottles of beer in a lamp, and the rest wasn’t too clear. Three thousand years maybe? Or maybe it was the drunkard who wasn’t too clear because the djinni needed to insist about choosing his first wish.
When a djinni talks about your first wish, it’s time to be very, very prudent so that you don’t waste your second wish undoing the first, and the third undoing both, if that’s even possible, but the drunkard had heard stories – not this one perhaps, but others. So, prudently, he humbly wished for an unbreakable bottle of beer that would always stay cold and never get empty. Prudent and humble but convenient, you see, for as a drink, beer befitted his social condition and beer bottles get empty way too early, don’t they, plus, hey, a cold beer goes a long way. Or something. Also, three thousand bottles of beer on the wall, not in a lamp.
And there he was, with a beer bottle not in a lamp, not on the wall, but in his hand. It wasn’t looking like much, as beer bottles go, but again there he was, with a nicely cold beer bottle in his hand, opened. Politely, he asked whether he could, and he could, so he did, and then he did some more, and then some more just to make sure, and wouldn’t you know: the level in the bottle hadn’t gotten any lower, and the bottle was still as pleasantly cold in his hand as before. That put him in quite a contemplation.
But the djinni was getting insistent about his two other wishes, so he asked for two more bottles just like it.
Harald: Wow. Does he plan to drink them in a row?Alfrothul: Apparently.Vigfus: Question.Harald: Yes, Vigfus?Vigfus: What is the point of this story?Harald: I think it’s an allegory.Vigfus: Right. But what isn’t an allegory in these side notes, interludes, and other postludes?Alfrothul (helpful): Preludes, too.Vigfus: Whatever.Brynja: The bottles are a metaphor for the streams, in Exercise 19.Vigfus: But we are asked to concatenate 2 streams, not 3!Alfrothul: I think the point remains.Vigfus: I’m still confused.Brynja: How about you write a unit-test function for append_stream?
Implement an OCaml function reverse_stream that, given a stream, returns that stream, reversed.
Harald: You can’t do THAT!Vigfus: Indeed. Adding exercises after a handin was published is UNFAIR!Brynja: Do we even need to write a unit-test function for reverse_stream?
Fixed a typo in the solution for Exercise 10, thanks to Rayner Ng Jing Kai’s eagle eye [29 Mar 2020]
Fixed a typo in the narrative, thanks to Yunjeong Lee’s eagle eye [11 Jun 2019]
Completed [13 Apr 2019]
Created [28 Mar 2019]