[Haskell-cafe] Pretty little definitions of left and right folds
kangas at math.ku.edu
Fri Jun 20 19:15:20 EDT 2008
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
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,
More information about the Haskell-Cafe