fold and accumulate

(You can also look at this post using the great my FPComplete tutorial for this)

what is this about?

Recently I played a bit with threepenny-gui and soon ran into the situation where I wanted to update a behavior (my state) using the old state and certain events.
Not having to much real functional approach to reactive programming my mind at once cried “give me some fold man” … but alas: there is nothing that has a close shape to a fold in this library.

So I skimmed through the libraray and could really not get how I could ever get to use “old-state” together with an event …

After a while I finally saw some “accumulate” functions in there, and as I knew their close relationship with folds (for example in .net/linq fold is named Accumulate) I knew I might have found a way out … but wait this is the type-signature of the one I finally used:

accumB :: MonadIO m => a -> Event (a -> a) -> m (Behavior a)

let’s rephrase that a bit and you get basically

accum :: acc -> [acc -> acc] -> acc

It’s quite a bit away from

foldl :: (acc -> b -> acc) -> acc -> [b] -> acc

And I really struggled to finally see how you could use accum to get foldl.

If you like me don’t see how you could possible to this read on – if you find this trivial better close the site now.

the idea

After 20 minutes or so (searching around for other stuff, coming back, scratching my head, …) I finally saw how to do it:

Just map the bs into functions acc -> acc and vóila: done.

let’s implement this

So let’s try – here is functional version of the basic accum function:

accum :: acc -> [acc -> acc] -> acc
accum acc []     = acc
accum acc (f:fs) = accum (f acc) fs

main = do
    putStrLn $ show . accum 0 $ [(+1), (+2), (+3), (+4)]

And of course, using f :: acc -> b -> acc and given a b we map this into \acc -> f acc b or flip f b:

fold :: (acc -> b -> acc) -> acc -> [b] -> acc
fold f acc = accum acc . map (flip f)

Seems to be correct (at least the compiler is happy and the results math).

a bit eq. reasoning

So let’s get a bit further by actually showing that this is correct. Using the definition of accum we see that (abusing the syntax highlighter and eq. reasoning here – so == is meta-equals instead of a lang. construct):

fold f acc [] == accum acc . map (flip f) $ []
              == accum acc []
              == acc

So the base-case is the same as foldl – check.

The non-empty list case is not much more:

fold f acc (b:bs) == accum acc . map (flip f) $ (b:bs)
                  == accum acc $ 1)\a -> f a b) : map (flip f) bs)
                  == accum ((\a -> f a b) acc) $ map (flip f) bs
                  == accum (f acc b) $ map ...continue

References   [ + ]

1. \a -> f a b) : map (flip f) bs) == accum ((\a -> f a b) acc) $ map (flip f) bs == accum (f acc b) $ map (flip f) bs == fold f (f acc b) bs

That’s it – qed 😉

and vice versa?

Well this is just as simple: having a fold like above you can define a accum by:

accum :: acc -> [acc -> acc] -> acc
accum = fold (flip ($