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). 2016-12-10 6:43 GMT+01:00 Kasey Speakman <kjspeak...@gmail.com>: > 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). > > On Friday, December 9, 2016 at 11:15:04 PM UTC-6, Kasey Speakman wrote: >> >> 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 >> <http://elm-lang.org/examples/hello-html>. >> >> 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. >> >> On Friday, December 9, 2016 at 4:17:50 PM UTC-6, Nick H wrote: >>> >>> 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. >>> >>> On Fri, Dec 9, 2016 at 7:03 AM, Kasey Speakman <kjspe...@gmail.com> >>> wrote: >>> >>>> 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. >>>> >>>> On Friday, December 9, 2016 at 8:44:25 AM UTC-6, Kasey Speakman wrote: >>>>> >>>>> 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 " >>>>> >>>>> On Friday, December 9, 2016 at 8:26:17 AM UTC-6, Kasey Speakman wrote: >>>>>> >>>>>> 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 " >>>>>> >>>>>> On Friday, December 9, 2016 at 1:05:56 AM UTC-6, Aaron VonderHaar >>>>>> wrote: >>>>>>> >>>>>>> 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 >>>>>>> >>>>>>> >>>>>>> On Thu, Dec 8, 2016 at 7:50 PM, Kasey Speakman <kjspe...@gmail.com> >>>>>>> wrote: >>>>>>> >>>>>>>> (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)) >>>>>>>> >>>>>>>> On Tuesday, July 16, 2013 at 6:13:01 AM UTC-5, Evan wrote: >>>>>>>>> >>>>>>>>> Gotcha, I definitely see the reasoning :) >>>>>>>>> >>>>>>>>> >>>>>>>>> On Tue, Jul 16, 2013 at 12:54 PM, Balazs Komuves < >>>>>>>>> bkom...@gmail.com> wrote: >>>>>>>>> >>>>>>>>>> >>>>>>>>>> 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 >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> On Tue, Jul 16, 2013 at 12:21 PM, Evan Czaplicki < >>>>>>>>>> eva...@gmail.com> wrote: >>>>>>>>>> >>>>>>>>>>> I think this might be a religious debate on some level. My first >>>>>>>>>>> functional languages were Scheme >>>>>>>>>>> <http://docs.racket-lang.org/reference/pairs.html#(def._((lib._racket/private/list..rkt)._foldl))> >>>>>>>>>>> and Standard ML <http://www.standardml.org/Basis/list.html>. >>>>>>>>>>> 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 >>>>>>>>>>> <http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html> 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. >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> On Tue, Jul 16, 2013 at 10:40 AM, Balazs Komuves < >>>>>>>>>>> bkom...@gmail.com> wrote: >>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> 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 >>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> On Wed, Jul 10, 2013 at 4:38 PM, Evan Czaplicki < >>>>>>>>>>>> eva...@gmail.com> wrote: >>>>>>>>>>>> >>>>>>>>>>>>> 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 >>>>>>>>>>>>> <http://www.standardml.org/Basis/list.html>, and it is my >>>>>>>>>>>>> favorite by far. >>>>>>>>>>>>> >>>>>>>>>>>>> >>>>>>>>>>>>> On Wed, Jul 10, 2013 at 4:12 PM, Tim hobbs <tim.t...@gmail.com >>>>>>>>>>>>> > wrote: >>>>>>>>>>>>> >>>>>>>>>>>>>> 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 >>>>>>>>>>>>>> >>>>>>>>>>>>>> >>>>>>>>>>>>>> On Wednesday, July 10, 2013 4:03:23 PM UTC+2, Zsombor Nagy >>>>>>>>>>>>>> wrote: >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> 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 >>>>>>>>>>>>>> >>>>>>>>>>>>>> -- >>>>>>>>>>>>>> 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/grou >>>>>>>>>>>>>> ps/opt_out. >>>>>>>>>>>>>> >>>>>>>>>>>>>> >>>>>>>>>>>>>> >>>>>>>>>>>>> >>>>>>>>>>>>> -- >>>>>>>>>>>>> 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/grou >>>>>>>>>>>>> ps/opt_out. >>>>>>>>>>>>> >>>>>>>>>>>>> >>>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> -- >>>>>>>>>>>> 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/grou >>>>>>>>>>>> ps/opt_out. >>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> -- >>>>>>>>>>> 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 >>>>>>>>>>> . >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>> >>>>>>>>>> -- >>>>>>>>>> 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. >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> >>>>>>>>> >>>>>>>>> -- >>>>>>>> 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/d/optout. >>>>>>>> >>>>>>> >>>>>>> -- >>>> 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/d/optout. >>>> >>> >>> -- > 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+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- 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+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
