art with code

2010-08-26

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.
Post a Comment

Blog Archive

About Me

My photo

Built art installations, web sites, graphics libraries, web browsers, mobile apps, desktop apps, media player themes, many nutty prototypes, much bad code, much bad art.

Have freelanced for Verizon, Google, Mozilla, Warner Bros, Sony Pictures, Yahoo!, Microsoft, Valve Software, TDK Electronics.

Ex-Chrome Developer Relations.