Folding, part 1

The fold function is a data structure accumulator: it goes through every element in the data structure and builds up an accumulator value from them. An example for folding lists:

foldl f acc [] = acc
foldl f acc (x:xs) = foldl f (f acc x) xs

With a fold you can do maps and filters of different kinds. Here's a few examples:

-- id x = x
reverseMap f lst = foldl (\l i -> (f i):l) [] lst
reverse = reverseMap id
map f lst = reverse (reverseMap f lst)

filter f lst = 
  reverse (foldl (\l i -> 
    if f i 
      then i:l 
      else l
  ) [] lst)

concat a b = foldl (\l i -> i:l) b (reverse a)

concatMap f lst = foldl (\l i -> concat l (f i)) [] lst

triplicate lst = concatMap (\i -> [i,i,i]) lst

drop n lst = 
  reverse $ snd $ foldl (\(c,l) i ->
    if c >= n 
      then (c, i:l) 
      else (c+1, l)) (0,[]) lst

You can also do find operations with fold, but they're not as efficient as you'd like, because the fold goes through all the elements in the list. To make find efficient, we need a fold with break.

findInefficient f lst = 
  foldl (\e i -> 
    case e of 
      Nothing -> (if f i then Just i else e)
      Just x -> e) Nothing lst

data Break a = Break a | Continue a

foldlWithBreak f acc [] = acc
foldlWithBreak f acc (x:xs) = 
  case f acc x of
    Break a -> a
    Continue a -> foldlWithBreak f a xs

find f lst = 
  foldlWithBreak (\e i -> 
    if f i 
      then Break (Just i) 
      else Continue Nothing) Nothing lst

take n lst = 
  reverse $ snd $ foldlWithBreak (\(c, l) i -> 
    if c >= n 
      then Break (c,l)
      else Continue (c+1, i:l)) (0, []) lst

any f lst = 
  -- maybe False (const True) (find f lst)
  case find f lst of
    Just x -> True
    Nothing -> False

all f lst = 
  -- not $ any (not.f) lst
  not (any (\x -> not (f x)) lst)

And that's it for today. Tomorrow, parallel folding.