Programming with streams

Streams are a mutable structure:

• stream.first(s) gets the first element of the stream, and removes it from there (it “consumes” it)
• stream.isEmpty(s) checks whether there is another element

For example, a recursion over a stream could look like

def count : T* -> data
def count =
  (s ->
    if (stream.isEmpty(s))
      0
    else (
      let _ = stream.first(s);     // gets the first element and drop it
      count(s)
    )
  )

For example:

let s = [1,2,3][] in
count(s)

returns 3, and s is empty afterwards.

Another important primitive is ++ for appending two streams. Note that this is a really fast operation (O(1) - doesn’t depend on the size of the stream). For example, if we wanted to map every number of the input elements to a whole stream, we could do it like:

def expand : data* -> data*
def expand =
  (s ->
    if (stream.isEmpty(s))
      stream.empty
    else (
      let k = stream.first(s);
      let expansion = stream.enumerate(k);
      expansion ++ expand(s)
    )
  )

For example,

let s = [4,2,1][] in
expand(s)

would return the stream [0,1,2,3,0,1,0].

Here’s a recursion over two streams:

def zip : data* -> data* -> data*
def zip =
  ((s1,s2) ->
    if (stream.isEmpty(s1) || stream.isEmpty(s2))
      stream.empty
    else (
      let x1 = stream.first(s1);
      let x2 = stream.first(s2);
      let pair = [x1,x2];
      let expansion = stream.singleton(pair);
      expansion ++ zip(s1,s2)
    )
  )

For example, zip([1,2,3,4][], [10,11,12,13][]) would return the stream [[1,10],[2,11],[3,12],[4,13]].