Recently to better understand the advantages and disadvantages of lazy evaluation, I check for some details of Haskell. I did that to do exercise 5.9 in SDF (Software Design for Flexibility)
More generally, the Lisp community has avoided changing cons to be kons, as recommended by Friedman and Wise (see footnote 17 on page 254). What potentially serious problems are avoided by using cons rather than kons? Assume that we do not care about small constant factors in performance.
kons is just lazy cons.
I found foldl is interesting with one foldl' variant. I checked QA1 How is foldl lazy? with its answer, QA2 foldl parameter order problem and QA3 how to implement foldl with foldr. I understand those. However I am still confused about something said by haskell wiki
You should pick foldl' principally in two cases:
... you do not care about the implicit reversal (for example, because your combining function is commutative like (+), (*), or Set.union) ...
IMHO foldl' does something like "(...((z f x1) f x2)... xn)" which just consumes the list from left to right, then why does the doc say foldl' has "implicit reversal"?
p.s. After understanding what "implicit reversal" means hinted by is7s and Louis Wasserman, here I give more related infos: 0. Here non-commutative function can also have no "implicit reversal", e.g. concat in "foldl parameter order problem" link.
Later after Daniel Wagner's and is7s's answers are given, I found where that ambiguous paragrph is added. Then I checked the author wiki contribution and found this talk
Moreover foldl' conceptually reverses the order of the list is a misleading formulation:
divisel :: [Double] -> Double divisel = foldl (/) 1 diviser :: [Double] -> Double diviser = foldr (/) 1 divisel [1,2] = diviser [1,2] = 0.5Both divide 1 by 2.
I think it would be better to say foldl/foldr associates to the left/right.
--Klt (talk) 14:28, 19 July 2024 (UTC)
As the original author of the erroneous language, I think you are right.
CarlEdman (talk) 15:07, 19 July 2024 (UTC)
What Klt says at the end is same as the shared part of those 2 answers
a reversal of association
evaluate as follows: ...
But IMHO the (/) example is not good although works sometimes as that talk shows if identity holds, i.e. (1 / 1) == 1 in foldr example and (2 / 1) == 2 in foldl example there. The reason is due to (/) is not associative. That is said by "foldl parameter order problem" link. So (foldl (/) 1 [2,2]) /= foldr (/) 1 [2,2] since (1 / 2) /= 2.
I can provide a commutative example where foldl and foldr return different result.
i.e. foldr (++) "c" ["a", "b"] example of Daniel Wagner's which doesn't use one correct identity value (see QA2).
For one more detailed explanation of "implicit reversal", please see is7s's answer and this chat comment for the related wiki contents.
I think the wiki has been imprecise. Instead of commutative, it should say associative; the "reversal" is a reversal of association.
foldr1 (+) [x0, x1, x2, x3, ...] = x0 + (x1 + (x2 + (x3 + ...)))
foldl1 (+) [x0, x1, x2, x3, ...] = (((x0 + x1) + x2) + x3) + ...
I've used foldr1 and foldl1 to avoid quibbles about the base case, which also moves in a meaningful way. In most cases, the base case is a neutral element, so this doesn't matter, but I suppose technically it could be another candidate for what is meant by "implicit reversal" when the base case is not neutral. For example:
> foldr (++) "c" ["a", "b"]
"abc"
> foldl (++) "c" ["a", "b"]
"cab"
The base case appears at the "reversed" end of the calculation. I really do not think this is what the wiki was talking about, though.