`[<<][compsci][>>][..]`
Sat Feb 13 17:54:06 CET 2010

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

```
-- CORECURSIVE

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

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

-- RECURSIVE

-- 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 []
where
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.

```
`[Reply][About]`
`[<<][compsci][>>][..]`