Infinite stream

Haskell's lazy evaluation allows us to specify an infinite list

[2, 4 .. ]


take 10 [2, 4 .. ]

will return a finite list of the first 10 even numbers.

This is not the default behavior of eagerly evaluated Purescript, but it's remarkably easy to simulate using nothing more than a tuple. If we consider an infinite stream of values as a Lisp style list

(define xs (a1 a2 ...))


> (car xs)

> (cadr xs)

> (cdr xs)
(a2, a3, ...)

> (cdr (cdr xs))
(a3, a4, ...)

Using these three procedures allows one to recurse down a sequence indefinitely, accessing any an value, which is the result of applying a monoidal function f against a1 n times.

This endless illusion is cast in Purescript with the following type.

type Stream a = Tuple a (a → a)

A stream is just a tuple with a concrete value as its first item and a monoidal function as its second. This latter function is applied to the first value to derive the next item in the sequence.

Creating a stream means creating a tuple with these two items.

stream ∷ ∀ a. a → (a → a) → Stream a
stream = Tuple

Accessing the first item in the stream means accessing the first item in the tuple.

car ∷ ∀ a. Stream a → a 
car = fst 

Accessing the second item in the stream means running the fetched function from the tuple's second slot against the fetched value from the tuple's first slot. The S combinator facilitates this behavior elegantly.

cadr ∷ ∀ a. Stream a → a
cadr = snd <*> fst

Iterating down the stream means returning a new stream object with its (cadr) as its (car). The second value remains unchanged. A monadic fork takes care of this.

cdr ∷ ∀ a. Stream a → Stream a
cdr = lift2 stream cadr snd 

That's it. Infinity in four one-liners; not bad. Consider this contrived sequence of doubling values.

xs ∷ Stream Int 
xs = stream 2 (_ * 2)

> (car xs)

> (cadr xs)

> (car (cdr xs))

> (cadr (cdr (cdr xs)))

> (cadr (cdr (cdr (cdr (cdr (cdr xs))))))

There's no need for the parentheses of course, but I wanted to keep things Lispy.

Stream procedures

Left and right folds over streams are implemented in the same manner as their finite cousins, but with an additional integer parameter to mark when the fold terminates.

foldl ∷ ∀ a b. Int → (b → a → b) → b → Stream a → b
foldl 0 _ acc xs = acc
foldl n f acc xs = foldl (n - 1) f (f acc (car xs)) (cdr xs)

foldr ∷ ∀ a b. Int → (a → b → b) → b → Stream a → b
foldr 0 _ acc xs = acc
foldr n f acc xs = f (car xs) (foldr (n - 1) f acc (cdr xs))

The nth value in a stream can be retrieved with a left fold of the K and I combinators. Notice how the parameter order of f makes this possible.

get ∷ ∀ a. Int → Stream a → a
get n xs = foldl n (const identity) (car xs) xs

> get 10 xs

The first n values of the stream can be fetched with a right fold of cons.

take ∷ ∀ a. Int → Stream a → Array a
take n = foldr n cons []

> take 10 xs

These basic procedures make it possible to construct more complex operations on streams.