(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 `b`

s 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 accum :: acc -> [acc -> acc] -> acc accum = fold (flip ($ |