Is this the correct way to write the Haskell foldr function?
I followed the exercises from the YAHT Recursive Datatype section and found the function to be a listFoldr
little tricky (mainly because I did Really understand the difference between foldl
and foldr
at first). When I finally figured out how a function works foldr
, I decided that a simple substitution of function arguments would be done to replace my function listFoldl
with 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 seems to work (I've done 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 very different from mine. They are listFoldl
exactly the same as mine, but look at them listFoldr
:
listFoldr f i [] = i
listFoldr f i (x:xs) = f x (listFoldr f i xs)
Which solution is better, mine or yours? Is one of them wrong? (In my tests, they both end up with the same result ...)
a source to share
I think you are processing elements in "opposite order" and therefore yours is wrong.
You must 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
f s1 s2 = "now processing f(" @ s1 @ "," @ s2 @ ")\n"
where '@' is the string-append operator (I forgot it's in Haskell). The point is just to "measure" the function so you can see what order it calls with different arguments.
(Note that this did not appear in your example, because the math "4-1-2-3" gives the same answer as "4-3-2-1".)
a source to share
Your decision is definitely wrong. You have just implemented foldl
in which the function f
takes arguments in reverse order. For example, what's wrong is foldr (:) []
supposed to be an identification function on lists, but your function changes the list. There are many other reasons why your function doesn't foldr
, like how it foldr
works in infinite lists, and yours doesn't. It is 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 see how it should work foldr
.
a source to share
In the list [x1, x2, ..., xk]
your listFoldr
computes
f xk (... (f x2 (f x1 i)) ...)
then how foldr
should I calculate
f x1 (f x2 (... (f xk i) ...))
(For comparison foldl
calculates
f (... (f (f i x1) x2) ...) xk
Essentially,. listFoldr f = foldl (flip f)
)
You are a test case unfortunately because
3 - (2 - (1 - 4)) = 1 - (2 - (3 - 4))
When you test functions like this, be sure to pass f
one that is non-commutative and non-associative (i.e. the argument and value of the application order), so you can be sure the expression evaluates correctly. Of course, subtraction is non-commutative and non-associative, and you're just out of luck.
a source to share