[Haskell-cafe] Pretty little definitions of left and right folds
Brent Yorgey
byorgey at seas.upenn.edu
Fri Jun 20 22:31:17 EDT 2008
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
More information about the Haskell-Cafe
mailing list