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