Haskell's lazy evaluation allows us to specify an infinite list
[2, 4 .. ]
where
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 ...))
then
> (car xs)
a1
> (cadr xs)
a2
> (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)
2
> (cadr xs)
4
> (car (cdr xs))
4
> (cadr (cdr (cdr xs)))
16
> (cadr (cdr (cdr (cdr (cdr (cdr xs))))))
128
There's no need for the parentheses of course, but I wanted to keep things Lispy.
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
1024
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
[2,4,8,16,32,64,128,256,512,1024]
These basic procedures make it possible to construct more complex operations on streams.