Am Sonntag, 6. August 2006 11:50 schrieb algorithms@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