We show how to merge two folds into another fold `elementwise'. Furthermore, we present a library of (potentially infinite) ``lists'' represented as folds (aka streams, aka success-failure-continuation--based generators). Whereas the standard Prelude functions such as |map| and |take| transform lists, we transform folds. We implement the range of progressively more complex transformers -- from |map|, |filter|, |takeWhile| to |take|, to |drop| and |dropWhile|, and finally, |zip| and |zipWith|. Emphatically we never convert a stream to a list and so we never use value recursion. All iterative processing is driven by the fold itself. The implementation of zip also solves the problem of ``parallel loops''. One can think of a fold as an accumulating loop. One can easily represent a nested loop as a nested fold. Representing parallel loop as a fold is a challenge, answered at the end of the message. We need recursive types -- but again, never value recursion. This library is inspired by Greg Buchholz' message on the Haskell-Cafe list and is meant to answer open questions posed at the end of that message http://www.haskell.org/pipermail/haskell-cafe/2005-October/011575.html This message a complete literate Haskell code.
{-# OPTIONS -fglasgow-exts #-} module Folds where
First we define the representation of a list as a fold:
newtype FR a = FR (forall ans. (a -> ans -> ans) -> ans -> ans) unFR (FR x) = x
It has a rank-2 type. The defining equations are: if flst is a value of a type |FR a|, then unFR flst f z = z if flst represents an empty list unFR flst f z = f e (unFR flst' f z) if flst represents the list with the head 'e' and flst' represents the rest of that list
From another point of view, |unFR flst| can be considered a _stream_ that takes two arguments: the success continuation of the type |a -> ans -> ans| and the failure continuation of the type |ans|. The LogicT paper discusses such types in detail, and shows how to find that "rest of the list" flst'. The slides of the ICFP05 presentation by Chung-chieh Shan point out to more related work in that area.
But we are here to drop, take, dropWhile, etc. Our functions will take a stream and return another stream, of the |FR a| type, which represents truncated, filtered, etc. source stream. Let us define two sample streams: a finite and an infinite one:
stream1 :: FR Char stream1 = FR (\f unit -> foldr f unit ['a'..'i']) stream2 :: FR Int stream2 = FR (\f unit -> foldr f unit [1..])
and the way to show the stream. This is the only time we convert |FR a| to a list -- so we can more easily show it.
instance Show a => Show (FR a) where show l = show $ unFR l (:) []
The map function is trivial:
smap :: (a->b) -> FR a -> FR b
*> smap f l = FR(\g -> unFR l (g . f)) which can also be written as
smap f l = FR((unFR l) . (flip (.) f))
For example,
test1 = show $ smap succ stream1
Next is the filter function:
sfilter :: (a -> Bool) -> FR a -> FR a sfilter p l = FR(\f -> unFR l (\e r -> if p e then f e r else r))
test2 = sfilter (not . (`elem` "ch")) stream1
The function takeWhile is quite straightforward, too
stakeWhile :: (a -> Bool) -> FR a -> FR a stakeWhile p l = FR(\f z -> unFR l (\e r -> if p e then f e r else z) z)
test3 = stakeWhile (< 'z') stream1 test3' = stakeWhile (< 10) stream2
As we can see, stakeWhile well applies to an infinite stream. The functions take, drop, dropWhile ask for more complexity.
stake :: (Ord n, Num n) => n -> FR a -> FR a stake n l = FR(\f z -> unFR l (\e r n -> if n <= 0 then z else f e (r (n-1))) (const z) n)
test4 = stake 20 stream1 test4' = stake 5 stream1 test4'' = stake 11 stream2 test4''' = (stake 11 . smap (^2)) stream2
The function sdrop shows the major deficiency: we're stuck with the (<=0) test for the rest of the stream. In this case, some delimited continuation operators like `control' can help, in limited circumstances.
sdrop :: (Ord n, Num n) => n -> FR a -> FR a sdrop n l = FR(\f z -> unFR l (\e r n -> if n <= 0 then f e (r n) else r (n-1)) (const z) n)
test5 = sdrop 20 stream1 test5' = sdrop 5 stream1 test5'' = stake 5 $ sdrop 11 stream2
The function dropWhile becomes straightforward
sdropWhile :: (a -> Bool) -> FR a -> FR a sdropWhile p l = FR(\f z -> unFR l (\e r done -> if done then f e (r done) else if p e then r done else f e (r True)) (const z) False)
test6 = sdropWhile (< 'z') stream1 test6' = sdropWhile (< 'd') stream1 test6'' = stake 5 $ sdropWhile (< 10) stream2
The zip function is the most complex. Here we need a recursive type: an iso-recursive type to emulate the equi-recursive one.
newtype RecFR a ans = RecFR (a -> (RecFR a ans -> ans) -> ans) unRecFR (RecFR x) = x
This is still a newtype: there is no extra consing. I will not pretend that the following is the most perspicuous piece of code: *> szip :: FR a1 -> FR a2 -> FR (a1,a2) *> szip l1 l2 = FR(\f z -> *> let l1' = unFR l1 (\e r x -> unRecFR x e r) (\r -> z) *> l2' = unFR l2 (\e2 r2 e1 r1 -> f (e1,e2) (r1 (RecFR r2))) (\e r-> z) *> in l1' (RecFR l2')) It can be simplified to the following:
szipWith :: (a->b->c) -> FR a -> FR b -> FR c szipWith t l1 l2 = FR(\f z -> unFR l1 (\e r x -> unRecFR x e r) (\x -> z) (RecFR $ unFR l2 (\e2 r2 e1 r1 -> f (t e1 e2) (r1 (RecFR r2))) (\e r -> z)))
szip :: FR a -> FR b -> FR (a,b) szip = szipWith (,)
One can easily prove that this function does correspond to zip for all finite streams. The proof for infinite streams requires more elaboration.
test81 = szip stream1 stream1 test82 = szip stream1 stream2 test83 = szip stream2 stream1 test84 = stake 5 $ szip stream2 (sdrop 10 stream2)
As one may expect (or not), these tests give the right results *Folds> test83 [(1,'a'),(2,'b'),(3,'c'),(4,'d'),(5,'e'),(6,'f'),(7,'g'),(8,'h'),(9,'i')] *Folds> test84 [(1,11),(2,12),(3,13),(4,14),(5,15)]