fold function argument order

[Zsombor Nagy]

Hi!

I wonder why is the foldl in Elm and in Haskell calling the binary operator with arguments in a different order?

foldl (\t acc -> acc + 1) 0 [1, 1, 1, 1, 1, 1]
haskell: 2
Elm: 6

For me the haskell way seems more straightforward, but maybe that "optimal composibility guideline" makes this turn around?



zs

[Tim hobbs]

Well, elm's ordering is more useful.  For example, I recently had a case where I wrote:

let
  irrelivantFuncitonName fold = fold blabla default list
in
 irrelivantFunctionName foldl + irrelivantFuncitonName foldr

In Haskell, the same example ends up being

let
  irrelivantFuncitonName fold = fold blabla default list
in
 irrelivantFunctionName foldl + irrelivantFuncitonName (\f d l-> foldr (\a b->f b a) d l)

Tim

[Evan Czaplicki]

It's partly about composability (i.e. the data structure should be last).

It is also about reuse. In Elm it is valid to say:

foldl (::) []

foldr (::) []

If I want to change the order of my traversal, I should not also need to change the definition of mildly related functions or start using flip on things.

Finally, once you know that the accumulator is always the second argument, you do not have to look at docs anymore. Even now I forget the order of arguments in Haskell's folds and need to look it up.

I first learned this way from Standard ML, and it is my favorite by far.

--
You received this message because you are subscribed to the Google Groups "Elm Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elm-discuss...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Balazs Komuves]

The Haskell version of the foldl is the "right one" in the following sense:

foldl makes sense in general for left-associative operators, and foldr makes sense for right-associative operators.

Left-associative operators must have the type (a -> b -> a), while right-associative operators must have type (a -> b -> b).

I think the fact that you cannot change a foldr to foldl without changing the types is actually an advantage: it forces you to think about which version is the "proper" one, and you cannot accidentally do the wrong one. Of course sometimes it can be inconvenient.

What I somewhat dislike in the Haskell version of foldr (not foldl), is that while

(foldl . foldl . foldl) etc makes sense, (foldr . foldr) does not; for that to work you would have to flip the last two arguments:

myfoldr :: (a -> b -> b) -> ([a] -> b -> b)

myfoldr f xs y = foldr f y xs

But the practicality of this change is debatable, I guess.

Balazs

[Evan Czaplicki]

I think this might be a religious debate on some level. My first functional languages were Scheme and Standard ML. The libraries I just linked both use the same argument order for foldl and foldr as in Elm. I was raised a certain way and it just stuck in my mind. I suspect that everyone prefers the order they learned first because it matches their mental model.

I wrote up a bunch of "reasoning", but really, I am just engaging in the religious debate. I'd feel bad deleting it all though, so here is some of it:

OCaml's list library does it the way you suggest. I find this order offensive on some level.

The big questions for "physical" argument order are as follows:

• What is the type of `fold` or `reduce`? When you fold an unordered thing, is it from the right or the left?
• What is the type of `foldp`? Which way does time go? Is this cultural?

I don't find these questions particularly useful, and I don't think programmers should have to wonder about them to use fold and foldp.

At the end of the day, I chose the types on purpose. I find them easier to use, easier to teach, easier to understand. I want to keep them this way.

[Balazs Komuves]

I was not engaging in debate, religious or not (though I tend to have very strong opinions about these questions). I was explaining why I think Haskell uses the order it uses (because it is distinguished from a mathematical viewpoint). Of course you are not required to follow that convention, I was just pointing out that it is not simply an ad-hoc choice.

Balazs

[Evan Czaplicki]

Gotcha, I definitely see the reasoning :)

[Kasey Speakman]

(deleted and corrected original post with proper expansion of Elm's foldl)

I know this is a really old thread, but I ran into this precise question and thought I would add a perspective.

The form a -> b -> b is not left-building, regardless of the direction you are traversing the list.

An example: Starting from zero, subtract the numbers 1, 2, and 3. The expected answer is -6.

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

-> returns -6 in Haskell (well, actually tested in F# which uses same order as Haskell)

    expands to: ((0 - 1) - 2) - 3 = -6

-> returns 2 in Elm

    expands to: 3 - ((1 - 0) - 2)

Elm's expansion is wonky for this. It appears to be center-building:

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

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

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

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

When a and b are the same type it will only return the correct answer if the fold operation is also commutative or if flip is used to correct the ordering. When a and b are not the same type, the compiler will provide an error for wrong ordering of course.

I started out on the side that a -> b -> b was correct as that feels like proper "reduction" or chainable syntax. But after exploring it, it is clearly not left-building. Makes sense when you consider this form is used with pipe to convert right-building operations into left-reading code. e.g. a |> f |> g |> h instead of h (g (f a))

[Aaron VonderHaar]

What's confusing here is how currying works with infix operators.  It's idiomatic in Elm to have your accumulator be the last argument, and, for instance, if you were writing your own data type, you would want to write your functions so that they can be chained together easily:

    myMatrix

        |> scale 2

        |> subtract 5

        |> subtractMatrix myOtherMatrix

        |> normalize

But as an infix operator (-) is not able to follow that convention;

    5

        |> (-) 3

        |> (-) 1

is confusingly equivalent to `(1 - (3 - 5))` rather than to `5 - 3 - 1`

If you had a function `subtract` such that

    5 |> subtract 3 |> subtract 1 == (5 - 3 - 1)

then you could use that function with fold as you intend

    List.foldl subtract 0 [1, 2, 3, 4]  ==  -10

You can achieve the same result with

    List.foldl (flip (-)) 0 [1, 2, 3, 4]  ==  -10

Another way to put it is, in Elm, folds expand in the following way:

    List.foldl f x [b, c, d]  ==  x |> f b |> f c |> f d 

    List.foldr f x [b, c, d]  ==  f b <| f c <| f d <| x

To unsubscribe from this group and stop receiving emails from it, send an email to elm-discuss+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Kasey Speakman]

You're confusing pipe's syntax and infix. Pipe is defined like this:

(|>) x f = f x

And used like this

x |> f == f x

So pipe has an inherent flip because it is used to chain otherwise right-building statements.

e.g. 

List.sum (List.filter isOdd [1, 2, 3])

vs

[1, 2, 3]

|> List.filter isOdd

|> List.sum

Pipe is inherently right-building, so operations like subtract or string concatenation are not suitable for it since they are only left associative.

List.foldl (++) "" ["The ", "quick ", "brown "]  -- returns "brown quick The "

For more options, visit https://groups.google.com/d/optout.

[Kasey Speakman]

Sorry, that last bit was an example of what happens in Elm when folding with string concat (++). That's unexpected behavior from a left fold.

List.foldl (++) "" ["The ", "quick ", "brown "]  -- returns "brown quick The "

[Kasey Speakman]

Ok, correction

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

-- returns 2

-- expands to 3 - (2 - (1 - 0)) = 2

During my testing last night, I had a typo (foldr instead of foldl) when I was testing the expansions. That was the center-building behavior.

Using the form a -> b -> b is right-building regardless of the order the list is traversed. Traversing from head to tail is equivalent to reversing the list and building right. This is obviously broken for left-associative only operations and not expected in general.

[Nick H]

I would disagree with "not expected in general." In general -- when a and b are different types -- Elm's API design guidelines should set you up to always expect a -> b -> b and never b -> a -> b. If the definition of foldl were changed to take the latter, it would be the only exception to this expectation.

To unsubscribe from this group and stop receiving emails from it, send an email to elm-discuss+unsubscribe@googlegroups.com.

[Nick H]

expection to this exceptation.

[Max Goldstein]

Fold takes arguments in the same order as update: the element and then the accumulator.

Don't trust partial application of infix ops unless you know they are commutative. Write a lambda instead.

[Kasey Speakman]

It's about associativity. Some operations have specific associativity even when a and b are different types.

Cons (::) is a great example of this. Cons is only right associative even when `a` is Int and `b` is List Int. You cannot write `[] :: 1 :: 2 :: 3`, because cons does not work from the left, but from the right: `1 :: 2 :: 3 :: []`.

Switching to same type: subtraction and string concatenation are left associative. Addition is (either-way) associative (order doesn't matter).

When folding over a list, I need to know whether it will handle left- or right-associative operators. The naming of foldl would suggest left. and foldr would suggest right.

Both fold functions in Elm are right associative (due to the a -> b -> b folder definition). You can already define a left associative operation with foldr using reverse and flip, so there's no reason for foldl to exist except to be a convenience for using left associative operations. And it doesn't event do that.

I just said a bunch of words that probably nobody will bother (or has time) to dig into to discover my point. So I'll leave you with this. Plug this into Elm Hello World example.

import Html exposing (text)

main =

     List.foldl (++) "" ["a", "b", "c"]

  == List.foldr (++) "" ["c", "b", "a"]

  |> toString

  |> text

Now ask yourself if you would expect the given outcome just by looking at it.

[Kasey Speakman]

Minor term correction. String concatenation isn't left-associative (duh on my part). It's just not commutative (the order can't be swapped and still get the same answer, unlike addition/multi).

[Janis Voigtländer]

Kasey, you keep talking as if there were a mathematical, semantic concept of “left-associativity” (and the same for “right-associativity”). But there isn’t. Or can you give a definition?

A definition of the mathematical, semantic concept of “associativity” is: “An operator is associative if applying that operator to a and b (in that order) and then applying it to the result of that and c (in that order) evaluates to the same result as applying it to a and to the result of applying it to b and c (in those orders).” No corresponding concept of “left-associativity” exists.

Reaching for something like “left-associativity means that a op b op c should be read as (a op b) op c“ means that you are talking of a parsing convention, not a mathematical property of the operator.

And all that is relevant because you are trying to make an argument about the behavior of some function being “mathematically wrong”, and basing that on something like “because it does not respect left-associativity”, which is moot given that there is no semantic property that you could state and see violated.

Similarly, you make a statement about “current foldl does not fold from the left”, but haven’t defined semantically what it means to “fold from the left”. One such definition could be “folding from the left means that the left-most element is first combined with the second-left-most element before any other elements are used”. In that sense, current foldl is folding from the left. If you want to say that it is not, you have to provide an alternative definition of the concept of “folding from the left”. Can you? Can you tell us what it is?

Aside: About the concepts of associativity, you may want to compare https://en.wikipedia.org/wiki/Operator_associativity and https://en.wikipedia.org/wiki/Associative_property, and to consider the explicit pointer from the former to the latter as regards “the mathematical concept of associativity”, as well as taking note of the fact that the latter page does not mention anything like “left-associativity” and “right-associativity” (because, I repeat, those do not exist as mathematical, semantical-as-opposed-to-syntactical concepts).

​

To unsubscribe from this group and stop receiving emails from it, send an email to elm-discuss+unsubscribe@googlegroups.com.

[Kasey Speakman]

I read the associativity article. You should examine this wikipedia article on fold.

OCaml, F#, Haskell, Scala, Clojure, Elixir, etc. all have left folds as described in this article. Elm does not. I included a quote from it below.

"The folding of the list [1,2,3,4,5] with the addition operator would result in 15, the sum of the elements of the list [1,2,3,4,5]. To a rough approximation, one can think of this fold as replacing the commas in the list with the + operation, giving 1 + 2 + 3 + 4 + 5."

Elm would generate 5 + 4 + 3 + 2 + 1. Since + is associative it does not matter. But using -, Elm's result would be incorrect.

So when you go from Elm on the front end to <insert modern function language here> on the back end, Elm's current foldl syntax lays something on the floor for you to trip over.

[Janis Voigtländer]

I do know how foldl is in other languages. And that it is different in those other languages than it is in Elm. And I even agree that it would be better that foldl in Elm is as in other languages (or Haskell, specifically). I think I even argued for this on this mailing list in the past.

But all this is not what my message to you was about. I pointed out that you have no argument for this position that is of the form “… because of mathematics”. All the argument you (or I) have is that other languages do something different and that it would be nicer if Elm behaved like those, also because what those do is easier to explain/visualize. You didn’t seem to acknowledge that this is the only argument you have, before. Your latest message suggests you now do see that this is the only argument you have. (It’s a fine argument. But it’s only this one, not a stronger mathematical argument as you previously tried to make exist.)

​

To unsubscribe from this group and stop receiving emails from it, send an email to elm-discuss+unsubscribe@googlegroups.com.

[Kasey Speakman]

Yes, I did confuse mathematically associativity with programming language associativity (which adds left and right distinctions for expression evaluation) in the previous post. I stand corrected.

A mathematically associative operation will work from either left or right when folding. But a non-associative operation's result depends on which direction it is processed. Foldl is expected to process left. If Elm's foldl where instead named foldHeadToTail, I could hardly argue it doesn't obey the contract it sets up. But its name and description in the documentation "Reduce a list from the left." makes it inaccurate and lacking "visually honesty" in the way you call it.

And I do get the mathematically wrong answer on foldl when using mathematically non-associative operations (like subtraction). That's provided we agree on the definition of which side of the list is the "left" side.

For bonus visual honesty, I also like the right fold syntax in languages that put the initial value as the last argument. It guides you to pick the correct fold for the operator, since it's easy to visualize the expansion. E.g.

List.foldBack (::) [1, 2, 3] []

    ==               1 :: 2 :: 3 :: []

I think the reason for all the right associativity in Elm is an emphasis on chaining/piping, which is inherently right-associative. E.g. step3 ( step2 ( step1 x) ) == x |> step1 |> step2 |> step3 == step1 >> step2 >> step3

I am keen on composition/piping myself, but ultimately pattern doesn't fit everywhere.

[Janis Voigtländer]

And I do get the mathematically wrong answer on foldl when using mathematically non-associative operations (like subtraction). That's provided we agree on the definition of which side of the list is the "left" side.

Well, still not quite for me. I’m sure we both agree what the “left” side of the list is. And still I don’t think there is an argument to make that hence Elm’ foldl‘s answer is mathematically wrong. The fact that we agree what the left side of the list is does not mean that foldl (-) 0 [1,2,3] needs to evaluate to ((0 - 1) - 2) -3. It can evaluate to 3 - (2 - (1 - 0)) without us disagreeing what is “left”. In other words, “leftiness” is not at issue here. Both ((0 - 1) - 2) -3 and 3 - (2 - (1 - 0)) do work “from the left”. They combine elements in the order in which they appear in the list from left to right. One could argue that the real thing at issue here is not what “left” means, but what “folding” means. You take it to mean to literally replace :: by (-) and you are only willing to argue about how the result is bracketed. But one can take “folding” to simply mean that stuff gets accumulated via an operator, and “left folding” then means that more-left-sitting elements get accumulated earlier. And Elm’s foldl is perfectly mathematically correct according to this meaning.

Of course, that’s back to a point I made already the other day. There’s nothing “mathematically wrong” about Elm’s foldl unless one postulates “mathematically correct” to mean “ foldl needs to be the specific operation it is in Haskell etc.” But that’s not a mathematical argument.

​

[Kasey Speakman]

foldl doesn't say it folds head to tail (which would be accurate). It says it folds from the left ("to the right" is understood... where else are you going to go from the left?).

I'm not going to quibble over what "left" is, nor what processing something from the left to right means. If that's not understood between us, then we don't have enough basis to discuss that aspect.

But I would like to point out that: the fact that it is a source of confusion only brings to the surface the imprecision of its name.

[Janis Voigtländer]

I would like to point out that: I’m sure neither of us is too stupid to know what the other means. :-)

And I don’t think there is no basis to discuss these aspects. In fact, here is a possible explanation of why this all seems so fuzzy: One could distinguish between “from left to right in terms of the input” and “from left to right in the output”. Then:

• ((0 - 1) - 2) - 3 processes elements from left to right in terms of the input and happens to produce an expression that is nested from left to right in the output
• 3 - (2 - (1 - 0)) processes elements from left to right in terms of the input and happens to produce an expression that is nested from right to left in the output

The distinction you make between “head to tail” and “left to right” (as if you would be fine with the current Elm behavior of foldl aka foldLeftToRight if it were simply called foldHeadToTail instead) is not one I can relate to.

​

--

You received this message because you are subscribed to the Google Groups "Elm Discuss" group.

To unsubscribe from this group and stop receiving emails from it, send an email to elm-discuss+unsubscribe@googlegroups.com.

[Kasey Speakman]

The two examples you provide, the first is left-to-right on both input and output. The other (Elm's) is not. Right fold is right-to-left on both input and output. The lack of symmetry between the two operations only reinforces the issue.

To unsubscribe from this group and stop receiving emails from it, send an email to elm-discuss...@googlegroups.com.

[Kasey Speakman]

I also would not care for a foldHeadToTail function where the order of operations is unspecified. It would be unusable without knowing the order in some cases. I was just pointing out that it's more accurate to foldl's implementation, considering the modern body of work that already implements foldl differently.

[Janis Voigtländer]

The two examples you provide, the first is left-to-right on both input and output. The other (Elm's) is not. Right fold is right-to-left on both input and output. The lack of symmetry between the two operations only reinforces the issue.

I don't disagree with your preference for symmetry. I just pointed out that if one considers processing order on the input (only), there is no basis to say that Elm's foldl is wrong or not left-to-right. That one should consider both input and output order/nesting when pondering the name of this function seems not to have been a principle of the maker of that decision.

[Kasey Speakman]

It's not only a matter of preference, but getting the result that you expect from the statement. Whether you look at visual expansion or the way the operation is defined most other places, I'm not sure how it could be considered working as described much less working as expected. Maybe it is working as intended, but that's not a criteria I'm basing my statements on.

[Janis Voigtländer]

Well, both in terms of "described" and "expected", all it takes is to have a look at the function's type. I personally often don't care much about prose in function documentation. For this specific function, take a look at the type (the placement of "a"s and "b"s) and that together with the "l" mnemonic from the function's name describes pretty much exactly how list elements will be combined. Or am I overlooking right now another way in which a function of that polymorphic type could process a list from left to right while producing some output? 

And likewise, seeing that function signature and knowing that the function is not the/a right-fold, there is only exactly one behavior I would expect from it, and it's the one it indeed has. :-)

(Of course, if the function had the implementation you want it to have, it would also have a different type, and that type would be equally descriptive for that other implementation's behavior, and would also raise exactly the correct expectations for that implementation.)

[Kasey Speakman]

Having the behavior you expect? So if you write List.foldl (++) "" ["a", "b", "c"], you expect to get "cba"? This does not produce what you visually see in the calling statement, nor what what is produced from by common definition of left fold (in case you want to argue about common definition, see above mentioned wikipedia article). How is that expected?

I certainly could consult the documentation before writing any given statement, but needing to do so to verify a common operation produces the expected result is a symptom of a problem.

This conversation is stagnating, saying the same things in different ways, arguing semantics and word meanings. So if there's no new information in the next post, the last word is yours. I do understand that your library would be affected by such a change. But I wouldn't worry about it, as I doubt this will get fixed anyway. In fact, it's this way because preference trumped other concerns during design. No disrespect to Evan... we've all been there.

[John Mayer]

FWIW, I think we (Elm) got this one wrong, and Kasey is pointing out something totally right. I feel that now I understand more about the difference between left/right folding than I did before as a result of really trying to understand the point that Kasey is making.

To unsubscribe from this group and stop receiving emails from it, send an email to elm-discuss+unsubscribe@googlegroups.com.

[Janis Voigtländer]

Having the behavior you expect? So if you write List.foldl (++) "" ["a", "b", "c"], you expect to get "cba"?

Yes, if I looked at the type of List.foldl first (or still had it in mind). Which is exactly what my statement about "expected" was conditioned by. Not more, not less.

[Kasey Speakman]

Here is a minimal function for a fold which operates the standard way.

fold : (b -> a -> b) -> b -> List a -> b

fold f =

    List.foldl (flip f)

Example use:

fold (++) "" ["a", "b", "c"]

-- result: (("" ++ "a") ++ "b") ++ "c"

--      == "" ++ "a" ++ "b" ++ "c"

--      == "abc"

Additionally, here is a minimal function for a right fold where the call visually matches how it works.

foldBack : (a -> b -> b) -> List a -> b -> b

foldBack f =

    flip (List.foldr f)

Example use:

foldBack (::) ["a", "b", "c"] []

-- result: "a" :: ("b" :: ("c" :: []))

--      == "a" :: "b" :: "c" :: []

--      == ["a", "b", "c"]