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]. For more options, visit https://groups.google.com/d/optout.
