[Haskell-cafe] Pretty little definitions of left and right folds

[Brent Yorgey]

On Fri, Jun 20, 2008 at 06:15:20PM -0500, George Kangas wrote:
> 
> foldright (+) [1, 2, 3] 0 == ( (1 +).(2 +).(3 +).id ) 0
> foldleft (+) [1, 2, 3] 0 == ( id.(3 +).(2 +).(1 +) ) 0
> 

Hi George,

This is very cool!  I have never thought of folds in quite this way
before.  It makes a lot of things (such as the identities you point
out) obvious and elegant.

>   We can also see the following identities:
> 
> foldright f as == foldright (.) (map f as) id
> foldleft f as == foldright (flip (.)) (map f as) id
> 
>   I like that second one, after trying to read another definition of 
> left fold in terms of right fold (in the web book "Real World Haskell").
> 
>   The type signature, which could be written (a -> (b -> b)) -> ([a] -> 
> (b -> b)), suggests generalization to another type constructor C: (a -> 
> (b -> b)) -> (C a -> (b -> b)).  Would a "foldable" typeclass make any 
> sense?

As Brandon points out, you have rediscovered Data.Foldable. =) There's
nothing wrong with that, congratulations on discovering it for
yourself!  But again, I like this way of organizing the type
signature: I had never thought of a fold as a sort of 'lift' before.
If f :: a -> b -> b, then foldright 'lifts' f to foldright f :: [a] ->
b -> b (or C a -> b -> b, more generally).  

>   Okay, it goes without saying that this is useless dabbling, but have 
> I entertained anyone?  Or have I just wasted your time?  I eagerly await 
> comments on this, my first posting.

Not at all!  Welcome, and thanks for posting.

-Brent