Transcript Programming with Streams - Department of Computer Science

CS321 Functional Programming 2
Programming with Streams
A stream is never finite and could be defined as special
polymorphic type
data stream a = a :^ Stream a
but it is more convenient to “simulate” them with standard lists,
but never use the empty list []
inf = 1 : inf -- the infinite list of 1's
from n = n : from (n+1)
nats = from 0 -- the natural numbers
© JAS 2005
2-1
CS321 Functional Programming 2
series f a = a : series f (f a)
-- a general series generating function
-- actually defined in the prelude as
-- iterate
nats2 = series (+1) 0
inf2 = series (\i -> i) 1
powers n = series (* n) 1-- the powers of n
These definitions work because of Haskell’s Normal Order
Reduction / Lazy Evaluation Strategy
© JAS 2005
2-2
CS321 Functional Programming 2
Another useful operation is to find the limit of a stream or
list (what value does it tend to?)
limit crit hs@(h:t) |
|
-- crit is a function
-- determines whether
-- elements of a list
-- enough
crit hs = h
otherwise = limit crit t
which
the first two
are similar
epsilon (h:(j:js)) = (h-j) < 0.000001
© JAS 2005
2-3
CS321 Functional Programming 2
A classic example of a stream computation is to generate
prime numbers
remove p = filter (not . p)
primes
= sieve [2..]
sieve (p:nos) =
p:sieve (remove (multsof p) nos)
where multsof p n = n 'rem' p == 0
© JAS 2005
2-4
CS321 Functional Programming 2
Stream problems and interconnected processes
A classic problem (attributed to Hamming) is to generate in
ascending order the sequence of positive numbers divisible only by
2, 3 and 5. ie the stream of nos 2m3n5p where m=0.., n=0.., p=0..
An alternative way of expressing this (due to Dijkstra) is
• the value 1 is in the sequence
• if x is in the sequence then so is 2x, 3x, 5x
• no other items are in the sequence
© JAS 2005
2-5
CS321 Functional Programming 2
It is fairly easy to define functions which given a sequence
generate sequences multiplied by 2, 3 or 5
t2 (h:t) = 2*h : t2
t3 (h:t) = 3*h : t3
t5 (h:t) = 5*h : t5
or
times n (h:t) = n*h
t
t
t
: times n t
The problem now is to merge the streams in ascending order
and remove duplicates
© JAS 2005
2-6
CS321 Functional Programming 2
[2,4,6,8..]
1
t2
[1,2,3,4..]
t3
merge
[3,6,9,12..]
merge
[5,10,15,20..]
:
t5
© JAS 2005
2-7
CS321 Functional Programming 2
We define a merge function
merge x@(hx:tx) y@(hy:ty)
| hx < hy
= hx : merge tx y
| hx == hy
=
merge tx y
| otherwise = hy : merge x ty
and a complete solution is
h
= 1:h235
h2
= times 2 h
h3
= times 3 h
h5
= times 5 h
h23 = merge h2 h3
h235 = merge h23 h5
© JAS 2005
2-8
CS321 Functional Programming 2
Sets and Infinite Streams
To remove duplicates from a finite list (to make it represent a set) we
can define the following function.
nub [] = []
nub (h:t)| elem h t = nub t
| otherwise = h : nub t
On an infinite list the test elem h t would never terminate.
© JAS 2005
2-9
CS321 Functional Programming 2
nub = rm []
where
rm sofar []
= []
rm sofar (h:t) | elem h sofar = rm sofar t
| otherwise = h:rm (h:sofar) t
sofar is a list of elements found so far – as the list/set grows this
will grow leading to what is sometimes termed a “space leak”
nub []
= []
nub (x:xs) = x: nub (filter (/= x) xs
With this version a series of nested calls to a filter function will
build up – again causing potential space/efficiency problem.
Such problems are a hidden danger in languages using lazy evaluation.
© JAS 2005
2-10
CS321 Functional Programming 2
Recall the concept of list comprehensions
[expr | qualifiers]
To define prime numbers we could write
primes = sieve [2..]
sieve (prime : rest) =
prime : sieve [r|r<-rest,r 'rem' prime/=0]
This would appear to require the implementation of an infinite set,
with the inherent problems of space leaks if we try and remove
duplicates. Hence an implementation may well ignore the
existence of duplicate elements.
© JAS 2005
2-11
CS321 Functional Programming 2
Consider a case with more than one list
cart s t = [ (x,y) | x <-s, y<-t]
This produces the cartesian product of two sets s and t.
If s and t are the natural numbers how can we guarantee that we
produce all pairs eventually? (This is known as fairness)
If we iterate over s first we would never get beyond pairs of the form
(n,1).
The solution is for the programmer (or the system, though this is not
always satisfactory) to define a different generation order diagonalisation.
Eg intpairs=[(x,n-x)|n<-[0..],x<-[0..n]]
© JAS 2005
2-12
CS321 Functional Programming 2
A recursive stream example
fib
fib
fib
fib
:: Integer -> Integer
0 = 1
1 = 1
n = fib (n-1) + fib (n-2)
fib 8
 fib 7 + fib 6
 (fib 6 + fib 5) + (fib 5 + fib 4)
 ((fib 5 + fib 4) + (fib 4 + fib 3)) +
((fib 4 + fib 3) + (fib 3 + fib 2))
………………
2-13
© JAS 2005
CS321 Functional Programming 2
Fibonacci seq
1 1 2 3 5
8 13 21
tail of Fibonnaci seq 1 2 3 5 8 13 21 34
tail of tail of fib seq 2 3 5 8 13 21 34 55
fibs :: [integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
fibs
 (1:1: zW (+) fibs (tail fibs))
 (1:1: zW (+) (1:1:zW+ fibs (tail fibs))
(1:zW+ fibs (tail fibs))
tf
© JAS 2005
2-14
CS321 Functional Programming 2
zipWith (+)
1
1
(:)
(:)
© JAS 2005
2-15
CS321 Functional Programming 2
Client Servers using Streams
client :: [Response] -> [Request]
server :: [Request] -> [Response]
reqs = client resps
resps = server reqs
type Request = Integer
type Response = Integer
client ys = 1 : ys
server xs = map (+1) xs
© JAS 2005
2-16
CS321 Functional Programming 2
server
(+1)
resps = 2,3,4..
1
(:)
client
reqs = 1,2,3..
reqs
 client resps
 1:resps
 1:server reqs
 1:tr
where tr = server reqs
 1:tr
where tr = 2:server tr
 1:tr
where tr = 2:tr2
where tr2 = server tr
 1:tr
where tr = 2:tr2
where tr2 = 3:server tr2
 1:2:tr2
2-17
where tr2 = 3:server tr2
© JAS 2005
CS321 Functional Programming 2
client (y:ys) = if ok y then 1:(y:ys)
else error “faulty server”
ok y = True
reqs
 client resps
 client (server reqs)
 client (server (client resps))
 ………
© JAS 2005
2-18
CS321 Functional Programming 2
client ys = 1 : if ok (head ys) then ys
else error “faulty server”
client ~(y:ys) = 1:if ok y then(y:ys)
else error “faulty server”
reqs
 client resps
 1:if ok y then y:ys else error “fault..”
where y:ys = resps
 1:(y:ys) where y:ys = resps
 1:resps
© JAS 2005
2-19
CS321 Functional Programming 2
Memoization
fibsFn :: () -> [Integer]
fibsFn x =
1:1:zipWith(+) (fibsFn()) (tail (fibsFn()))
fibsFn ()
 1:1:zW+ (fibsFn()) (tail (fibsFn()))
 1:tf
where tf = 1:zW+(fibsFn())(tail( fibsFn()))
Equal? – no general way to tell
© JAS 2005
2-20
CS321 Functional Programming 2
Imagine a function
memo :: (a->b)->(a->b)
Which is such that
memo f x = f x
And records values f has been applied to and the result (the memo)
Assume a function memo1 which saves just one argument and result
mfibsFn :: () -> [Integer]
mfibsFn x =
let mfibs = memo1 mfibsFn
in 1:1:zipWith(+)(mfibs())(tail(mfibs()))
© JAS 2005
2-21