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.