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 stream_make seed next =
(* stream_make : '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, stream_make 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, stream_make 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 = stream_make 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 = stream_make 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 = stream_make 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 = stream_make 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 = stream_make 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 stream_merge (Scons (v1, s1)) (Scons (v2, s2)) =
(* stream_merge : 'a stream -> 'a stream -> 'a stream *)
Scons (v1,
lazy (Scons (v2,
lazy (stream_merge (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 (stream_merge evens odds);;
- : bool = true
#
Implement an OCaml function stream_nth that, given a stream and an index, yields the element in this stream at that index:
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: i = 0
given a stream Scons (v, s'), indexing it at 0 should yield v
induction step: i = succ i'
given a stream s', and under the induction hypothesis that indexing it at i' yields v', then for any value v, indexing Scons (v, lazy s') at index succ i' should also yield v
In OCaml:
let stream_nth s n =
(* stream_nth : 'a stream -> int -> 'a *)
let () = assert (n >= 0) in
let rec loop i (Scons (v, s')) =
if i = 0
then v
else loop (pred i) (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 stream_prefix that, given a stream and an index, yields a list that is the prefix of this stream prior to this index:
let test_stream_prefix_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 =
(* iota : int -> int list *)
let rec visit i a =
match i with
| 0 ->
a
| _ ->
let i' = pred i
in visit i' (i' :: a)
in visit n [];;
let test_stream_prefix_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: i = 0
given a stream s, prefixing it at 0 should yield []
induction step: i = succ i'
given a stream s', and under the induction hypothesis that prefixing it at i' yields vs', then for any value v, prefixing Scons (v, lazy s') at index succ i' should yield v :: vs'
In OCaml:
let stream_prefix s n =
(* stream_prefix : 'a stream -> int -> 'a list *)
let () = assert (n >= 0) in
let rec visit i (Scons (v, s')) =
if i = 0
then []
else v :: visit (pred i) (Lazy.force s')
in visit n s;;
The implementation passes the unit test:
# test_stream_prefix_int stream_prefix;;
- : 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 =
stream_prefix (candidate vs s) (List.length vs) = vs
in let b0 = test [] nats
and b1 = test [-1] nats
and b2 = test [-2; -1] nats
and b3 = test [-3; -2; -1] nats
in b0 && b1 && b2 && b3;;
Explain why this unit-test function makes sense, and flesh it out.
The point of test, in the definition of test_stream_prepend_int, is to check whether applying the candidate function to a given list of length n and to a given stream yields a stream whose prefix (of length n) is the given list. In other words, if we prepend a list to a stream, the prefix of the resulting stream should be this list.
This unit-test function can be expanded to check beyond the given prefix and into the given stream:
let expanded_test_stream_prepend_int candidate =
let new_test vs s =
let x = Random.int 100
in stream_prefix (candidate vs s) (List.length vs + x) = vs @ stream_prefix s x
in let b0 = new_test [] nats
and b1 = new_test [-1] nats
and b2 = new_test [-2; -1] nats
and b3 = new_test [-3; -2; -1] 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
#
As in the solution for Exercise 37 in Week 09 (to quote Alfrothul, “S-m-n theorem much, Dana?”), unfolding the let-expression has the effect of delaying the traversal of the given list until the resulting stream is forced:
let stream_prepend' vs s =
let rec visit vs s =
match vs with
| [] ->
s
| v :: vs' ->
Scons (v, lazy (visit vs' s))
in visit vs s;;
This implementation also passes both unit tests.
Implement an OCaml function compare_stream_prefixes that, given two streams and an index 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 =
stream_prefix s1 n = stream_prefix 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 stream_prefix) and then compares them. Yours should not construct any intermediate lists.
Implement an OCaml function stream_suffix that, given a stream and an index, yields a stream that is the suffix of this stream beyond this index:
let test_stream_suffix_int candidate =
let b0 = (let n = Random.int 100
in stream_prefix (candidate nats 0) n = stream_prefix nats n)
and b1 = (let n = Random.int 100
in stream_prefix (candidate nats 1) n = stream_prefix posints n)
(* etc. *)
in b0 && b1;;
Explain why this unit-test function makes sense, and flesh it out.
Using stream_make, 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 =
(stream_prefix candidate_stream 10 = [1; -1; 1; -1; 1; -1; 1; -1; 1; -1]);;
Using stream_make, 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 =
(stream_prefix candidate_stream 10 = [0; 1; 0; 1; 0; 1; 0; 1; 0; 1]);;
Using stream_make, 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 =
(stream_prefix candidate_stream 10 = [0; -1; 0; -1; 0; -1; 0; -1; 0; -1]);;
Using stream_make, 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 =
(stream_prefix candidate_stream 10 = [0; -1; 2; -3; 4; -5; 6; -7; 8; -9]);;
Using stream_make, 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 =
(stream_prefix candidate_stream 10 = [0; -1; 1; -2; 2; -3; 3; -4; 4; -5]);;
Trouble with streams, I’m stumped,But I won’t be slumped always,‘Cause the truth is gonna shineIn my backbrain somedayI’m scrolling down through the bufferI’m gonna meta-x run-ocamlAnd since tail calls will get me there,My own reward will see no delayBubbles in streams, I’m thrilled,And I will graduate one day,And the truth is gonna shineIn my backbrain always—with obvious apologies to Richard M. Jones
Implement an OCaml function stream_append 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 bottle of beer not in a lamp, not on the fourth wall, but in his hand. It wasn’t looking like much, as bottles of beer go, but again there he was, with a nicely inviting cold bottle of beer in his hand. 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.
Anton: Wow. Does he plan to drink them in a row?Alfrothul: Apparently.Pablito: Question.Anton: Yes, Pablito?Pablito: What is the point of this story?Anton: I think it’s an allegory.Pablito: Right. But what isn’t an allegory in these side notes, interludes, and other postludes?Alfrothul (helpful): Preludes, too.Pablito (impatiently): Whatever.Dana: The bottles are a metaphor for the streams, in Exercise 20.Pablito: But we are asked to concatenate 2 streams, not 3!Alfrothul: I think the point remains.Pablito: I’m still confused.Dana: How about you write a unit-test function for stream_append?
Implement an OCaml function stream_reverse that, given a stream, returns that stream, reversed.
Anton: You can’t do THAT!Pablito: Indeed. Adding exercises after a handin was published is UNFAIR!Dana: Do we even need to write a unit-test function for stream_reverse?
Created [27 Oct 2022]