Is this a correct way of writing the Haskell foldr function?

Question

I was doing the exercises from YAHT's Recursive Datatype section, and found writing the listFoldr function a bit challenging (mainly because I didn't really understand the difference between foldl and foldr at first). When I finally realized exactly how the foldr function worked, I decided that a simple swap of function arguments would be all that'd be needed to change my listFoldl function to a listFoldr function:

listFoldl f i [] = i
listFoldl f i (x:xs) = listFoldl f (f i x) xs

listFoldr f i [] = i
listFoldr f i (x:xs) = listFoldr f (f x i) xs

This appears to work (I did more tests than this):

Main> foldr (-) 4 [1, 2, 3]
-2
Main> listFoldr (-) 4 [1, 2, 3]
-2

But the solution given for the exercise is much different than mine. Their listFoldl is exactly the same as mine, but look at their listFoldr:

listFoldr f i [] = i
listFoldr f i (x:xs) = f x (listFoldr f i xs)

Which solution is better, mine or theirs? Is one of them incorrect? (In my tests, they both end up with the exact same result...)

Answer 1

I think you are processing the elements in the 'opposite order', and so yours is not right.

You should be able to demonstrate this with an example where 'order matters'. For example, something like

listfoldr f "" ["a", "b", "c"]

where 'f' is a function along the lines of

f s1 s2 = "now processing f(" @ s1 @ "," @ s2 @ ")\n"

where '@' is a string-append operator (I forget what it is in Haskell). The point is just to 'instrument' the function so you can see what order it is getting called with the various args.

(Note that this didn't show up in your example because the math "4-1-2-3" yields the same answer as "4-3-2-1".)

Answer 2

Yours is broken. Try it with something that doesn't end up with a single numeric result.

eg: listFoldr (++) "a" ["b", "c", "d"]

You're processing in the wrong direction.

Answer 3

Your solution is definitely incorrect. You have simply implemented a foldl in which the function f takes arguments in the opposite order. For example of what is wrong, foldr (:) [] is supposed to be an identify function on lists, but your function reverses the list. There are lots of other reasons why your function is not foldr, like how foldr works on infinite lists and yours does not. It is a pure coincidence that they are the same in your example, because 3 - (2 - (1 - 4)) == 1 - (2 - (3 - 4)). I think you should start from scratch and look at how foldr is supposed to work.

Answer 4

On a list [x1, x2, ..., xk], your listFoldr computes

 f xk (... (f x2 (f x1 i)) ...)

whereas foldr should compute

 f x1 (f x2 (... (f xk i) ...))

(In comparison, foldl computes

f (... (f (f i x1) x2) ...) xk

Essentially, listFoldr f = foldl (flip f).)

You're test case is unfortunate, because

3 - (2 - (1 - 4)) = 1 - (2  - (3 - 4))

When you are testing functions like these, be sure to pass in an f that is non-commutative and non-associative (i.e., argument and application order matter), so you can be sure the expression is evaluated correctly. Of course, subtraction is non-commutative and non-associative and you just got unlucky.