Sat Feb 13 17:54:06 CET 2010

Recursion and Co-recursion for filters (s,a) -> (s,b) on a list [a]


-- The intermediate/end state s is never observed, so [a] can be infinite.

iimap :: ((s,a) -> (s,b)) -> s -> [a] -> [b]
iimap fn = f
      f s [] = []
      f s (a:as) = let (s',b) = fn (s,a) in b:(f s' as)


-- State s can be observed, so [a] needs to be finite.  This can't be
-- written as co-recursion, so we write it as a fold where the results
-- are accumulated in reverse.

iifold :: ((s,a) -> (s,b)) -> (s,[a]) -> (s,[b])

iifold fn (s,as) = f s as []
      f s [] bs = (s, bs)
      f s (a:as) bs = let (s',b) = fn (s,a) in f s' as (b:bs)

integrate (s,a) = let s' = a+s in (s',s')

-- In the RECURSIVE pattern, the fact that the `bs' accumulator is a
-- list is irrelevant.  In the CORECURSIVE pattern, the fact that the
-- result is a list is essential: it is the recursion inside the list
-- constructor that makes it possible to present iimap with infinite
-- data.