Skip to content

Sixian Li

Stream

Functional Programming

Source code from COMP302 course page. Some helper functions are not shown here.

This post is my attempt to understand the beauty and power of streams.

Intro

The stream type below allows finite and infinite streams. Finite streams end with an end-of-stream marker that is written as Eos. An infinite stream does not end so it will not have an end-of-stream marker.

To represent “infinity”, we need to suspend the evaluation or no memory is large enough to hold infinite data. Here, we wrap the stream inside a function, and we “wake up” the stream by applying the function. We can never see the whole stream let alone print it, but we can ask for part of it, as long as this part is finite.

Examples

A stream of all ones

What is left after you take away the first 1 from infinitely many 1’s? Infinitely many 1’s!

So the code is saying: the stream starts with 1, and the rest of the stream also starts with 1, and the rest of the rest…

Natural numbers

Now we have 1,2,3,4,5…

Take out 1, we get an infinite stream starting from 2, then 3, then…

Fibonacci numbers

Below is a great picture that I found on stackoverflow for the famous one-liner in Haskell:

Visualization

Partial sum