6 ms·

I mean generally I tend to prefer operations that are commutative and associative, so it really doesn't matter which one is the accumulator. But I still really

by ummonk 8y ago

I mean generally I tend to prefer operations that are commutative and associative, so it really doesn't matter which one is the accumulator. But I still really like your naming, it seems to bridge the gap in making reduces (which are conceptually cleaner) understandable to people who are used to iterative code.

whatshisface 8y ago
Floating point sums are one example of a place where the only usable operator doesn't commute.
- BeetleB 8y ago
  Which floating point operator is not commutative? Addition is.
  - karmakaze 8y ago
    Adding smaller magnitude first gives a different result than adding larger magnitudes first due to mixing precisions.
    - BeetleB 8y ago
      If I read you right, you are saying that if you compute a+b, you'll get a different result than if you compute b+a, if a is tiny and b is huge. I believe this is incorrect. Feel free to show me a counterexample.
      - jonsen 8y ago
        a + b commutes all right, but some-start-value +a +b ... +x does not necessarily.
        JadeNB 8y ago
        As rhimenoceros points out, that is a failure of associativity, not commutativity.
      - rhymenoceros 8y ago
        Not quite a+b, but a+b+c reordered may give different results[1]. Example from Python: >>> 0.1+0.2+0.3 0.6000000000000001 >>> 0.2+0.3+0.1 0.6 It's an associativity problem and not a commutative one, however, that is relevant to the original point about folding floating point operations over lists. [1] https://www.quora.com/Is-floating-point-addition-commutative-and-associative https://www.quora.com/Is-floating-point-addition-commutative...
  - jonsen 8y ago
    (small number)+(small number)+ ... +(small number)+(much bigger number) may not give the same result as (much bigger number)+(small number)+(small number)+ ... +(small number)
    - BeetleB 8y ago
      You are confusing associativity with commutativity. The IEEE floating point standard guarantees commutativity for addition.
      - jonsen 8y ago
        I think you are confusing commutativity in general with commutativity of binary operations.
        BeetleB 8y ago
        We are now lost in a semantic discussion, as it is clear that all parties agree on the content, just not the terminology. In that spirit, I will disagree. In mathematics, commutativity is always about two operands. My textbook on floating point arithmetic[1] (probably the most famous one) states that addition and multiplication in floating point is commutative. They use examples similar to yours as an example of associativity being violated, and point out that commutativity is preserved. Putting FP aside: In mathematics, no one disputes that addition is commutative. Yet, they all agree that for infinite sums, if you rearrange the order of the terms, you can get different results. They don't say that addition is commutative only for finite sums. They say it is commutative for all addition, and that associativity is the property that fails for infinite sums. See the discussion here[2] for example: >The commutative property of addition is that a+b=b+a. Technically, it applies only to sums of two numbers! >Actually, commutivity does hold for infinite sums. Glossing over a few technicalities, commutivity says that you get the same answer whenever you interchange any two terms in a sum. Although I'll grant that when I look at some other answers in StackExchage, they do generalize to "repeated use of commutativity", and that if commutativity is applied a finite number of times, the sum is preserved, but not if applied an infinite number of times. The common refrain in both cases, though, is that commutativity applies only to two operands. [1] https://www.springer.com/us/book/9780817647056 https://www.springer.com/us/book/9780817647056 [2] https://math.stackexchange.com/questions/646665/why-does-commutativity-of-addition-fail-for-infinite-sums https://math.stackexchange.com/questions/646665/why-does-com...
  - Someone 8y ago
    Technically, addition is mostly commutative (a phrase I just made up) in IEEE 754. On the one hand, we have: NaN + 1 = NaN 1 + NaN = NaN but we also have: NaN ≠ NaN , so that’s an example where a + b ≠ b + a
    - BeetleB 8y ago
      Heh. You got me thinking on that one! I do know that with the floating point standard, NaN ≠ NaN returns True. But what does it mandate for NaN == NaN? Is this always false? If so, you're right. If not, I'd argue I'm still right, as that means that NaN + 1 == 1 + NaN would still be true.
skrebbel 8y ago
I find that few practical folds have that property. I mean, you're not going to actually implement "sum" - there's a library function for that. Your reduces are going to be domain specific, and then order often matters, and explicitly accumulating the result on the left (or right) hand side often has a performance impact (eg when building lists).

by ummonk 8y ago

whatshisface 8y ago

Floating point sums are one example of a place where the only usable operator doesn't commute.

BeetleB 8y ago
Which floating point operator is not commutative? Addition is.
- karmakaze 8y ago
  Adding smaller magnitude first gives a different result than adding larger magnitudes first due to mixing precisions.
  - BeetleB 8y ago
    If I read you right, you are saying that if you compute a+b, you'll get a different result than if you compute b+a, if a is tiny and b is huge. I believe this is incorrect. Feel free to show me a counterexample.
    - jonsen 8y ago
      a + b commutes all right, but some-start-value +a +b ... +x does not necessarily.
      - JadeNB 8y ago
        As rhimenoceros points out, that is a failure of associativity, not commutativity.
    - rhymenoceros 8y ago
      Not quite a+b, but a+b+c reordered may give different results[1]. Example from Python: >>> 0.1+0.2+0.3 0.6000000000000001 >>> 0.2+0.3+0.1 0.6 It's an associativity problem and not a commutative one, however, that is relevant to the original point about folding floating point operations over lists. [1] https://www.quora.com/Is-floating-point-addition-commutative-and-associative https://www.quora.com/Is-floating-point-addition-commutative...
- jonsen 8y ago
  (small number)+(small number)+ ... +(small number)+(much bigger number) may not give the same result as (much bigger number)+(small number)+(small number)+ ... +(small number)
  - BeetleB 8y ago
    You are confusing associativity with commutativity. The IEEE floating point standard guarantees commutativity for addition.
    - jonsen 8y ago
      I think you are confusing commutativity in general with commutativity of binary operations.
      - BeetleB 8y ago
        We are now lost in a semantic discussion, as it is clear that all parties agree on the content, just not the terminology. In that spirit, I will disagree. In mathematics, commutativity is always about two operands. My textbook on floating point arithmetic[1] (probably the most famous one) states that addition and multiplication in floating point is commutative. They use examples similar to yours as an example of associativity being violated, and point out that commutativity is preserved. Putting FP aside: In mathematics, no one disputes that addition is commutative. Yet, they all agree that for infinite sums, if you rearrange the order of the terms, you can get different results. They don't say that addition is commutative only for finite sums. They say it is commutative for all addition, and that associativity is the property that fails for infinite sums. See the discussion here[2] for example: >The commutative property of addition is that a+b=b+a. Technically, it applies only to sums of two numbers! >Actually, commutivity does hold for infinite sums. Glossing over a few technicalities, commutivity says that you get the same answer whenever you interchange any two terms in a sum. Although I'll grant that when I look at some other answers in StackExchage, they do generalize to "repeated use of commutativity", and that if commutativity is applied a finite number of times, the sum is preserved, but not if applied an infinite number of times. The common refrain in both cases, though, is that commutativity applies only to two operands. [1] https://www.springer.com/us/book/9780817647056 https://www.springer.com/us/book/9780817647056 [2] https://math.stackexchange.com/questions/646665/why-does-commutativity-of-addition-fail-for-infinite-sums https://math.stackexchange.com/questions/646665/why-does-com...
- Someone 8y ago
  Technically, addition is mostly commutative (a phrase I just made up) in IEEE 754. On the one hand, we have: NaN + 1 = NaN 1 + NaN = NaN but we also have: NaN ≠ NaN , so that’s an example where a + b ≠ b + a
  - BeetleB 8y ago
    Heh. You got me thinking on that one! I do know that with the floating point standard, NaN ≠ NaN returns True. But what does it mandate for NaN == NaN? Is this always false? If so, you're right. If not, I'd argue I'm still right, as that means that NaN + 1 == 1 + NaN would still be true.

skrebbel 8y ago

I find that few practical folds have that property. I mean, you're not going to actually implement "sum" - there's a library function for that. Your reduces are going to be domain specific, and then order often matters, and explicitly accumulating the result on the left (or right) hand side often has a performance impact (eg when building lists).