Let us continue to explore streams, based on the same infrastructure as in the previous lecture note:
a polymorphic type for streams:
type 'a stream = Scons of 'a * 'a stream Lazy.t;;
a stream maker, out of an initial seed and an endofunction:
let make_stream seed_init next =
(* make_stream : 'a -> ('a -> 'a) -> 'a stream *)
let rec emanate seed_current =
(* emanate : 'a -> 'a stream *)
Scons (seed_current, lazy (emanate (next seed_current)))
in emanate seed_init;;
the stream of natural numbers, the stream of even natural numbers, and the stream of odd natural numbers:
let nats = make_stream 0 succ;;
let evens = make_stream 0 (fun i -> i + 2);;
let odds = make_stream 1 (fun i -> i + 2);;
two stream accessors – one for the head, and one for the tail:
let shd (Scons (v, _)) =
(* shd : 'a stream -> 'a *)
v;;
let stl (Scons (_, ds)) =
(* stl : 'a stream -> 'a stream *)
Lazy.force ds;;
a function mapping the first elements of a stream into a list, in the same order:
let prefix_stream s n =
(* prefix_stream : 'a stream -> int -> 'a list *)
assert (n >= 0);
let rec visit n (Scons (v, ds')) =
if n = 0
then []
else let ih = visit (pred n) (Lazy.force ds')
in v :: ih
in visit n s;;
The rest of this lecture note is dedicated to stream transducers, i.e., functions mapping streams to other streams.
Here is how we had defined a function that duplicates the elements of any given list:
let stutter2 vs_init =
(* stutter2 : 'a list -> 'a list *)
let rec visit vs =
(* visit : 'a list -> 'a list *)
match vs with
| [] ->
[]
| v :: vs' ->
let ih = visit vs'
in v :: v :: ih
in visit vs_init;;
By analogy, let us implement a function that duplicates the elements of any given stream.
To test this function, we should verify that it gives the stream analogue of stutter2, which we can do by constructing the prefix of the result—a prefix which is twice as long as the initial list, due to the stuttering:
let test_stream_stutter2 candidate =
let b0 = (let n = Random.int 100
in prefix_stream (candidate nats) (2 * n)
= stutter2 (iota n))
(* etc. *)
in b0;;
(Reminder: iota maps a non-negative integer n to the increasing list of the first n non-negative integers.)
The solution is to recursively traverse the given stream and to construct a resulting stream where each element of the given stream is duplicated:
let rec stream_stutter2 (Scons (v, ds)) =
Scons (v, lazy (Scons (v, lazy (stream_stutter2 (Lazy.force ds)))));;
This implementation passes the unit test:
# test_stream_stutter2 stream_stutter2;;
- : bool = true
#
The goal here is to implement the analogue of the map function for streams, after studying it for strings (see Exercise 1 in Week 05), for lists (see The map function over polymorphic lists in Week 09), and for binary trees (see The map function over polymorphic binary trees in Week 11).
Here is a simple unit-test function that tests whether mapping the successor function over the increasing stream of natural numbers yields the increasing stream of positive natural numbers, and and whether mapping the twice function over the increasing stream of natural numbers yields the increasing stream of even natural numbers:
let test_map_stream candidate =
let b0 = (let n = Random.int 100
in prefix_stream (candidate succ nats) n = prefix_stream posnats n)
and b1 = (let n = Random.int 100
in prefix_stream (candidate (fun i -> 2 * i) nats) n = prefix_stream evens n)
in b0 && b1;;
We proceed recursively over the stream, as for lazy lists but without a base case:
let map_stream f s =
(* map_stream : ('a -> 'b) -> 'a stream -> 'b stream *)
let rec visit (Scons (v, ds)) =
(* visit : 'a stream -> 'b stream *)
Scons (f v, lazy (visit (Lazy.force ds)))
in visit s;;
This implementation passes the unit tests:
# test_map_stream map_stream;;
- : bool = true
#
For the same price, we can define a map function over two streams:
let map2_stream f s1 s2 =
(* map2_stream : ('a -> 'b -> 'c) -> 'a stream -> 'b stream -> 'c stream *)
let rec visit2 (Scons (v1, ds1)) (Scons (v2, ds2)) =
(* visit2 : 'a stream -> 'b stream -> 'c stream *)
Scons (f v1 v2, lazy (visit2 (Lazy.force ds1) (Lazy.force ds2)))
in visit2 s1 s2;;
We can then verify that adding pointwise the elements of the stream of non-negative integers and of the stream of non-positive integers yields the stream of zeroes:
# prefix_stream (map2_stream (fun p n -> p + n) (make_stream 1 succ) (make_stream ~-1 pred)) 10;;
- : int list = [0; 0; 0; 0; 0; 0; 0; 0; 0; 0]
#
In other words, map2_stream implements the dot-product of two streams.
The goal here is to write a stream transducer, that given a predicate (i.e., a Boolean-returning function), filters out the elements of the input stream that satisfy the predicate.
For example, filtering out the odd numbers in the stream of natural numbers yields the stream of even numbers, and filtering out the even numbers in the stream of natural numbers yields the stream of odd numbers:
let test_filter_out candidate =
let b0 = (prefix_stream (candidate (fun i -> i mod 2 = 1) nats) 20
= prefix_stream evens 20)
and b1 = (prefix_stream (candidate (fun i -> i mod 2 = 0) nats) 20
= prefix_stream odds 20)
(* etc. *)
in b0 && b1;;
Food for thought:
Here is a straight version with stream accessors:
let filter_out_v0 p xs_init =
let rec visit xs =
if p (shd xs)
then visit (stl xs)
else Scons (shd xs, lazy (visit (stl xs)))
in visit xs_init;;
This straight version passes the unit test:
# test_filter_out filter_out_v0;;
- : bool = true
#
Here is a version where the result of the accessors is named:
let filter_out_v1 p xs_init =
let rec visit xs =
let x = shd xs
and xs' = stl xs
in if p x
then visit xs'
else Scons (x, lazy (visit xs'))
in visit xs_init;;
This version with names also passes the unit test:
# test_filter_out filter_out_v1;;
- : bool = true
#
Here is a version that uses a match-expression instead of accessors:
let filter_out_v2 p xs_init =
let rec visit xs =
match xs with
| Scons (x, dxs') ->
if p x
then visit (Lazy.force dxs')
else Scons (x, lazy (visit (Lazy.force dxs')))
in visit xs_init;;
This version with a match-expression also passes the unit test:
# test_filter_out filter_out_v2;;
- : bool = true
#
And here is a version where pattern matching is carried out not with a match-expression but in the header of the local recursive function:
let filter_out_v3 p xs_init =
let rec visit (Scons (x, dxs')) =
if p x
then visit (Lazy.force dxs')
else Scons (x, lazy (visit (Lazy.force dxs')))
in visit xs_init;;
This final version also passes the unit test:
# test_filter_out filter_out_v3;;
- : bool = true
#
All these versions differ only because of their syntactic sugar: they are compiled to the same object program.
Write a stream transducer, filter_in, that given a predicate, filters in the elements of the input stream that satisfy the predicate.
For example, filtering in the odd numbers in the stream of natural numbers should yield the stream of odd numbers, and filtering in the even numbers in the stream of natural numbers should yield the stream of even numbers.
Could you define filter_in using filter_out?
The following OCaml function implements the sieve of Eratosthenes:
let stream_of_prime_numbers =
let rec down_this_stream (Scons (x, ds')) =
Scons (x, lazy (down_this_stream (filter_out_v3 (fun i -> i mod x = 0) (Lazy.force ds'))))
in down_this_stream (make_stream 2 succ);;
Starting from the sieve of natural numbers greater than 1, all the multiples of 2, 3, 5, etc. are filtered out, yielding the stream of prime numbers:
# prefix_stream stream_of_prime_numbers 20;;
- : int list =
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71]
#
The goal of the game is to map a stream of pairs into a stream of triples and vice-versa in such a way that the elements in the input stream occur in the same order in the output stream.
Let us characterize a stream of pairs of successive non-negative integers as well as a stream of triples of successive non-negative integers:
let test_stream_of_pairs_of_successive_non_negative_integers candidate =
let b0 = (prefix_stream candidate 0 =
[])
and b1 = (prefix_stream candidate 1 =
[(0, 1)])
and b7 = (prefix_stream candidate 7 =
[(0, 1); (2, 3); (4, 5); (6, 7); (8, 9); (10, 11); (12, 13)])
in b0 && b1 && b7;;
let test_stream_of_triples_of_successive_non_negative_integers candidate =
let b0 = (prefix_stream candidate 0 =
[])
and b1 = (prefix_stream candidate 1 =
[(0, 1, 2)])
and b5 = (prefix_stream candidate 5 =
[(0, 1, 2); (3, 4, 5); (6, 7, 8); (9, 10, 11); (12, 13, 14)])
in b0 && b1 && b5;;
Here are two quick-and-dirty implementations:
let stream_of_pairs_of_successive_non_negative_integers_v0 =
make_stream (0, 1) (fun (_, j) -> (j + 1, j + 2));;
let stream_of_triples_of_successive_non_negative_integers_v0 =
make_stream (0, 1, 2) (fun (_, _, k) -> (k + 1, k + 2, k + 3));;
Analysis:
These implementations pass the unit tests:
# test_stream_of_pairs_of_successive_non_negative_integers stream_of_pairs_of_successive_non_negative_integers_v0;;
- : bool = true
# test_stream_of_triples_of_successive_non_negative_integers stream_of_triples_of_successive_non_negative_integers_v0;;
- : bool = true
#
We are now in position to write two unit-test functions for functions that map a stream of pairs to a stream of triples and vice-versa:
let test_transduce_2_3_int candidate =
let b0 = test_stream_of_triples_of_successive_non_negative_integers
(candidate stream_of_pairs_of_successive_non_negative_integers_v0)
and b1 = let n = Random.int 100
in prefix_stream (candidate stream_of_pairs_of_successive_non_negative_integers_v0) n
= prefix_stream stream_of_triples_of_successive_non_negative_integers_v0 n
in b0 && b1;;
let test_transduce_3_2_int candidate =
let b0 = test_stream_of_pairs_of_successive_non_negative_integers
(candidate stream_of_triples_of_successive_non_negative_integers_v0)
and b1 = let n = Random.int 100
in prefix_stream (candidate stream_of_triples_of_successive_non_negative_integers_v0) n
= prefix_stream stream_of_pairs_of_successive_non_negative_integers_v0 n
in b0 && b1;;
The key idea is to consume the input stream until enough elements are gathered to produce the output stream, and then loop when all the input elements have been emitted:
let rec transduce_2_3 (Scons ((v1, v2), ds1)) =
(* transduce_2_3 : ('a * 'a) stream -> ('a * 'a * 'a) stream *)
let (Scons ((v3, v4), ds2)) = Lazy.force ds1
in Scons ((v1, v2, v3),
lazy (let (Scons ((v5, v6), ds3)) = Lazy.force ds2
in Scons ((v4, v5, v6),
lazy (transduce_2_3 (Lazy.force ds3)))));;
let rec transduce_3_2 (Scons ((v1, v2, v3), ds1)) =
(* transduce_3_2 : ('a * 'a * 'a) stream -> ('a * 'a) stream *)
Scons ((v1, v2),
lazy (let (Scons ((v4, v5, v6), ds2)) = Lazy.force ds1
in Scons ((v3, v4),
lazy (Scons ((v5, v6),
lazy (transduce_3_2 (Lazy.force ds2)))))));;
These two functions pass their unit tests:
# test_transduce_2_3_int transduce_2_3;;
- : bool = true
# test_transduce_3_2_int transduce_3_2;;
- : bool = true
#
Can we make do without the two quick-and-dirty implementations of the streams of pairs (and of triples) of successive non-negative integers?
Yes we can, if we first implement a transducer that maps a stream into a stream of pairs in such a way that the elements in the input stream occur in the same order in the output stream:
let rec transduce_1_2 (Scons (v1, ds1)) =
(* transduce_1_2 : 'a stream -> ('a * 'a) stream *)
let (Scons (v2, ds2)) = Lazy.force ds1
in Scons ((v1, v2), lazy (transduce_1_2 (Lazy.force ds2)));;
Then it is simple to obtain a stream of pairs of successive non-negative integers:
let stream_of_pairs_of_successive_non_negative_integers_v1 =
transduce_1_2 nats;;
This implementation passes the unit test:
# test_stream_of_pairs_of_successive_non_negative_integers stream_of_pairs_of_successive_non_negative_integers_v1;;
- : bool = true
#
Ditto for obtaining a stream of triples of successive non-negative integers:
let stream_of_triples_of_successive_non_negative_integers_v1 =
transduce_2_3 (transduce_1_2 nats);;
This implementation passes the unit test:
# test_stream_of_triples_of_successive_non_negative_integers stream_of_triples_of_successive_non_negative_integers_v1;;
- : bool = true
#
And we are now in position to define a polymorphic transducer that maps a stream into a stream of triples in such a way that the elements in the input stream occur in the same order in the output stream:
let transduce_1_3 s =
(* transduce_1_3 : 'a stream -> ('a * 'a * 'a) stream *)
transduce_2_3 (transduce_1_2 s);;
It is simple to construct the stream of Fibonacci numbers:
let test_fibs candidate =
match candidate with
| Scons (0, s1) ->
(match Lazy.force s1 with
| Scons (1, s2) ->
(match Lazy.force s2 with
| Scons (1, s3) ->
(match Lazy.force s3 with
| Scons (2, s4) ->
(match Lazy.force s4 with
| Scons (3, s5) ->
(match Lazy.force s5 with
| Scons (5, s6) ->
(match Lazy.force s6 with
| Scons (8, s7) ->
(match Lazy.force s7 with
| Scons (13, s7) ->
true
| _ ->
false)
| _ ->
false)
| _ ->
false)
| _ ->
false)
| _ ->
false)
| _ ->
false)
| _ ->
false)
| _ ->
false;;
let rec fib n =
match n with
| 0 -> 0
| 1 -> 1
| _ -> fib (n - 1) + fib (n - 2);;
let fibs_from_scratch =
let rec make_fibs n =
Scons (fib n, lazy (make_fibs (succ n)))
in make_fibs 0;;
In this definition, make_fibs is passed the index of the Fibonacci number to construct, and successively applies it as the stream is constructed.
Of course this is something that we have to test:
# test_fibs fibs_from_scratch;;
- : bool = true
#
In the definition of fibs_from_scratch, fib is invoked to construct each successive element of the stream, and therefore each successive Fibonacci number is computed from scratch. However, there is a simple relation between three consecutive Fibonacci numbers: by definition, adding the two first ones gives the third. Let us exploit this fact to implement an alternative version fibs_incremental as a simple example of incremental computing:
let fibs_incremental =
let rec make_fibs fib_i fib_succ_i =
Scons (fib_i, lazy (make_fibs fib_succ_i (fib_i + fib_succ_i)))
in make_fibs 0 1;;
In this definition, make_fibs is passed two consecutive Fibonacci numbers:
And it passes the unit test too:
# test_fibs fibs_incremental;;
- : bool = true
#
Alfrothul: On the other hand, why wait?
Harald: Well, we are talking about demand-driven computation here, so, very much on the one hand and not on the other. But that’s probably not what you mean. What do you mean?
Alfrothul: Right. I mean, in the definition of fibs_incremental, why wait until the next call to make_fibs to emit the second Fibonacci number? We have it right at hand, look:
let fibs_incremental =
let rec make_fibs fib_i fib_succ_i =
Scons (fib_i, lazy (make_fibs fib_succ_i (fib_i + fib_succ_i)))
in make_fibs 0 1;;
Harald: Oh, you mean that hand. That would work – we just need to manufacture the next two Fibonacci numbers in the next recursive call:
let fibs_incremental' =
let rec make_fibs fib_i fib_i_plus_1 =
Scons (fib_i,
lazy (Scons (fib_i_plus_1,
let fib_i_plus_2 = fib_i + fib_i_plus_1
in let fib_i_plus_3 = fib_i_plus_1 + fib_i_plus_2
in lazy (make_fibs fib_i_plus_2 fib_i_plus_3))))
in make_fibs 0 1;;
Vigfus (always helpful): This implementation passes the unit tests:
# test_fibs fibs_incremental';;
- : bool = true
#
Alfrothul: And now there are half as many recursive calls to make_fibs.
Harald: There were infinitely many calls, and now there are half as many. Yay.
Alfrothul: Also there is less argument shuffling at each recursive call, which I hear is always A Good Thing.
Implement two versions of the stream of Factorial numbers: one should construct each successive element of the stream from scratch, and the other should use an incremental construction.
Harald: I don’t know whether it is more efficient or what, but we could obtain posnats, the increasing stream of positive natural numbers, just by taking the tail of nats, lazily. Look:
# test_posnats (stl nats);;
- : bool = true
#
Alfrothul: True. Or by recursively mapping the successor function over nats, also lazily, that would work too:
# test_posnats (map_stream succ nats);;
- : bool = true
#
Harald: Right, but that would produce a new stream.
Alfrothul: Yes it would. If we recursively map the identity function over a given stream, we get another stream – an indistinguishable copy of this given stream:
let identity_stream s =
(* identity_stream : 'a stream -> 'a stream *)
map_stream (fun v -> v) s;;
Harald: Hum. Since the stream is constructed on demand, do you think that we could construct it out of itself?
Alfrothul: You mean like Jörmungandr?
Halcyon (interjecting a precision): Ouroboros for the rest of us.
Harald: More like its dual since it would construct itself by eating its own head, not its own tail.
Alfrothul (meditatively): Could it even reach its tail?
Harald: A good question, Alfrothul, a good question. But assuming it could, that wouldn’t actually be its head or its tail.
Alfrothul: Right. That would be a copy of its head or of its tail. But it wouldn’t know the difference, since there isn’t any.
Harald: Anyhow, the idea is that the stream of natural numbers would start with 0, and then continue with the result of mapping the successor function over itself.
Alfrothul: You mean like this:
let rec nats_bootstrapped =
Scons (0, lazy (map_stream succ nats_bootstrapped));;
Harald: Well, OCaml accepts that definition as something well typed.
Vigfus: And it passes the unit test:
# test_nats (nats_bootstrapped);;
- : bool = true
#
Harald: Still, to see is to believe. Let’s compute a prefix:
# prefix_stream nats_bootstrapped 10;;
- : int list = [0; 1; 2; 3; 4; 5; 6; 7; 8; 9]
#
Alfrothul: Oh, my.
Loki: Guys, I’m so proud of you! And thank you too for remembering Jörmungandr.
Brynja (coughing in her hand): Fathers.
Loki (blissfully): In a similar vein, you know what happens if you add pointwise the stream of Fibonacci numbers and its tail?
Harald (fast on the keyboard): You mean like this:
# prefix_stream (map2_stream (+) fibs_incremental (stl fibs_incremental)) 15;;
- : int list = [1; 2; 3; 5; 8; 13; 21; 34; 55; 89; 144; 233; 377; 610; 987]
#
Alfrothul: Ohmygoshes!
Loki (modestly): Thank you.
Alfrothul (not even noticing the interruption): We obtain a copy of the tail of the tail of the stream of Fibonacci numbers. How ...amusing.
Harald: Hey, we could pull the same stunt and define the stream of Fibonacci numbers like that. Look:
let rec fibs_bootstrapped =
Scons (0, lazy (Scons (1, lazy (map2_stream (+) fibs_bootstrapped (stl fibs_bootstrapped)))));;
Alfrothul: Well, OCaml accepts that definition as something well typed.
Vigfus: And it passes the unit test too:
# test_fibs fibs_bootstrapped;;
- : bool = true
#
Harald: Still, to see is to believe. Let’s compute a prefix:
# prefix_stream fibs_bootstrapped 17;;
- : int list = [0; 1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; 144; 233; 377; 610; 987]
#
Harald: Wow. It’s like the stream is braiding itself.
Alfrothul: And pulling each next number out of the resulting braid, yes. Actually, it is the same point as in nats_bootstrapped.
Harald: The things you get when putting recursion and laziness together...
Loki (unashamedly): Who would have thunk.
Alfrothul: I guess we should be careful what we wish for.
A passing drunkard, three identical bottles of beer tucked under one arm: Live and learn, young man. Live and learn.
The example of the stream transducers from pairs to triples and from triples to pairs is due to Carolyn L. Talcott.
Created [13 Apr 2019]