What happened to the subsequent foldl implementation?

Question

For this task, we had to implement foldl by foldr. Comparing both function signatures and the foldl implementation, I came up with the following solution:

myFoldl :: (a -> b -> a) -> a -> [b] -> a myFoldl _ acc [] = acc myFoldl fn acc (x:xs) = foldr fn' (fn' x acc) xs where fn' = flip fn 

Just override the function arguments to satisfy the expected foldr types and the definition of the foldy simulator by recursively applying the passed function. This was a surprise since my teacher rated this answer with zero points.

I even tested this definition, summarizing the intermediate results in the same way as the standard foldl:

  > myFoldl (\a elm -> concat ["(",a,"+",elm,")"]) "" (map show [1..10]) > "((((((((((+1)+10)+9)+8)+7)+6)+5)+4)+3)+2)" > foldl (\a elm -> concat ["(",a,"+",elm,")"]) "" (map show [1..10]) > "((((((((((+1)+10)+9)+8)+7)+6)+5)+4)+3)+2)" 

The correct answer was the following definition:

 myFoldl :: (a -> b -> a) -> a -> [b] -> a myFoldl fz xs = foldr step id xs z where step xga = g (fax) 

Just ask why my previous definition is wrong?

Answer 1

Essentially, your shift is going in the wrong order. I think you did not copy your output from foldl correctly; I get the following:

 *Main> myFoldl (\ a elem -> concat ["(", a, "+", elem, ")"]) "" (map show [1..10]) "((((((((((+1)+10)+9)+8)+7)+6)+5)+4)+3)+2)" *Main> foldl (\ a elem -> concat ["(", a, "+", elem, ")"]) "" (map show [1..10]) "((((((((((+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)" 

so it happens that your implementation receives the first element - the base register - correct, but then uses foldr for the rest, which leads to the fact that everything else is processed in the opposite direction.

There are some good photos of different orders that folds work on the Haskell wiki :

This shows how foldr (:) [] should be the identifier for lists, and foldl (flip (:)) [] should cancel the list. In your case, all he does is put the first element at the end, but leaves everything else in the same order. Here is what I mean:

 *Main> foldl (flip (:)) [] [1..10] [10,9,8,7,6,5,4,3,2,1] *Main> myFoldl (flip (:)) [] [1..10] [2,3,4,5,6,7,8,9,10,1] 

This leads us to a deeper and much more important point - even in Haskell, just because the type line does not mean that your code is working. A system of type Haskell is not omnipotent, and often there are many - even an infinite number of functions that satisfy any given type. As a degenerate example, even the following definition of myFoldl types:

 myFoldl :: (a -> b -> a) -> a -> [b] -> a myFoldl _ acc _ = acc 

So, you need to think about what exactly your function does, even if the types match. Thinking about things like folds can be a bit confusing, but you'll get used to it.