4 ms·

> Case in point: type classes, the Monoid type class, and Monoids as the mathematical concept; [...] when implemented by a compiler behaves exactly as expected

by a1369209993 4y ago

> Case in point: type classes, the Monoid type class, and Monoids as the mathematical concept; [...] when implemented by a compiler behaves exactly as expected when the program is executed. Not true in general. For some specific instances (such as fixed-size Int under addition or multiplication[0]), it works[1], but in the general case (eg Integer under add or mul, [Foo] under concat) `a <> b` can fail with out-of-memory if a and b are large enough. (This debateably violates closure of `<>` (you could say `undefined`/`error "out of memory"`/etc is a valid element), but indirectly breaks all the other Monoid laws like `(a<>b)<>c==a<>(b<>c)`, since the result is `undefined`(/etc), rather than `True`.) 0: Actually, I'm not sure it's true even then: does Haskell actually guarantee 2s-complement truncation on overflow? 1: Give or take "How many bits does Int truncate to?".

agentultra 4y ago
Isn't this why fixed, signed integer types don't have a Monoid instance? https://hackage.haskell.org/package/base-4.17.0.0/docs/Data-Int.html https://hackage.haskell.org/package/base-4.17.0.0/docs/Data-... For arbitrary sized `Integer` type, which is basically a libgmp arbitrary integer, we also don't have a Monoid.
- a1369209993 4y ago
  > Isn't this why fixed, signed integer types don't have a Monoid instance? No. Integers (signed or unsigned, fixed or arbitrary-precision) don't have Monoid instances since Haskell requires a single class instance per type, and it's ambigous which instance should be the "canonical" one. The types `Num a => Sum a` and `Num a => Product a` have Monoid instances, but it's not clear whether the "canonical" instance for a given integer type should have `(<>)` defined as `(+)` or `(*)`... or `min`, `max`, `and`, `or`, `xor`, `lcm`, `gcd`, or any of several dozen other monoidal operations. Conversely, `[a]` doesn't really have any resonable monoidal operation other then `concat`, and most of the existing Monoid instances (most conspicuously Sum and Product above) are even more nothing-else-is-reasonable, if only because of their names.
  - agentultra 4y ago
    Ah ok that makes sense, and if you choose to use `Sum Int` you'd be technically implementing the Monoid abstraction for that type. In practice because the `Int` type is a signed, fixed-size integer it would break the laws for all integers. In that case it would still be a useful abstraction but you would have to be aware that your `Int` will wrap around for large values which kind of makes `Int` a poor choice. `Integer` would be better but is still somewhat finite because computers.
    - a1369209993 4y ago
      > In practice because the `Int` type is a signed, fixed-size integer it would break the laws for all integers. No. `Sum Int` (unlike, pedantically, `Sum Integer` or `[a]`) is a valid (non-leaky-abstraction) monoid. It adds `Int`s, which is a monoidal operation that satisfies `(a<>b)<>c==a<>(b<>c)` for all (2^(3*MACHINE_BIT_WIDTH) distinct triplets (a,b,c) of) Ints, due to 2s-complement truncation on overflow. > your `Int` will wrap around for large values Yes, that's what `Int` means. > `Integer` will fail to terminate when adding sufficiently large values (in theory with a out of memory error, although in practice operations just get slower and slower until you abort them with ^C or a timeout), a property not shared by addition of `Int`.
- garethrowlands 4y ago
  The main reason Haskell does not define Monoid instances for numbers is that there are two equally valid instances: with 1 and * or with 0 and +. So, instead, there are two newtypes defined: * `Sum` whose `mempty` (identity) is `Sum 0` and `<>` (combining operator) is multiplication; and * `Product` whose `mempty` is `Product 1` and `<>` is addition You have to choose one explicitly. That is, you can't say `2 <> 3` and expect 6 (or is it 5?). Instead you have to say `Product 2 <> Product 3`
  - a1369209993 4y ago
    > * `Sum` whose [`<>`] is multiplication; and * `Product` whose [...] `<>` is addition ... Uhh?
    - nequo 4y ago
      Parent probably wanted to create two bullet points with the two asterisks.
      - a1369209993 4y ago
        I was actually questioning the "Sum is multiplication, Product is addition" part, although now that you mention it, the lack of a line break is also a (less significant) problem.

agentultra 4y ago

Isn't this why fixed, signed integer types don't have a Monoid instance? https://hackage.haskell.org/package/base-4.17.0.0/docs/Data-Int.html https://hackage.haskell.org/package/base-4.17.0.0/docs/Data-... For arbitrary sized `Integer` type, which is basically a libgmp arbitrary integer, we also don't have a Monoid.

a1369209993 4y ago
> Isn't this why fixed, signed integer types don't have a Monoid instance? No. Integers (signed or unsigned, fixed or arbitrary-precision) don't have Monoid instances since Haskell requires a single class instance per type, and it's ambigous which instance should be the "canonical" one. The types `Num a => Sum a` and `Num a => Product a` have Monoid instances, but it's not clear whether the "canonical" instance for a given integer type should have `(<>)` defined as `(+)` or `(*)`... or `min`, `max`, `and`, `or`, `xor`, `lcm`, `gcd`, or any of several dozen other monoidal operations. Conversely, `[a]` doesn't really have any resonable monoidal operation other then `concat`, and most of the existing Monoid instances (most conspicuously Sum and Product above) are even more nothing-else-is-reasonable, if only because of their names.
- agentultra 4y ago
  Ah ok that makes sense, and if you choose to use `Sum Int` you'd be technically implementing the Monoid abstraction for that type. In practice because the `Int` type is a signed, fixed-size integer it would break the laws for all integers. In that case it would still be a useful abstraction but you would have to be aware that your `Int` will wrap around for large values which kind of makes `Int` a poor choice. `Integer` would be better but is still somewhat finite because computers.
  - a1369209993 4y ago
    > In practice because the `Int` type is a signed, fixed-size integer it would break the laws for all integers. No. `Sum Int` (unlike, pedantically, `Sum Integer` or `[a]`) is a valid (non-leaky-abstraction) monoid. It adds `Int`s, which is a monoidal operation that satisfies `(a<>b)<>c==a<>(b<>c)` for all (2^(3*MACHINE_BIT_WIDTH) distinct triplets (a,b,c) of) Ints, due to 2s-complement truncation on overflow. > your `Int` will wrap around for large values Yes, that's what `Int` means. > `Integer` will fail to terminate when adding sufficiently large values (in theory with a out of memory error, although in practice operations just get slower and slower until you abort them with ^C or a timeout), a property not shared by addition of `Int`.
garethrowlands 4y ago
The main reason Haskell does not define Monoid instances for numbers is that there are two equally valid instances: with 1 and * or with 0 and +. So, instead, there are two newtypes defined: * `Sum` whose `mempty` (identity) is `Sum 0` and `<>` (combining operator) is multiplication; and * `Product` whose `mempty` is `Product 1` and `<>` is addition You have to choose one explicitly. That is, you can't say `2 <> 3` and expect 6 (or is it 5?). Instead you have to say `Product 2 <> Product 3`
- a1369209993 4y ago
  > * `Sum` whose [`<>`] is multiplication; and * `Product` whose [...] `<>` is addition ... Uhh?
  - nequo 4y ago
    Parent probably wanted to create two bullet points with the two asterisks.
    - a1369209993 4y ago
      I was actually questioning the "Sum is multiplication, Product is addition" part, although now that you mention it, the lack of a line break is also a (less significant) problem.