I read the associativity article. You should examine this wikipedia article on fold <https://en.wikipedia.org/wiki/Fold_(higher-order_function)>.
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. On Saturday, December 10, 2016 at 12:44:30 AM UTC-6, Janis Voigtländer wrote: > > 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 <[email protected] <javascript:> > >: > >> 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 <[email protected]> >>>> 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 <[email protected]> >>>>>>>> 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 < >>>>>>>>>> [email protected]> 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 < >>>>>>>>>>> [email protected]> 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 < >>>>>>>>>>>> [email protected]> 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 < >>>>>>>>>>>>> [email protected]> 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 < >>>>>>>>>>>>>> [email protected]> 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 [email protected]. >>>>>>>>>>>>>>> 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 [email protected]. >>>>>>>>>>>>>> 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 [email protected]. >>>>>>>>>>>>> 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 [email protected]. >>>>>>>>>>>> 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 [email protected]. >>>>>>>>>>> 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 [email protected]. >>>>>>>>> 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 [email protected]. >>>>> 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 [email protected] <javascript:>. >> 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 [email protected]. For more options, visit https://groups.google.com/d/optout.
