STREAMS: INFINITE LISTS

Interleaving the elements of two streams.
We define it as a binary operator with low priority.

> infixr 5 \/

> (\/) :: [a] -> [a] -> [a]
> (x:xs) \/ ys = x : (ys \/ xs)

Selecting the elements in even and odd position

> evenEl :: [a] -> [a]
> evenEl (x:xs) = x : oddEl xs

> oddEl :: [a] -> [a]
> oddEl (_:xs) = evenEl xs

The list of prime numbers
First defined in the naive way

> prime :: Integer -> Bool
> prime n = (n>1) && and [n `rem` k /= 0 | k <- [2..n-1]]

> primeList :: [Integer]
> primeList = [n | n <- [2..], prime n]

Using the sieve of Eratosthenes

> multiple :: Integer -> Integer -> Bool
> multiple k n = n `rem` k == 0

> sieve :: Integer -> [Integer] -> [Integer]
> sieve k ns = filter (not.multiple k) ns 

> primes :: [Integer]
> primes = primAux [2..]
>   where primAux (n:ns) = n : primAux (sieve n ns)
        
We make lists an instance of the numeric class
so we can use constants and operations

> instance Num a => Num [a] where
>  (+) = zipWith (+)
>  (-) = zipWith (-)
>  (*) = zipWith (*)
>  abs = undefined   
>  signum = undefined
>  fromInteger = repeat . fromInteger

We can define streams very coincisely with recursive equations

> nat = 0:(nat+1)
> fac = 1:(nat+1)*fac
> fib = 0:fib' where fib'=1:fib+fib'

Productivity is in general undecidablle.
Is the following stream well-defined?

> psi :: [a] -> [a]
> psi (x:xs) = x : evenEl (psi (oddEl xs)) \/ oddEl (psi (evenEl xs))

> phi :: [a] -> [a]
> phi (x:xs) = x : oddEl (phi (evenEl xs)) \/ evenEl (phi (oddEl xs))

The unfold function is the most general way of defining streams.
To define a function from a type a to streams of b
we give two functions h and cont:
  h produces the head of the stream
  cont produces a "continuation" to generate the tail

> unfold :: (a->b) -> (a->a) -> a -> [b]
> unfold h cont x = h x : unfold h cont (cont x)

> nat' = unfold id (+1) 0
> fac' = unfold snd (\(n,x)->(n+1,n*x)) (1,1)
> fib' = unfold fst (\(x,y)->(y,x+y)) (0,1)

Try to define psi and phi using unfold: it's very difficult.
The unfold operator is a safe way to generate streams.

Stream of differences:

> delta :: Num a => [a] -> [a]
> delta s = tail s - s

Stream of partial sums:

> sigma :: Num a => [a] -> [a]
> sigma s = s + (0:sigma s)

delta and sigma are mutual inverses.

JUST STREAMS

If we want a type that contains only the infinite streams,
excluding the finite list, we can define it without the nil constructor.

> data Stream a = Cons a (Stream a)

Instead of deriving automatically an instance of the Show class
we program it to display only a finite number of elements (20)

> instance Show a => Show (Stream a) where
>   show s = shown 20 s
>     where shown 0 s = "..."
>           shown n (Cons a as) = (show a) ++ ", " ++ shown (n-1) as

All operations can be defined in the same way as for lists.

> repeatS :: a -> Stream a
> repeatS a = Cons a (repeatS a)

> mapS :: (a -> b) -> Stream a -> Stream b
> mapS f (Cons a as) = Cons (f a) (mapS f as)

> zipS :: (a -> b -> c) -> Stream a -> Stream b -> Stream c
> zipS g (Cons a as) (Cons b bs) = Cons (g a b) (zipS g as bs)

> iterateS :: (a -> a) -> a -> Stream a
> iterateS f a = Cons a (iterateS f (f a))

Conversion with infinite lists

> listStream :: [a] -> Stream a
> listStream (a:as) = Cons a (listStream as) -- works only on infinite lists

> streamList :: Stream a -> [a]
> streamList (Cons a as) = a : (streamList as)

In the sequel we continue using the list type to represent streams.

Not all recursive stream equations correctly define a stream.
Some will loop without generating elements or will hang after
generating only a few.
For example, the function phi above hangs, while the similar function
psi correctly produces a stream.

There are three important concepts about the correct definition of streams.

PRODUCTIVITY
  A recursive equation is called "productive" if, when we unfold and
  simplify it, it always keeps producing new elements.
  psi is productive, but phi is not productive.
  Productivity is in general undecidable, so it is not useful when
  we want to determine the correct form of a recursive equation.

UNFOLD
  Streams generated by using the "unfold" operator are always productive.
  We just have to make sure that the functions that we pass
  as parameters to "unfold" are total.

GUARDEDNESS
  We can restrict the allowed recursive equations to those that
  are "guarded by constructors". This means that recursive calls
  on the right-hand side of the equation can only occur as arguments
  of the constructor (:).
                           
Examples:
                           
> s1 = 7 : 2 : s1

is guarded because s1 is the argument of two successive (:) applications.
                           
> s2 = 8 : tail s2

is not guarded because s2 is the argument of tail,
which is not a constructor.

> s3 = 9 : 2 : tail s3

is also not guarded, but it is productive anyway.
Sometimes guardedness is strichter than necessary

> s4 = 3 : (evenEl (4:s4))

is not guarded: even if s4 is an argument of (:), the resulting
term is an argument of evenEl, which is not a constructor.

We can relax a bit the condition of guardedness, but allowing the use
of functions that are guaranteed not to delete elements, that is, to
produce at least one part of the output stream for every element in
the input streams.
For example (\/) is such a function; but evenEl is not because it
deletes the elements in odd position. Also the numeric operations
are acceptable in this sense.

So the following definition is acceptable by an extended notion
of guardedness:

> s5 = 0 : (s5+1) \/ (2*s5)