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

[George Kangas]

Hi, Cafe,

   For no practical purpose, I wrote new definitions of list folds as 
chains of partially applied functions, joined by composition.  I took 
the liberty of rearranging the type signature.

 > foldright :: (a -> b -> b)) -> [a] -> b -> b
 > foldright f = chain where
 >     chain (a:as) = (f a).(chain as)
 >     chain _ = id

 > foldleft :: (a -> b -> b) -> [a] -> b -> b
 > foldleft f = chain where
 >     chain (a:as) = (chain as).(f a)
 >     chain _ = id

   These definitions are point free, with respect to the "initializer" 
argument (which is now the last argument).  Also, you can see how 
similar they are to each other, with the difference boiling down to the 
order of the composition, e.g.:

foldright (+) [1, 2, 3] 0 == ( (1 +).(2 +).(3 +).id ) 0
foldleft (+) [1, 2, 3] 0 == ( id.(3 +).(2 +).(1 +) ) 0


   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?

   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.

very truly yours,

George Kangas