List.foldl actually folds right

[kspeakman]

Elm's List.foldl implementation is the same as reversing the list and folding from the right. This does not produce equivalent results to left folding when the operation is left associative only.

Example:

List.foldl (++) "" [ "a", "b", "c" ]
-- returns "cba"
-- expands to ("c" ++ ("b" ++ ("a" ++ "")))

List.foldl (-) 0 [ 1, 2, 3 ]
-- returns 2
-- expands to (3 - (2 - (1 - 0)))

The example given in the documentation List.foldl (::) [] [1, 2, 3] shows that it is right-building (a reversed list) because cons is right-associative only. The expectation is that cons is incompatible with left fold and a right-fold would be used instead.

The expected behavior of a left fold is that it expands from the left instead of the right:

List.foldl (++) "" [ "a", "b", "c" ]
-- expected: "abc"
-- expected expansion: ((("" ++ "a") ++ "b") ++ "c")

List.foldl (-) 0 [ 1, 2, 3 ]
-- expected: -6
-- expected expansion: (((0 - 1) - 2) - 3)

This is fixed by changing the parameter order of the List.foldl function from a -> b -> b to b -> a -> b. This is a breaking change.

The reason for left or right-building based on parameter order can be seen by expansion:

a -> b -> b
expands: aN -> ( ... -> (a1 -> (a0 -> b)))

b -> a -> b
expands: (((b -> a0) -> a1) -> ... ) -> aN

I posted on the discussion list here.

[process-bot]

Thanks for the issue! Make sure it satisfies this checklist. My human colleagues will appreciate it!

Here is what to expect next, and if anyone wants to comment, keep these things in mind.

[process-bot]

Thanks for the issue! Make sure it satisfies this checklist. My human colleagues will appreciate it!

Here is what to expect next, and if anyone wants to comment, keep these things in mind.

[jvoigtlaender]

I don't see how this is a bug, which is what the issue tracker here is for. Close?

What it is, is that the function is not the function you would like. But a bug? No. What specification does it violate, and who said that that's the specification to adhere to?

In any case, saying that the function does not fold from the left is too strong a statement. It does fold from the left, just with the flipped function. For example, List.foldl (++) "" [ "a", "b", "c" ] is f (f (f "" "a") "b") "c", with f = flip (++). Obviously folding from the left.

[jvoigtlaender]

I don't see how this is a bug, which is what the issue tracker here is for. Close?

What it is, is that the function is not the function you would like. But a bug? No. What specification does it violate, and who said that that's the specification to adhere to?

In any case, saying that the function does not fold from the left is too strong a statement. It does fold from the left, just with the flipped function. For example, List.foldl (++) "" [ "a", "b", "c" ] is f (f (f "" "a") "b") "c", with f = flip (++). Obviously folding from the left.

[kspeakman]

It's mathematically wrong as defined. Yes, you could call List.foldl (flip (++)) "" ["a", "b", "c"] To get "abc", but this is unexpected behavior from most functional languages and math. Folding left usually means "use this operation to fold left" instead of "you have to flip your operation to make foldl actually fold left".

…

On Fri, Dec 9, 2016 at 2:24 PM Janis Voigtländer ***@***.***> wrote: I don't see how this is a bug, which is what the issue tracker here is for. Close? What it is, is that the function is not the function you would like. But a bug? No. What specification does it violate, and who said that that's the specification to adhere to? In any case, saying that the function does not fold from the left is too strong a statement. It does fold from the left, just with the flipped function. For example, List.foldl (++) "" [ "a", "b", "c" ] is f (f (f "" "a") "b") "c", with f = flip (++). Obviously folding from the left. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <https://github.com/elm-lang/core/issues/779#issuecomment-266114125>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AEXtDKDEKrB-VdpZ30U5xlmvD5D9r0l7ks5rGbkLgaJpZM4LJKQ_> .

[kspeakman]

It's mathematically wrong as defined. Yes, you could call List.foldl (flip (++)) "" ["a", "b", "c"] To get "abc", but this is unexpected behavior from most functional languages and math. Folding left usually means "use this operation to fold left" instead of "you have to flip your operation to make foldl actually fold left".

…

On Fri, Dec 9, 2016 at 2:24 PM Janis Voigtländer ***@***.***> wrote: I don't see how this is a bug, which is what the issue tracker here is for. Close? What it is, is that the function is not the function you would like. But a bug? No. What specification does it violate, and who said that that's the specification to adhere to? In any case, saying that the function does not fold from the left is too strong a statement. It does fold from the left, just with the flipped function. For example, List.foldl (++) "" [ "a", "b", "c" ] is f (f (f "" "a") "b") "c", with f = flip (++). Obviously folding from the left. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <https://github.com/elm-lang/core/issues/779#issuecomment-266114125>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AEXtDKDEKrB-VdpZ30U5xlmvD5D9r0l7ks5rGbkLgaJpZM4LJKQ_> .

[jinjor]

Elm's List.foldl implementation is the same as reversing the list and folding from the right.

For this at least, I would repeat jvoigtlaender's mention. Not doing "folding from the right".

Folding left usually means "use this operation to fold
left" instead of "you have to flip your operation to make foldl
actually fold left".

Mathematical operator is the minority. Most of functions in Elm are defined like a -> b -> b. It is useful for currying. So you don't need to flip functions for most cases.

substractionBy a b = b - a

List.foldl substractionBy 0 [ 1, 2, 3 ]

[jinjor]

Elm's List.foldl implementation is the same as reversing the list and folding from the right.

For this at least, I would repeat jvoigtlaender's mention. Not doing "folding from the right".

Folding left usually means "use this operation to fold
left" instead of "you have to flip your operation to make foldl
actually fold left".

Mathematical operator is the minority. Most of functions in Elm are defined like a -> b -> b. It is useful for currying. So you don't need to flip functions for most cases.

substractionBy a b = b - a

List.foldl substractionBy 0 [ 1, 2, 3 ]

[kspeakman]

@jvoigtlaender said it is not "folding from the right" with the proviso that you flip the operator when you call foldl. Needing to apply a flip to make it fold left is still not actually folding left by itself. No amount of re-explanation is going to fix that.

Your subtractionBy definition is literally the same as flip (-). You could define subtractionBy = flip (-) and it would be functionally equivalent to your definition. Try it in http://elm-lang.org/try.

a -> b -> b only works for (either-way) associative and right-associative functions. See my original post on this issue at the bottom for the explanation of how that works (expands). I didn't discover the math behind that, and I can't change whether it's true or not. When I use an operator that says it folds left, I expect to be able to use a left-associative operator. If only foldr exists, then I would just figure out a way to call that with flip. But I assume foldl exists for a reason. Currently, it provides no different functionality from foldr (and reverse).

List.foldl (-) 0 [1, 2, 3]
==
List.foldr (-) 0 [3, 2, 1]

[kspeakman]

@jvoigtlaender said it is not "folding from the right" with the proviso that you flip the operator when you call foldl. Needing to apply a flip to make it fold left is still not actually folding left by itself. No amount of re-explanation is going to fix that.

Your subtractionBy definition is literally the same as flip (-). You could define subtractionBy = flip (-) and it would be functionally equivalent to your definition. Try it in http://elm-lang.org/try.

a -> b -> b only works for (either-way) associative and right-associative functions. See my original post on this issue at the bottom for the explanation of how that works (expands). I didn't discover the math behind that, and I can't change whether it's true or not. When I use an operator that says it folds left, I expect to be able to use a left-associative operator. If only foldr exists, then I would just figure out a way to call that with flip. But I assume foldl exists for a reason. Currently, it provides no different functionality from foldr (and reverse).

List.foldl (-) 0 [1, 2, 3]
==
List.foldr (-) 0 [3, 2, 1]

[avh4]

elm-lang/core is not going to change based on the discussion here. If you have examples of real-world use cases where this makes a difference, please share them on elm-discuss. Another approach would be to publish a package that implements the API you want and encourage people to try it out.

[avh4]

elm-lang/core is not going to change based on the discussion here. If you have examples of real-world use cases where this makes a difference, please share them on elm-discuss. Another approach would be to publish a package that implements the API you want and encourage people to try it out.

[kspeakman]

Just trying to help correct something that operates unexpectedly and is provably wrong. I made a mental note that such pursuits are unwelcome. That will save us all some time going forward.

[kspeakman]

Just trying to help correct something that operates unexpectedly and is provably wrong. I made a mental note that such pursuits are unwelcome. That will save us all some time going forward.

[mgold]

He literally gave you two different paths to continue "such pursuits", and is (correctly) warning you away from a path that will not be fruitful given how the community operates.

Secondly, and this is a culture shift from Haskell, Elm considers very few API designs that (type-check) to be "provable wrong", and has a different perspective of what "unexpected" operation is.

[mgold]

He literally gave you two different paths to continue "such pursuits", and is (correctly) warning you away from a path that will not be fruitful given how the community operates.

Secondly, and this is a culture shift from Haskell, Elm considers very few API designs that (type-check) to be "provable wrong", and has a different perspective of what "unexpected" operation is.

[nateabele]

At a minimum, this unexpected behavior should be documented. I spent a good bit of time staring at the docs, trying to figure out what I was missing, since I figured there was no way it would work the exact opposite of basically every other left-fold/left-reduce everywhere. 😕 Thoroughly confusing.

[nateabele]

At a minimum, this unexpected behavior should be documented. I spent a good bit of time staring at the docs, trying to figure out what I was missing, since I figured there was no way it would work the exact opposite of basically every other left-fold/left-reduce everywhere. 😕 Thoroughly confusing.

[nateabele]

Secondly, and this is a culture shift from Haskell

Well, and JavaScript, and functional JS libraries (i.e. Ramda), and Java, and Python... heck, even PHP.

[nateabele]

Secondly, and this is a culture shift from Haskell

Well, and JavaScript, and functional JS libraries (i.e. Ramda), and Java, and Python... heck, even PHP.

[rtoal]

Agree with @nateabele here; the documentation at http://package.elm-lang.org/packages/elm-lang/core/5.1.1/List might consider a note describing how this function works. I too stared for a bit at an unexpected result from List.foldl because unfortunately I have used a few other languages where foldl worked a certain way and silly me I assumed Elm would fold left the same way.

All the documentation says is "reduce a list from the left." I agree that Elm's behavior is not "wrong." And I agree there's nothing inherently wrong with taking a common term like foldl and implementing it differently than in (nearly every?) other language(s). And I even understand how this use of foldl more elegantly meshes with the way Elm tends to work (a->b->b instead of b->a->b). But perhaps a note saying that Elm folds left differently from most other languages, and in fact does so like this:

    List.foldl f x [y1, y2, ..., yk]
        = f yk ... (f y2 (f y1 x)) ...)

would be more helpful than just saying "reduce a list from the left." I get it that if you carefully look at the type signature and you carefully look at the example, you can figure this all out, but maybe a footnote will save some newbie a little bit of time.

TL;DR I agree there's nothing wrong here other than Elm just being different. But the potential for confusion exists, so why not a footnote in the docs?

[rtoal]

Agree with @nateabele here; the documentation at http://package.elm-lang.org/packages/elm-lang/core/5.1.1/List might consider a note describing how this function works. I too stared for a bit at an unexpected result from List.foldl because unfortunately I have used a few other languages where foldl worked a certain way and silly me I assumed Elm would fold left the same way.

All the documentation says is "reduce a list from the left." I agree that Elm's behavior is not "wrong." And I agree there's nothing inherently wrong with taking a common term like foldl and implementing it differently than in (nearly every?) other language(s). And I even understand how this use of foldl more elegantly meshes with the way Elm tends to work (a->b->b instead of b->a->b). But perhaps a note saying that Elm folds left differently from most other languages, and in fact does so like this:

    List.foldl f x [y1, y2, ..., yk]
        = f yk ... (f y2 (f y1 x)) ...)

would be more helpful than just saying "reduce a list from the left." I get it that if you carefully look at the type signature and you carefully look at the example, you can figure this all out, but maybe a footnote will save some newbie a little bit of time.

TL;DR I agree there's nothing wrong here other than Elm just being different. But the potential for confusion exists, so why not a footnote in the docs?