[Haskell-cafe] Exercise in YAHT

[Daniel Fischer]

Am Sonntag, 6. August 2006 11:50 schrieb algorithms at gmx.de:
> Dear Hugs users,
>
> could you answer the following question from a Haskell novice?
>
> In "Yet another Haskell Tutorial" by Hal Daumé III there is the following
> exercise:
>
> Exercise 4.8 Write functions listHead, listTail, listFoldl and listFoldr
> which are equivalent to their Prelude twins, but function on our List
> datatype. Don’t worry about exceptional conditions on the first two.
>
> My question is solely on listfoldr, in fact I only want to ask whether the
> solution provided in the tutorial is really so obviously wrong as I
> perceive it to be:
>
> (What follows uses the definition
>
> data List a = Nil
>
>             | Cons a (List a)
>
> )
>
>
>
> listFoldr f y Nil = y
> listFoldr f y (Cons x xs) = f x (foldr f z xs)
>
>
> This IS wrong, isn't it? The y does not even appear after all.

Yes, definitely wrong. Obviously Hal was tired when this slipped past his 
eyes. The "z" should be "y" and of course he can't use foldr here, he meant 
listFoldr (and typed foldr out of habit, probably).
So:

listFoldr f y Nil = y
listFoldr f y (Cons x xs) = f x (listFoldr f y xs)

>
> And what can you say about my attempt
> for listFoldr?
>
> listFoldr f y Nil = y
> listFoldr f y (Cons x xs) = f y (listFoldr f (f y x) xs)
>

You should apply f only once to x, this way you fold in f from the left and 
from the right, so you get different results:
foldLR f y [] = y
foldLR f y (x:xs) = f x (foldLR f (f x y) xs)
-- I changed the argument order of the inner application of f, so foldLR has 
the same type as foldr

Prelude> :t foldLR
foldLR :: (a -> t -> t) -> t -> [a] -> t
Prelude> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
Prelude> foldLR (+) 0 [1 .. 10]
110
Prelude> foldLR (*) 1 [1 .. 6]
518400
Prelude> foldr (:) [] [1 .. 10]
[1,2,3,4,5,6,7,8,9,10]
Prelude> foldLR (:) [] [1 .. 10]
[1,2,3,4,5,6,7,8,9,10,10,9,8,7,6,5,4,3,2,1]

you see what's going on, don't you?


>
> My attempt yields a similar, albeit not identical result compared with the
> Prelude function foldr when :t-ing it under Hugs:
>
> Hugs> :t foldr
> foldr :: (a -> b -> b) -> b -> [a] -> b
>
> Hugs> :t listFoldr
> listFoldr :: (a -> a -> a) -> a -> List a -> a
>
That's because of the (f y x) in your definition, let's do some type 
inference:
1) listFoldr f y Nil = y
so listFoldr takes three arguments, 
f - whose type we know nothing about yet and call tf for the moment
y - the type of which we also don't know and call ty
a third argument, which may be Nil and so has type List tl for some - as yet 
completely arbitrary type tlist
and returns the second of its arguments, so from the first equation we find

listFoldr :: tf -> ty -> List tlist -> ty

2) listFoldr f y (Cons x xs) = f x (listFoldr f (f y x) xs)
here we see that f is applied to two arguments (twice), hence has type
ta1 -> ta2 -> tres, so we found out more about tf.
Now in the outer application of f, the first argument of f is x, of type 
tlist, the second argument is a result of listFoldr, hence of type ty and the 
result of this application of f is the overall result of listFoldr, hence has 
type ty as we know from above, so
ta1 = tlist
ta2 = ty
tres = ty, yielding
tf = tlist -> ty -> ty
and
listFoldr :: (tlist -> ty -> ty) -> ty -> List tlist -> ty

which we'd want, but we have a further application of f, which might provide 
further information, namely f y x
Now we know f's type
tlist -> ty -> ty,
so we deduce
y :: tlist
x :: ty,
which together with y :: ty yields tlist = ty, hence
listFoldr :: (ty -> ty -> ty) -> ty -> List ty -> ty
and now rename ty as a.

>
> Thank you very much.
>
> Christian

HTH,
Daniel

-- 

"In My Egotistical Opinion, most people's C programs should be
indented six feet downward and covered with dirt."
	-- Blair P. Houghton