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 `a`

_{n} value, which is the result of applying a monoidal function `f`

against `a`

_{1} `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.