I'm still a Haskell newbie, so take this with a grain of salt: the type signature of foldr and foldr1 confuses me also. While I understand how each operates, I've never found a description of the type signatures of either functions which explains why the function argument of foldr1 is of type (a -> a -> a) instead of (a -> b -> b). This is the conclusion I came to. Hopefully it helps; if it's wrong, then hopefully it can be corrected.

Suppose we have a list M = [x1, x2, ..., x(n-1), xn], and we evaluate the function:

foldr1 f M = f x1 (f x2 ... (f x(n-1) xn) ...)

We know that for all xi <- M, xi has type a. Suppose that the function f has type (a -> b -> c) and consider the expression f x(i-1) xi, where x(i-1), xi <- M. Since x(i-1) and xi have type a, the expression is well-typed only if the type b is the same as a. Because each such expression resulting from folding f into M becomes the second argument to f, the result of evaluating f must be a value of type a. That is, c must be the same type as a.

With foldr, however, this isn't necessarily the case. Suppose we have a list N = [x1, x2, ..., xn], and we evaluate the function:

foldr f v N = f x1 (f x2 ... (f xn v) ...)

There is no reason that v must have the same type as each xi <- N, since v is not derived from N. You can see that as foldr is evaluated, starting from the most nested f, the value bound to the second argument of each occurrence of f has the same type as the value which is the result of evaluating f. If this is the case, however, then the type of the value which results from evaluating foldr, where v has type b, must be a value of type b.

You might, however, define a function using foldr and foldr1 which produce the same result. For instance,

mySum list = foldr (+) 0 list
mySum' list = foldr1 (+) list

In this case, (+) :: (a -> a -> a). So b is the same type as a and all is well.




On Mon, Jul 26, 2010 at 12:30 AM, Ertugrul Soeylemez <es@ertes.de> wrote:
prad <prad@towardsfreedom.com> wrote:

> i'm trying to make sense of the a vs b in foldr, so here goes:
>
> foldr takes 3 arguments:
>       1. some function f, illustrated within () of type b
>       2. some value of type b
>       3. some list with elements of type a
>
> foldr applies f to each element of [a], computing a new function (f a)
> which is then applied to the item of type b, computing a result of
> type b, which is then combined with #2 (this would be the accumulator)
>
> finally, the net computation of foldr results in some item of type b.

You think too complicated.  It's really very simple.  Look at how foldr
is defined:

 foldr f z []     = z
 foldr f z (x:xs) = x `f` foldr f z xs

In the recursive case the folding function gets its two arguments:  The
first argument is the head element of the list.  The second argument is
the result of folding the rest of the list.  You can read from this
function immediately that it really replaces each (:) by 'f' and the []
by 'z' in a right-associative manner.

 foldr (+) 0 [a,b,c] = a + (b + (c + 0))


> foldr1 takes 2 arguments:
>       1. some function g, illustrated within () of type a
>       2. some list with elements of type a
>
> foldr1 applies g to each element of [a], computing a new function (g
> a) which is then applied to a non-explicitly defined item of type a,
> computing a result also of type a.
>
> the net computation of foldr1 results in some item of type a.

Simple:

 foldr1 f [x]    = x
 foldr1 f (x:xs) = x `f` foldr1 f xs

This is just a simplified version of foldr.  The base element is passed
explicitly in foldr as 'z'.  Here the base element is just the last
element of the list to be folded.  For some folds, having an extra base
element wouldn't make much sense, for example for the 'maximum'
function:

 myMaximum = foldr1 max

This is why there is the foldr1 variant of foldr.  But of course, you
would write 'maximum' as a left fold (foldl1), not a right fold.

 foldr1 max [a,b,c] = a `max` (b `max` c)


> i know how i can use the folds in some situations, but explaining
> their type definitions to reveal how they work, is coming out pretty
> convoluted when i make the attempt. :(

Just read the type of the function and its definition.  For most
functions in Haskell, you will even find that reading the type signature
and the name of the function suffices to understand, what it does.
Trying to interpret combinators (or even to find metaphors, as many
people do) is not always the right thing to do.

However, in this case there is an easy interpretation:  It takes the
list elements and puts a binary operator between each of them.  It also
appends a base element (usually some kind of neutral element or initial
value) to the list, so that the empty list is allowed.  That's it.


Greets,
Ertugrul


--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://ertes.de/


_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners