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)