On Iteratee's, part I

There's a concept that's been explored recently in Haskell, the idea of enumerated IO. I'd like to go over the idea in detail.

Folds.

The basic idea is that of a fold. In Haskell, there are two basic folds over lists.

foldr :: (b->a->a) -> a -> [b] -> a
foldr f y0 [] = y0 -- folding an empty list returns the base case.
foldr f y0 (x:xs) = f x (foldr f y0 xs)


-- Note that outermost is f. This is important in Haskell.
-- You can right fold over an infinite list, but not a left fold.


foldl :: (a->b->a) -> a -> [b] -> a
foldl f y0 [] = y0 -- folding an empty list returns the base case.
foldl f y0 (x:xs) = foldl (f x y0) xs


-- There's also a strict version foldl'.


Read "foldr ::" as "foldr has the type". foldr takes a function, a value of type a, a list of b's, and returns an a.
foldl is similar. For this post, we'll mainly deal with left folds. A good example to start with is the function sum:


sum :: [Int] -> Int  --sum maps a list of Ints to an Int
sum xs = foldl (+) 0 xs


reverse :: [a] -> a
reverse as = foldl (flip (:)) [] as


A left fold has the advantage that it uses an accumulating parameter. It gets compiled down to a tight loop. You would write sum as a strict left fold. A right fold has the advantage that it can skip part of the input. You would write and as a right fold.

and :: [Bool] -> Bool
and as = foldr (&&) True as.


This has the nice property that it returns as soon as it sees a False (short circuit evaluation).
There's a way to get both properties in a left fold. It's called an early terminating left fold.

etfoldl :: (a->b->(a, Bool)) -> a -> [b] -> a
etfoldl f y0 [] = y0
etfoldl f y0 (x:xs) =
  case (f y0 x) of
    (y, True) -> y  -- True means we're done.
    (y, False) -> etfoldl f y xs


I used it to solve some problems where I was looking for the smallest value that satisfied some condition, but I had to chain some data structure along. Early terminating folds are a good place to stop.


Next up, Iteratees, A generalization of early terminating folds.