Re: Break `abs` into two aspects

newer
Fwd: add instance PrintfArg Ratio

older
I'm concerned about the...

Andrew Lelechenko

28 Jan 2020 28 Jan '20

12:10 p.m.

On Tue, 28 Jan 2020, Dannyu NDos wrote:

...

`abs` represents a norm, but its type is wrong

There are two useful meanings of `abs`, which coincide for integers. One is a norm. Another one is to define `abs` as a mapping from a ring R to a factor ring R / U(R), where U(R) is a ring of units, and `signum` as a mapping from R to U(R) such that `abs a * signum a = a`.

...

This enables us to implement rings (Num) and fields (Fractional) without concerning about norms. For example, Gaussian integers.

For Gaussian integers I find convenient to define `signum z` with a codomain {1, i, -1, -I} (basically, to which quadrant does z belong?) and `abs z` with the first quadrant as a codomain. Best regards, Andrew

Show replies by date

Carter Schonwald

28 Jan 28 Jan

2:59 p.m.

New subject: Break `abs` into two aspects

Well said Andrew! There’s a second twist : last I checked our abs for complex numbers isn’t the Euclidean norm or any Lp norm .. We could define the Pth power of the lpNorm for any complex a I think. Though that’s a weaker operation. On Tue, Jan 28, 2020 at 7:11 AM Andrew Lelechenko < andrew.lelechenko@gmail.com> wrote:

...

On Tue, 28 Jan 2020, Dannyu NDos wrote:

...
`abs` represents a norm, but its type is wrong

There are two useful meanings of `abs`, which coincide for integers. One is a norm. Another one is to define `abs` as a mapping from a ring R to a factor ring R / U(R), where U(R) is a ring of units, and `signum` as a mapping from R to U(R) such that `abs a * signum a = a`.

...
This enables us to implement rings (Num) and fields (Fractional) without concerning about norms. For example, Gaussian integers.

For Gaussian integers I find convenient to define `signum z` with a codomain {1, i, -1, -I} (basically, to which quadrant does z belong?) and `abs z` with the first quadrant as a codomain.

Best regards, Andrew

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Carter Schonwald

4:10 p.m.

New subject: Break `abs` into two aspects

One long running pain point is that the abs definition we have for complex numbers is terrible. Does anyone use it ? On Tue, Jan 28, 2020 at 9:59 AM Carter Schonwald wrote:

...

Well said Andrew!

There’s a second twist : last I checked our abs for complex numbers isn’t the Euclidean norm or any Lp norm ..

We could define the Pth power of the lpNorm for any complex a I think. Though that’s a weaker operation.

On Tue, Jan 28, 2020 at 7:11 AM Andrew Lelechenko < andrew.lelechenko@gmail.com> wrote:

...
On Tue, 28 Jan 2020, Dannyu NDos wrote:

...
`abs` represents a norm, but its type is wrong

There are two useful meanings of `abs`, which coincide for integers. One is a norm. Another one is to define `abs` as a mapping from a ring R to a factor ring R / U(R), where U(R) is a ring of units, and `signum` as a mapping from R to U(R) such that `abs a * signum a = a`.

...
This enables us to implement rings (Num) and fields (Fractional) without concerning about norms. For example, Gaussian integers.

For Gaussian integers I find convenient to define `signum z` with a codomain {1, i, -1, -I} (basically, to which quadrant does z belong?) and `abs z` with the first quadrant as a codomain.

Best regards, Andrew

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Andrew Lelechenko

31 Jan 31 Jan

8:38 p.m.

New subject: Break `abs` into two aspects

On Tue, 28 Jan 2020, Dannyu NDos wrote:

...

Second, I suggest to move `abs` and `signum` from `Num` to `Floating`

I can fully relate your frustration with `abs` and `signum` (and numeric type classes in Haskell altogether). But IMO breaking both in `Num` and in `Floating` at once is not a promising way to make things proper. I would rather follow the beaten track of Applicative Monad and Semigroup Monoid proposals and - as a first step - introduce a superclass (probably, borrowing the design from `semirings` package): class Semiring a where zero :: a plus :: a -> a -> a one :: a times :: a -> a -> a fromNatural :: Natural -> a class Semiring a => Num a where ... Tangible benefits in `base` include: a) instance Semiring Bool, b) a total instance Semiring Natural (in contrast to a partial instance Num Natural), c) instance Num a => Semiring (Complex a) (in contrast to instance RealFloat a => Num (Complex a)), d) newtypes Sum and Product would require only Semiring constraint instead of Num. Best regards, Andrew

Carter Schonwald

9:36 p.m.

New subject: Break `abs` into two aspects

that actually sounds pretty sane. I think! On Fri, Jan 31, 2020 at 3:38 PM Andrew Lelechenko < andrew.lelechenko@gmail.com> wrote:

...

On Tue, 28 Jan 2020, Dannyu NDos wrote:

...
Second, I suggest to move `abs` and `signum` from `Num` to `Floating`

I can fully relate your frustration with `abs` and `signum` (and numeric type classes in Haskell altogether). But IMO breaking both in `Num` and in `Floating` at once is not a promising way to make things proper.

I would rather follow the beaten track of Applicative Monad and Semigroup Monoid proposals and - as a first step - introduce a superclass (probably, borrowing the design from `semirings` package):

class Semiring a where zero :: a plus :: a -> a -> a one :: a times :: a -> a -> a fromNatural :: Natural -> a class Semiring a => Num a where ...

Tangible benefits in `base` include: a) instance Semiring Bool, b) a total instance Semiring Natural (in contrast to a partial instance Num Natural), c) instance Num a => Semiring (Complex a) (in contrast to instance RealFloat a => Num (Complex a)), d) newtypes Sum and Product would require only Semiring constraint instead of Num.

Best regards, Andrew

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Carter Schonwald

3 Feb 3 Feb

9:34 p.m.

New subject: Break `abs` into two aspects

Andrew: could you explain the algebra notation you were using for short hand? I think I followed, but for people the libraries list might be their first exposure to advanced / graduate abstract algebra (which winds up being simpler than most folks expect ;) ) On Fri, Jan 31, 2020 at 4:36 PM Carter Schonwald wrote:

...

that actually sounds pretty sane. I think!

On Fri, Jan 31, 2020 at 3:38 PM Andrew Lelechenko < andrew.lelechenko@gmail.com> wrote:

...
On Tue, 28 Jan 2020, Dannyu NDos wrote:

...
Second, I suggest to move `abs` and `signum` from `Num` to `Floating`

I can fully relate your frustration with `abs` and `signum` (and numeric type classes in Haskell altogether). But IMO breaking both in `Num` and in `Floating` at once is not a promising way to make things proper.

I would rather follow the beaten track of Applicative Monad and Semigroup Monoid proposals and - as a first step - introduce a superclass (probably, borrowing the design from `semirings` package):

class Semiring a where zero :: a plus :: a -> a -> a one :: a times :: a -> a -> a fromNatural :: Natural -> a class Semiring a => Num a where ...

Tangible benefits in `base` include: a) instance Semiring Bool, b) a total instance Semiring Natural (in contrast to a partial instance Num Natural), c) instance Num a => Semiring (Complex a) (in contrast to instance RealFloat a => Num (Complex a)), d) newtypes Sum and Product would require only Semiring constraint instead of Num.

Best regards, Andrew

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Andreas Abel

4 Feb 4 Feb

8:21 a.m.

New subject: Break `abs` into two aspects

...

class Semiring a where zero :: a plus :: a -> a -> a one :: a times :: a -> a -> a fromNatural :: Natural -> a

I think `fromNatural` should not be part of the `Semiring` class, but we could have an extension (NaturalSemiring) that adds this method. In the Agda code base, we have, for lack of a standard, rolled our own semiring class, https://github.com/agda/agda/blob/master/src/full/Agda/Utils/SemiRing.hs and we use it for several finite semirings, e.g., https://github.com/agda/agda/blob/64c0c2e813a84f91b3accd7c56efaa53712bc3f5/s... Cheers, Andreas On 2020-02-03 22:34, Carter Schonwald wrote:

...

Andrew: could you explain the algebra notation you were using for short hand? I think I followed, but for people the libraries list might be their first exposure to advanced / graduate abstract algebra (which winds up being simpler than most folks expect ;) )

On Fri, Jan 31, 2020 at 4:36 PM Carter Schonwald mailto:carter.schonwald@gmail.com> wrote:

that actually sounds pretty sane. I think!

On Fri, Jan 31, 2020 at 3:38 PM Andrew Lelechenko mailto:andrew.lelechenko@gmail.com> wrote:

On Tue, 28 Jan 2020, Dannyu NDos wrote:

> Second, I suggest to move `abs` and `signum` from `Num` to `Floating`

I can fully relate your frustration with `abs` and `signum` (and numeric type classes in Haskell altogether). But IMO breaking both in `Num` and in `Floating` at once is not a promising way to make things proper.

I would rather follow the beaten track of Applicative Monad and Semigroup Monoid proposals and - as a first step - introduce a superclass (probably, borrowing the design from `semirings` package):

class Semiring a where zero :: a plus :: a -> a -> a one :: a times :: a -> a -> a fromNatural :: Natural -> a class Semiring a => Num a where ...

Tangible benefits in `base` include: a) instance Semiring Bool, b) a total instance Semiring Natural (in contrast to a partial instance Num Natural), c) instance Num a => Semiring (Complex a) (in contrast to instance RealFloat a => Num (Complex a)), d) newtypes Sum and Product would require only Semiring constraint instead of Num.

Best regards, Andrew

_______________________________________________ Libraries mailing list Libraries@haskell.org mailto:Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Zemyla

12:42 p.m.

New subject: Break `abs` into two aspects

There is a homomorphism from the Naturals to any Semiring, which obeys: fromNatural 0 = zero fromNatural 1 = one fromNatural (m + n) = fromNatural m `plus` fromNatural n fromNatural (m * n) = fromNatural m `times` fromNatural n The simplest implementation is this, but it's nowhere near the most efficient: fromNatural :: Semiring a => Natural -> a fromNatural 0 = zero fromNatural n = one `plus` fromNatural (n - 1) One which takes O(log n) time instead of O(n) would go like this: fromNatural :: Semiring a => Natural -> a fromNatural = go 0 zero one go i s m n | i `seq` s `seq` m `seq` n `seq` False = undefined go _ s _ 0 = s go i s m n | testBit n i = go (i + 1) (plus s m) (plus m m) (clearBit n i) | otherwise = go (i + 1) s (plus m m) n On Tue, Feb 4, 2020, 02:21 Andreas Abel wrote:

...

...
class Semiring a where zero :: a plus :: a -> a -> a one :: a times :: a -> a -> a fromNatural :: Natural -> a

I think `fromNatural` should not be part of the `Semiring` class, but we could have an extension (NaturalSemiring) that adds this method.

In the Agda code base, we have, for lack of a standard, rolled our own semiring class,

https://github.com/agda/agda/blob/master/src/full/Agda/Utils/SemiRing.hs

and we use it for several finite semirings, e.g.,

https://github.com/agda/agda/blob/64c0c2e813a84f91b3accd7c56efaa53712bc3f5/s...

Cheers, Andreas

On 2020-02-03 22:34, Carter Schonwald wrote:

...
Andrew: could you explain the algebra notation you were using for short hand? I think I followed, but for people the libraries list might be their first exposure to advanced / graduate abstract algebra (which winds up being simpler than most folks expect ;) )

On Fri, Jan 31, 2020 at 4:36 PM Carter Schonwald mailto:carter.schonwald@gmail.com> wrote:

that actually sounds pretty sane. I think!

On Fri, Jan 31, 2020 at 3:38 PM Andrew Lelechenko mailto:andrew.lelechenko@gmail.com> wrote:

On Tue, 28 Jan 2020, Dannyu NDos wrote:

> Second, I suggest to move `abs` and `signum` from `Num` to `Floating`

I can fully relate your frustration with `abs` and `signum` (and numeric type classes in Haskell altogether). But IMO breaking both in `Num` and in `Floating` at once is not a promising way to make things proper.

I would rather follow the beaten track of Applicative Monad and Semigroup Monoid proposals and - as a first step - introduce a superclass (probably, borrowing the design from `semirings` package):

class Semiring a where zero :: a plus :: a -> a -> a one :: a times :: a -> a -> a fromNatural :: Natural -> a class Semiring a => Num a where ...

Tangible benefits in `base` include: a) instance Semiring Bool, b) a total instance Semiring Natural (in contrast to a partial instance Num Natural), c) instance Num a => Semiring (Complex a) (in contrast to instance RealFloat a => Num (Complex a)), d) newtypes Sum and Product would require only Semiring constraint instead of Num.

Best regards, Andrew

_______________________________________________ Libraries mailing list Libraries@haskell.org mailto:Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Andreas Abel

3:20 p.m.

New subject: Break `abs` into two aspects

...

There is a homomorphism from the Naturals to any Semiring

Sure, but there are many finite semirings where I would not care about such a homomorphism, thus, why force me to define it?

...

fromNatural 0 = zero fromNatural 1 = one fromNatural (m + n) = fromNatural m `plus` fromNatural n fromNatural (m * n) = fromNatural m `times` fromNatural n

This might not be surjective, and also not very interesting. For instance consider the semiring Set Bool zero = Set.empty one = Set.singleton True plus = Set.union times s t = { x == y | x <- s, y <- t } This semiring models variances (covariant = {True}, contravariant = {False}, constant = {}, dontknow = {True,False}). times is for function composition and plus combination of information. The fromNatural targets only the zero/one-fragment since plus is idempotent. I conjecture there is not a single surjective semiring-hom from Nat to Set Bool. Thus, a function fromNatural is totally uninteresting for the general case of semirings. On 2020-02-04 13:42, Zemyla wrote:

...

There is a homomorphism from the Naturals to any Semiring, which obeys:

fromNatural 0 = zero fromNatural 1 = one fromNatural (m + n) = fromNatural m `plus` fromNatural n fromNatural (m * n) = fromNatural m `times` fromNatural n

The simplest implementation is this, but it's nowhere near the most efficient:

fromNatural :: Semiring a => Natural -> a fromNatural 0 = zero fromNatural n = one `plus` fromNatural (n - 1)

One which takes O(log n) time instead of O(n) would go like this:

fromNatural :: Semiring a => Natural -> a fromNatural = go 0 zero one go i s m n | i `seq` s `seq` m `seq` n `seq` False = undefined go _ s _ 0 = s go i s m n | testBit n i = go (i + 1) (plus s m) (plus m m) (clearBit n i) | otherwise = go (i + 1) s (plus m m) n

On Tue, Feb 4, 2020, 02:21 Andreas Abel mailto:andreas.abel@ifi.lmu.de> wrote:

> class Semiring a where > zero :: a > plus :: a -> a -> a > one :: a > times :: a -> a -> a > fromNatural :: Natural -> a

I think `fromNatural` should not be part of the `Semiring` class, but we could have an extension (NaturalSemiring) that adds this method.

In the Agda code base, we have, for lack of a standard, rolled our own semiring class,

https://github.com/agda/agda/blob/master/src/full/Agda/Utils/SemiRing.hs

and we use it for several finite semirings, e.g.,

https://github.com/agda/agda/blob/64c0c2e813a84f91b3accd7c56efaa53712bc3f5/s...

Cheers, Andreas

On 2020-02-03 22:34, Carter Schonwald wrote: > Andrew: could you explain the algebra notation you were using for short > hand? I think I followed, but for people the libraries list might be > their first exposure to advanced / graduate abstract algebra (which > winds up being simpler than most folks expect ;) ) > > On Fri, Jan 31, 2020 at 4:36 PM Carter Schonwald > mailto:carter.schonwald@gmail.com mailto:carter.schonwald@gmail.com>> wrote: > > that actually sounds pretty sane. I think! > > On Fri, Jan 31, 2020 at 3:38 PM Andrew Lelechenko > mailto:andrew.lelechenko@gmail.com mailto:andrew.lelechenko@gmail.com>> > wrote: > > On Tue, 28 Jan 2020, Dannyu NDos wrote: > > > Second, I suggest to move `abs` and `signum` from `Num` to > `Floating` > > I can fully relate your frustration with `abs` and `signum` (and > numeric type classes in Haskell altogether). But IMO breaking > both in `Num` and in `Floating` at once is not a promising way > to make things proper. > > I would rather follow the beaten track of Applicative Monad and > Semigroup Monoid proposals and - as a first step - introduce a > superclass (probably, borrowing the design from `semirings` > package): > > class Semiring a where > zero :: a > plus :: a -> a -> a > one :: a > times :: a -> a -> a > fromNatural :: Natural -> a > class Semiring a => Num a where ... > > Tangible benefits in `base` include: > a) instance Semiring Bool, > b) a total instance Semiring Natural (in contrast to a partial > instance Num Natural), > c) instance Num a => Semiring (Complex a) (in contrast to > instance RealFloat a => Num (Complex a)), > d) newtypes Sum and Product would require only Semiring > constraint instead of Num. > > Best regards, > Andrew > > > _______________________________________________ > Libraries mailing list > Libraries@haskell.org mailto:Libraries@haskell.org mailto:Libraries@haskell.org> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > > > _______________________________________________ > Libraries mailing list > Libraries@haskell.org mailto:Libraries@haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > _______________________________________________ Libraries mailing list Libraries@haskell.org mailto:Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Zemyla

4:32 p.m.

New subject: Break `abs` into two aspects

It really doesn't matter if it's not "interesting" or not surjective for some Semirings. It should be included, because: (a) Even for semirings where it is "interesting", it's not surjective (for instance, Rational or Double) (b) It's a method with a default definition, so you don't have to expend any mental effort on it (c) A lot of instances have uninteresting methods: for instance, (*>) and (<*) for Applicative ((->) e) are const id and const respectively. Haskell adds methods to classes when they're always possible and sometimes useful/interesting/faster, rather than when they're always interesting. (d) It's useful for Semiring-generic methods and instances. (e) It can achieve an asymptotic speedup on some instances. Like, if you have Semiring a => Semiring (f a) for some type f, then you can have fromNatural n = pure (fromNatural n) instead of doing the whole O(log n) song and dance with the default definition. Also, your example admits a simple definition: fromNatural n = if n == 0 then S.empty else S.singleton True (f) "zero" and "one" can be defined in terms of fromNatural, for programmers who only need to define that: zero = fromNatural 0 one = fromNatural 1 This leads to the MINIMAL pragma on Semiring being {-# MINIMAL plus, times, (zero, one | fromNatural) #-} (g) If it's not included in the class, but in some subclass (NaturalSemiring, you proposed), but it's possible from the class, then people will just define and use the O(log n) version instead of requiring the subclass, leading to wasted effort and duplicated code. On Tue, Feb 4, 2020, 09:20 Andreas Abel wrote:

...

...
There is a homomorphism from the Naturals to any Semiring

Sure, but there are many finite semirings where I would not care about such a homomorphism, thus, why force me to define it?

...
fromNatural 0 = zero fromNatural 1 = one fromNatural (m + n) = fromNatural m `plus` fromNatural n fromNatural (m * n) = fromNatural m `times` fromNatural n

This might not be surjective, and also not very interesting. For instance consider the semiring

Set Bool zero = Set.empty one = Set.singleton True plus = Set.union times s t = { x == y | x <- s, y <- t }

This semiring models variances (covariant = {True}, contravariant = {False}, constant = {}, dontknow = {True,False}). times is for function composition and plus combination of information.

The fromNatural targets only the zero/one-fragment since plus is idempotent. I conjecture there is not a single surjective semiring-hom from Nat to Set Bool. Thus, a function fromNatural is totally uninteresting for the general case of semirings.

On 2020-02-04 13:42, Zemyla wrote:

...
There is a homomorphism from the Naturals to any Semiring, which obeys:

fromNatural 0 = zero fromNatural 1 = one fromNatural (m + n) = fromNatural m `plus` fromNatural n fromNatural (m * n) = fromNatural m `times` fromNatural n

The simplest implementation is this, but it's nowhere near the most efficient:

fromNatural :: Semiring a => Natural -> a fromNatural 0 = zero fromNatural n = one `plus` fromNatural (n - 1)

One which takes O(log n) time instead of O(n) would go like this:

fromNatural :: Semiring a => Natural -> a fromNatural = go 0 zero one go i s m n | i `seq` s `seq` m `seq` n `seq` False = undefined go _ s _ 0 = s go i s m n | testBit n i = go (i + 1) (plus s m) (plus m m) (clearBit n i) | otherwise = go (i + 1) s (plus m m) n

On Tue, Feb 4, 2020, 02:21 Andreas Abel mailto:andreas.abel@ifi.lmu.de> wrote:

> class Semiring a where > zero :: a > plus :: a -> a -> a > one :: a > times :: a -> a -> a > fromNatural :: Natural -> a

I think `fromNatural` should not be part of the `Semiring` class, but we could have an extension (NaturalSemiring) that adds this method.

In the Agda code base, we have, for lack of a standard, rolled our own semiring class,

https://github.com/agda/agda/blob/master/src/full/Agda/Utils/SemiRing.hs

...
and we use it for several finite semirings, e.g.,

https://github.com/agda/agda/blob/64c0c2e813a84f91b3accd7c56efaa53712bc3f5/s...

...
Cheers, Andreas

On 2020-02-03 22:34, Carter Schonwald wrote: > Andrew: could you explain the algebra notation you were using for short > hand? I think I followed, but for people the libraries list might be > their first exposure to advanced / graduate abstract algebra

(which

...
> winds up being simpler than most folks expect ;) ) > > On Fri, Jan 31, 2020 at 4:36 PM Carter Schonwald > mailto:carter.schonwald@gmail.com mailto:carter.schonwald@gmail.com>> wrote: > > that actually sounds pretty sane. I think! > > On Fri, Jan 31, 2020 at 3:38 PM Andrew Lelechenko > mailto:andrew.lelechenko@gmail.com mailto:andrew.lelechenko@gmail.com>> > wrote: > > On Tue, 28 Jan 2020, Dannyu NDos wrote: > > > Second, I suggest to move `abs` and `signum` from

`Num` to

...
> `Floating` > > I can fully relate your frustration with `abs` and `signum` (and > numeric type classes in Haskell altogether). But IMO

breaking

...
> both in `Num` and in `Floating` at once is not a promising way > to make things proper. > > I would rather follow the beaten track of Applicative Monad and > Semigroup Monoid proposals and - as a first step - introduce a > superclass (probably, borrowing the design from

`semirings`

...
> package): > > class Semiring a where > zero :: a > plus :: a -> a -> a > one :: a > times :: a -> a -> a > fromNatural :: Natural -> a > class Semiring a => Num a where ... > > Tangible benefits in `base` include: > a) instance Semiring Bool, > b) a total instance Semiring Natural (in contrast to a partial > instance Num Natural), > c) instance Num a => Semiring (Complex a) (in contrast to > instance RealFloat a => Num (Complex a)), > d) newtypes Sum and Product would require only Semiring > constraint instead of Num. > > Best regards, > Andrew > > > _______________________________________________ > Libraries mailing list > Libraries@haskell.org mailto:Libraries@haskell.org mailto:Libraries@haskell.org> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > > > _______________________________________________ > Libraries mailing list > Libraries@haskell.org mailto:Libraries@haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > _______________________________________________ Libraries mailing list Libraries@haskell.org mailto:Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Carter Schonwald

5:09 p.m.

New subject: Break `abs` into two aspects

well said! On Tue, Feb 4, 2020 at 11:32 AM Zemyla wrote:

...

It really doesn't matter if it's not "interesting" or not surjective for some Semirings. It should be included, because:

(a) Even for semirings where it is "interesting", it's not surjective (for instance, Rational or Double) (b) It's a method with a default definition, so you don't have to expend any mental effort on it (c) A lot of instances have uninteresting methods: for instance, (*>) and (<*) for Applicative ((->) e) are const id and const respectively. Haskell adds methods to classes when they're always possible and sometimes useful/interesting/faster, rather than when they're always interesting. (d) It's useful for Semiring-generic methods and instances. (e) It can achieve an asymptotic speedup on some instances. Like, if you have Semiring a => Semiring (f a) for some type f, then you can have fromNatural n = pure (fromNatural n) instead of doing the whole O(log n) song and dance with the default definition. Also, your example admits a simple definition: fromNatural n = if n == 0 then S.empty else S.singleton True (f) "zero" and "one" can be defined in terms of fromNatural, for programmers who only need to define that: zero = fromNatural 0 one = fromNatural 1 This leads to the MINIMAL pragma on Semiring being {-# MINIMAL plus, times, (zero, one | fromNatural) #-} (g) If it's not included in the class, but in some subclass (NaturalSemiring, you proposed), but it's possible from the class, then people will just define and use the O(log n) version instead of requiring the subclass, leading to wasted effort and duplicated code.

On Tue, Feb 4, 2020, 09:20 Andreas Abel wrote:

...
...
There is a homomorphism from the Naturals to any Semiring

Sure, but there are many finite semirings where I would not care about such a homomorphism, thus, why force me to define it?

...
fromNatural 0 = zero fromNatural 1 = one fromNatural (m + n) = fromNatural m `plus` fromNatural n fromNatural (m * n) = fromNatural m `times` fromNatural n

This might not be surjective, and also not very interesting. For instance consider the semiring

Set Bool zero = Set.empty one = Set.singleton True plus = Set.union times s t = { x == y | x <- s, y <- t }

This semiring models variances (covariant = {True}, contravariant = {False}, constant = {}, dontknow = {True,False}). times is for function composition and plus combination of information.

The fromNatural targets only the zero/one-fragment since plus is idempotent. I conjecture there is not a single surjective semiring-hom from Nat to Set Bool. Thus, a function fromNatural is totally uninteresting for the general case of semirings.

On 2020-02-04 13:42, Zemyla wrote:

...
There is a homomorphism from the Naturals to any Semiring, which obeys:

fromNatural 0 = zero fromNatural 1 = one fromNatural (m + n) = fromNatural m `plus` fromNatural n fromNatural (m * n) = fromNatural m `times` fromNatural n

The simplest implementation is this, but it's nowhere near the most efficient:

fromNatural :: Semiring a => Natural -> a fromNatural 0 = zero fromNatural n = one `plus` fromNatural (n - 1)

One which takes O(log n) time instead of O(n) would go like this:

fromNatural :: Semiring a => Natural -> a fromNatural = go 0 zero one go i s m n | i `seq` s `seq` m `seq` n `seq` False = undefined go _ s _ 0 = s go i s m n | testBit n i = go (i + 1) (plus s m) (plus m m) (clearBit n i) | otherwise = go (i + 1) s (plus m m) n

On Tue, Feb 4, 2020, 02:21 Andreas Abel mailto:andreas.abel@ifi.lmu.de> wrote:

> class Semiring a where > zero :: a > plus :: a -> a -> a > one :: a > times :: a -> a -> a > fromNatural :: Natural -> a

I think `fromNatural` should not be part of the `Semiring` class, but we could have an extension (NaturalSemiring) that adds this method.

In the Agda code base, we have, for lack of a standard, rolled our own semiring class,

https://github.com/agda/agda/blob/master/src/full/Agda/Utils/SemiRing.hs

...
and we use it for several finite semirings, e.g.,

https://github.com/agda/agda/blob/64c0c2e813a84f91b3accd7c56efaa53712bc3f5/s...

...
Cheers, Andreas

On 2020-02-03 22:34, Carter Schonwald wrote: > Andrew: could you explain the algebra notation you were using for short > hand? I think I followed, but for people the libraries list might be > their first exposure to advanced / graduate abstract algebra

(which

...
> winds up being simpler than most folks expect ;) ) > > On Fri, Jan 31, 2020 at 4:36 PM Carter Schonwald > mailto:carter.schonwald@gmail.com mailto:carter.schonwald@gmail.com>> wrote: > > that actually sounds pretty sane. I think! > > On Fri, Jan 31, 2020 at 3:38 PM Andrew Lelechenko > mailto:andrew.lelechenko@gmail.com mailto:andrew.lelechenko@gmail.com>> > wrote: > > On Tue, 28 Jan 2020, Dannyu NDos wrote: > > > Second, I suggest to move `abs` and `signum` from

`Num` to

...
> `Floating` > > I can fully relate your frustration with `abs` and `signum` (and > numeric type classes in Haskell altogether). But IMO

breaking

...
> both in `Num` and in `Floating` at once is not a promising way > to make things proper. > > I would rather follow the beaten track of Applicative Monad and > Semigroup Monoid proposals and - as a first step - introduce a > superclass (probably, borrowing the design from

`semirings`

...
> package): > > class Semiring a where > zero :: a > plus :: a -> a -> a > one :: a > times :: a -> a -> a > fromNatural :: Natural -> a > class Semiring a => Num a where ... > > Tangible benefits in `base` include: > a) instance Semiring Bool, > b) a total instance Semiring Natural (in contrast to a partial > instance Num Natural), > c) instance Num a => Semiring (Complex a) (in contrast to > instance RealFloat a => Num (Complex a)), > d) newtypes Sum and Product would require only Semiring > constraint instead of Num. > > Best regards, > Andrew > > > _______________________________________________ > Libraries mailing list > Libraries@haskell.org mailto:Libraries@haskell.org mailto:Libraries@haskell.org> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > > > _______________________________________________ > Libraries mailing list > Libraries@haskell.org mailto:Libraries@haskell.org > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > _______________________________________________ Libraries mailing list Libraries@haskell.org mailto:Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Andreas Abel

5 Feb 5 Feb

6:34 p.m.

New subject: Break `abs` into two aspects

Well, I see your arguments, but cannot help the feeling that you are reasoning from a specific instance family of semirings, namely numerical ones (N, Z, Q, ...). For idempotent semirings (e.g. the example I gave), repetitively adding one gets you nowhere. (Cf. also lattices, many of which are semirings.) I'd be convinced if Natural was something like the free semiring, but this is certainly not the case. Semirings are really diverse, I don't think the Semiring class should be hijacked for a particular flavor of semirings. We do not have any such pretext for Semigroup or Monoid either. Enjoy the diversity at https://en.wikipedia.org/wiki/Semiring On 2020-02-04 17:32, Zemyla wrote:

...

It really doesn't matter if it's not "interesting" or not surjective for some Semirings. It should be included, because:

(a) Even for semirings where it is "interesting", it's not surjective (for instance, Rational or Double) (b) It's a method with a default definition, so you don't have to expend any mental effort on it (c) A lot of instances have uninteresting methods: for instance, (*>) and (<*) for Applicative ((->) e) are const id and const respectively. Haskell adds methods to classes when they're always possible and sometimes useful/interesting/faster, rather than when they're always interesting. (d) It's useful for Semiring-generic methods and instances. (e) It can achieve an asymptotic speedup on some instances. Like, if you have Semiring a => Semiring (f a) for some type f, then you can have fromNatural n = pure (fromNatural n) instead of doing the whole O(log n) song and dance with the default definition. Also, your example admits a simple definition: fromNatural n = if n == 0 then S.empty else S.singleton True (f) "zero" and "one" can be defined in terms of fromNatural, for programmers who only need to define that: zero = fromNatural 0 one = fromNatural 1 This leads to the MINIMAL pragma on Semiring being {-# MINIMAL plus, times, (zero, one | fromNatural) #-} (g) If it's not included in the class, but in some subclass (NaturalSemiring, you proposed), but it's possible from the class, then people will just define and use the O(log n) version instead of requiring the subclass, leading to wasted effort and duplicated code.

On Tue, Feb 4, 2020, 09:20 Andreas Abel mailto:andreas.abel@ifi.lmu.de> wrote:

> There is a homomorphism from the Naturals to any Semiring

Sure, but there are many finite semirings where I would not care about such a homomorphism, thus, why force me to define it?

> fromNatural 0 = zero > fromNatural 1 = one > fromNatural (m + n) = fromNatural m `plus` fromNatural n > fromNatural (m * n) = fromNatural m `times` fromNatural n

This might not be surjective, and also not very interesting. For instance consider the semiring

Set Bool zero = Set.empty one = Set.singleton True plus = Set.union times s t = { x == y | x <- s, y <- t }

This semiring models variances (covariant = {True}, contravariant = {False}, constant = {}, dontknow = {True,False}). times is for function composition and plus combination of information.

The fromNatural targets only the zero/one-fragment since plus is idempotent. I conjecture there is not a single surjective semiring-hom from Nat to Set Bool. Thus, a function fromNatural is totally uninteresting for the general case of semirings.

On 2020-02-04 13:42, Zemyla wrote: > There is a homomorphism from the Naturals to any Semiring, which obeys: > > fromNatural 0 = zero > fromNatural 1 = one > fromNatural (m + n) = fromNatural m `plus` fromNatural n > fromNatural (m * n) = fromNatural m `times` fromNatural n > > The simplest implementation is this, but it's nowhere near the most > efficient: > > fromNatural :: Semiring a => Natural -> a > fromNatural 0 = zero > fromNatural n = one `plus` fromNatural (n - 1) > > One which takes O(log n) time instead of O(n) would go like this: > > fromNatural :: Semiring a => Natural -> a > fromNatural = go 0 zero one > go i s m n | i `seq` s `seq` m `seq` n `seq` False = undefined > go _ s _ 0 = s > go i s m n > | testBit n i = go (i + 1) (plus s m) (plus m m) (clearBit n i) > | otherwise = go (i + 1) s (plus m m) n > > On Tue, Feb 4, 2020, 02:21 Andreas Abel mailto:andreas.abel@ifi.lmu.de > mailto:andreas.abel@ifi.lmu.de>> wrote: > > > class Semiring a where > > zero :: a > > plus :: a -> a -> a > > one :: a > > times :: a -> a -> a > > fromNatural :: Natural -> a > > I think `fromNatural` should not be part of the `Semiring` class, > but we > could have an extension (NaturalSemiring) that adds this method. > > In the Agda code base, we have, for lack of a standard, rolled our own > semiring class, > > https://github.com/agda/agda/blob/master/src/full/Agda/Utils/SemiRing.hs > > and we use it for several finite semirings, e.g., > > > https://github.com/agda/agda/blob/64c0c2e813a84f91b3accd7c56efaa53712bc3f5/s... > > Cheers, > Andreas > > On 2020-02-03 22:34, Carter Schonwald wrote: > > Andrew: could you explain the algebra notation you were using for > short > > hand? I think I followed, but for people the libraries list > might be > > their first exposure to advanced / graduate abstract algebra (which > > winds up being simpler than most folks expect ;) ) > > > > On Fri, Jan 31, 2020 at 4:36 PM Carter Schonwald > > mailto:carter.schonwald@gmail.com mailto:carter.schonwald@gmail.com> > mailto:carter.schonwald@gmail.com > mailto:carter.schonwald@gmail.com>>> wrote: > > > > that actually sounds pretty sane. I think! > > > > On Fri, Jan 31, 2020 at 3:38 PM Andrew Lelechenko > > mailto:andrew.lelechenko@gmail.com > mailto:andrew.lelechenko@gmail.com> > mailto:andrew.lelechenko@gmail.com > mailto:andrew.lelechenko@gmail.com>>> > > wrote: > > > > On Tue, 28 Jan 2020, Dannyu NDos wrote: > > > > > Second, I suggest to move `abs` and `signum` from `Num` to > > `Floating` > > > > I can fully relate your frustration with `abs` and > `signum` (and > > numeric type classes in Haskell altogether). But IMO breaking > > both in `Num` and in `Floating` at once is not a > promising way > > to make things proper. > > > > I would rather follow the beaten track of Applicative > Monad and > > Semigroup Monoid proposals and - as a first step - > introduce a > > superclass (probably, borrowing the design from `semirings` > > package): > > > > class Semiring a where > > zero :: a > > plus :: a -> a -> a > > one :: a > > times :: a -> a -> a > > fromNatural :: Natural -> a > > class Semiring a => Num a where ... > > > > Tangible benefits in `base` include: > > a) instance Semiring Bool, > > b) a total instance Semiring Natural (in contrast to a > partial > > instance Num Natural), > > c) instance Num a => Semiring (Complex a) (in contrast to > > instance RealFloat a => Num (Complex a)), > > d) newtypes Sum and Product would require only Semiring > > constraint instead of Num. > > > > Best regards, > > Andrew > > > > > > _______________________________________________ > > Libraries mailing list > > Libraries@haskell.org mailto:Libraries@haskell.org mailto:Libraries@haskell.org> > mailto:Libraries@haskell.org mailto:Libraries@haskell.org>> > > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > > > > > > _______________________________________________ > > Libraries mailing list > > Libraries@haskell.org mailto:Libraries@haskell.org mailto:Libraries@haskell.org> > > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > > > _______________________________________________ > Libraries mailing list > Libraries@haskell.org mailto:Libraries@haskell.org mailto:Libraries@haskell.org> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries >

Carter Schonwald

6:50 p.m.

New subject: Break `abs` into two aspects

ooo, thats a good point about lattices/partial orders! (we like those here too, but sometimes forget :) ) On Wed, Feb 5, 2020 at 1:34 PM Andreas Abel wrote:

...

Well, I see your arguments, but cannot help the feeling that you are reasoning from a specific instance family of semirings, namely numerical ones (N, Z, Q, ...).

For idempotent semirings (e.g. the example I gave), repetitively adding one gets you nowhere. (Cf. also lattices, many of which are semirings.)

I'd be convinced if Natural was something like the free semiring, but this is certainly not the case.

Semirings are really diverse, I don't think the Semiring class should be hijacked for a particular flavor of semirings. We do not have any such pretext for Semigroup or Monoid either.

Enjoy the diversity at https://en.wikipedia.org/wiki/Semiring

On 2020-02-04 17:32, Zemyla wrote:

...
It really doesn't matter if it's not "interesting" or not surjective for some Semirings. It should be included, because:

(a) Even for semirings where it is "interesting", it's not surjective (for instance, Rational or Double) (b) It's a method with a default definition, so you don't have to expend any mental effort on it (c) A lot of instances have uninteresting methods: for instance, (*>) and (<*) for Applicative ((->) e) are const id and const respectively. Haskell adds methods to classes when they're always possible and sometimes useful/interesting/faster, rather than when they're always interesting. (d) It's useful for Semiring-generic methods and instances. (e) It can achieve an asymptotic speedup on some instances. Like, if you have Semiring a => Semiring (f a) for some type f, then you can have fromNatural n = pure (fromNatural n) instead of doing the whole O(log n) song and dance with the default definition. Also, your example admits a simple definition: fromNatural n = if n == 0 then S.empty else S.singleton True (f) "zero" and "one" can be defined in terms of fromNatural, for programmers who only need to define that: zero = fromNatural 0 one = fromNatural 1 This leads to the MINIMAL pragma on Semiring being {-# MINIMAL plus, times, (zero, one | fromNatural) #-} (g) If it's not included in the class, but in some subclass (NaturalSemiring, you proposed), but it's possible from the class, then people will just define and use the O(log n) version instead of requiring the subclass, leading to wasted effort and duplicated code.

On Tue, Feb 4, 2020, 09:20 Andreas Abel mailto:andreas.abel@ifi.lmu.de> wrote:

> There is a homomorphism from the Naturals to any Semiring

Sure, but there are many finite semirings where I would not care about such a homomorphism, thus, why force me to define it?

> fromNatural 0 = zero > fromNatural 1 = one > fromNatural (m + n) = fromNatural m `plus` fromNatural n > fromNatural (m * n) = fromNatural m `times` fromNatural n

This might not be surjective, and also not very interesting. For instance consider the semiring

Set Bool zero = Set.empty one = Set.singleton True plus = Set.union times s t = { x == y | x <- s, y <- t }

This semiring models variances (covariant = {True}, contravariant = {False}, constant = {}, dontknow = {True,False}). times is for function composition and plus combination of information.

The fromNatural targets only the zero/one-fragment since plus is idempotent. I conjecture there is not a single surjective semiring-hom from Nat to Set Bool. Thus, a function fromNatural is totally uninteresting for the general case of semirings.

On 2020-02-04 13:42, Zemyla wrote: > There is a homomorphism from the Naturals to any Semiring, which obeys: > > fromNatural 0 = zero > fromNatural 1 = one > fromNatural (m + n) = fromNatural m `plus` fromNatural n > fromNatural (m * n) = fromNatural m `times` fromNatural n > > The simplest implementation is this, but it's nowhere near the most > efficient: > > fromNatural :: Semiring a => Natural -> a > fromNatural 0 = zero > fromNatural n = one `plus` fromNatural (n - 1) > > One which takes O(log n) time instead of O(n) would go like this: > > fromNatural :: Semiring a => Natural -> a > fromNatural = go 0 zero one > go i s m n | i `seq` s `seq` m `seq` n `seq` False = undefined > go _ s _ 0 = s > go i s m n > | testBit n i = go (i + 1) (plus s m) (plus m m) (clearBit n i) > | otherwise = go (i + 1) s (plus m m) n > > On Tue, Feb 4, 2020, 02:21 Andreas Abel mailto:andreas.abel@ifi.lmu.de > mailto:andreas.abel@ifi.lmu.de>> wrote: > > > class Semiring a where > > zero :: a > > plus :: a -> a -> a > > one :: a > > times :: a -> a -> a > > fromNatural :: Natural -> a > > I think `fromNatural` should not be part of the `Semiring` class, > but we > could have an extension (NaturalSemiring) that adds this method. > > In the Agda code base, we have, for lack of a standard, rolled our own > semiring class, > >

https://github.com/agda/agda/blob/master/src/full/Agda/Utils/SemiRing.hs

...
> > and we use it for several finite semirings, e.g., > > >

https://github.com/agda/agda/blob/64c0c2e813a84f91b3accd7c56efaa53712bc3f5/s...

...
> > Cheers, > Andreas > > On 2020-02-03 22:34, Carter Schonwald wrote: > > Andrew: could you explain the algebra notation you were using for > short > > hand? I think I followed, but for people the libraries

list

...
> might be > > their first exposure to advanced / graduate abstract algebra (which > > winds up being simpler than most folks expect ;) ) > > > > On Fri, Jan 31, 2020 at 4:36 PM Carter Schonwald > > mailto:carter.schonwald@gmail.com
carter.schonwald@gmail.com>>

...
> mailto:carter.schonwald@gmail.com > mailto:carter.schonwald@gmail.com>>> wrote: > > > > that actually sounds pretty sane. I think! > > > > On Fri, Jan 31, 2020 at 3:38 PM Andrew Lelechenko > > mailto:andrew.lelechenko@gmail.com > mailto:andrew.lelechenko@gmail.com> > mailto:andrew.lelechenko@gmail.com > mailto:andrew.lelechenko@gmail.com>>> > > wrote: > > > > On Tue, 28 Jan 2020, Dannyu NDos wrote: > > > > > Second, I suggest to move `abs` and `signum` from `Num` to > > `Floating` > > > > I can fully relate your frustration with `abs` and > `signum` (and > > numeric type classes in Haskell altogether). But IMO breaking > > both in `Num` and in `Floating` at once is not a > promising way > > to make things proper. > > > > I would rather follow the beaten track of

Applicative

...
> Monad and > > Semigroup Monoid proposals and - as a first step - > introduce a > > superclass (probably, borrowing the design from `semirings` > > package): > > > > class Semiring a where > > zero :: a > > plus :: a -> a -> a > > one :: a > > times :: a -> a -> a > > fromNatural :: Natural -> a > > class Semiring a => Num a where ... > > > > Tangible benefits in `base` include: > > a) instance Semiring Bool, > > b) a total instance Semiring Natural (in contrast

to a

...
> partial > > instance Num Natural), > > c) instance Num a => Semiring (Complex a) (in contrast to > > instance RealFloat a => Num (Complex a)), > > d) newtypes Sum and Product would require only Semiring > > constraint instead of Num. > > > > Best regards, > > Andrew > > > > > > _______________________________________________ > > Libraries mailing list > > Libraries@haskell.org mailto:Libraries@haskell.org mailto:Libraries@haskell.org> > mailto:Libraries@haskell.org mailto:Libraries@haskell.org>> > > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > > > > > > _______________________________________________ > > Libraries mailing list > > Libraries@haskell.org mailto:Libraries@haskell.org mailto:Libraries@haskell.org> > > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries > > > _______________________________________________ > Libraries mailing list > Libraries@haskell.org mailto:Libraries@haskell.org mailto:Libraries@haskell.org> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries >

Zemyla

7 p.m.

New subject: Break `abs` into two aspects

If your semiring is idempotent, then you can simply have fromNatural = idempotentFromNatural where idempotentFromNatural :: Semiring a => Natural -> a idempotentFromNatural n = if n == 0 then zero else one It's like stimes in Semigroup. The default implementation is almost always sensible, and sometimes it can have more meaning (like how the Sum monoid allows negative values as the repeat argument in stimes). And again, it's an operation that can be defined by default on all Semirings, and can be vastly faster than the default on some. That, in my opinion, justifies its inclusion. If you don't feel it's meaningful for your Semiring, just let it be defined by default. But it's definitely useful for numeric and derived ones. On Wed, Feb 5, 2020, 12:51 Carter Schonwald wrote:

...

ooo, thats a good point about lattices/partial orders! (we like those here too, but sometimes forget :) )

On Wed, Feb 5, 2020 at 1:34 PM Andreas Abel wrote:

...
Well, I see your arguments, but cannot help the feeling that you are reasoning from a specific instance family of semirings, namely numerical ones (N, Z, Q, ...).

For idempotent semirings (e.g. the example I gave), repetitively adding one gets you nowhere. (Cf. also lattices, many of which are semirings.)

I'd be convinced if Natural was something like the free semiring, but this is certainly not the case.

Semirings are really diverse, I don't think the Semiring class should be hijacked for a particular flavor of semirings. We do not have any such pretext for Semigroup or Monoid either.

Enjoy the diversity at https://en.wikipedia.org/wiki/Semiring

On 2020-02-04 17:32, Zemyla wrote:

...
It really doesn't matter if it's not "interesting" or not surjective for some Semirings. It should be included, because:

(a) Even for semirings where it is "interesting", it's not surjective (for instance, Rational or Double) (b) It's a method with a default definition, so you don't have to expend any mental effort on it (c) A lot of instances have uninteresting methods: for instance, (*>) and (<*) for Applicative ((->) e) are const id and const respectively. Haskell adds methods to classes when they're always possible and sometimes useful/interesting/faster, rather than when they're always interesting. (d) It's useful for Semiring-generic methods and instances. (e) It can achieve an asymptotic speedup on some instances. Like, if you have Semiring a => Semiring (f a) for some type f, then you can have fromNatural n = pure (fromNatural n) instead of doing the whole O(log n) song and dance with the default definition. Also, your example admits a simple definition: fromNatural n = if n == 0 then S.empty else S.singleton True (f) "zero" and "one" can be defined in terms of fromNatural, for programmers who only need to define that: zero = fromNatural 0 one = fromNatural 1 This leads to the MINIMAL pragma on Semiring being {-# MINIMAL plus, times, (zero, one | fromNatural) #-} (g) If it's not included in the class, but in some subclass (NaturalSemiring, you proposed), but it's possible from the class, then people will just define and use the O(log n) version instead of requiring the subclass, leading to wasted effort and duplicated code.

On Tue, Feb 4, 2020, 09:20 Andreas Abel mailto:andreas.abel@ifi.lmu.de> wrote:

> There is a homomorphism from the Naturals to any Semiring

Sure, but there are many finite semirings where I would not care about such a homomorphism, thus, why force me to define it?

> fromNatural 0 = zero > fromNatural 1 = one > fromNatural (m + n) = fromNatural m `plus` fromNatural n > fromNatural (m * n) = fromNatural m `times` fromNatural n

This might not be surjective, and also not very interesting. For instance consider the semiring

Set Bool zero = Set.empty one = Set.singleton True plus = Set.union times s t = { x == y | x <- s, y <- t }

This semiring models variances (covariant = {True}, contravariant = {False}, constant = {}, dontknow = {True,False}). times is for function composition and plus combination of information.

The fromNatural targets only the zero/one-fragment since plus is idempotent. I conjecture there is not a single surjective semiring-hom from Nat to Set Bool. Thus, a function fromNatural is totally uninteresting for the general case of semirings.

On 2020-02-04 13:42, Zemyla wrote: > There is a homomorphism from the Naturals to any Semiring, which obeys: > > fromNatural 0 = zero > fromNatural 1 = one > fromNatural (m + n) = fromNatural m `plus` fromNatural n > fromNatural (m * n) = fromNatural m `times` fromNatural n > > The simplest implementation is this, but it's nowhere near the most > efficient: > > fromNatural :: Semiring a => Natural -> a > fromNatural 0 = zero > fromNatural n = one `plus` fromNatural (n - 1) > > One which takes O(log n) time instead of O(n) would go like this: > > fromNatural :: Semiring a => Natural -> a > fromNatural = go 0 zero one > go i s m n | i `seq` s `seq` m `seq` n `seq` False = undefined > go _ s _ 0 = s > go i s m n > | testBit n i = go (i + 1) (plus s m) (plus m m) (clearBit n i) > | otherwise = go (i + 1) s (plus m m) n > > On Tue, Feb 4, 2020, 02:21 Andreas Abel mailto:andreas.abel@ifi.lmu.de > mailto:andreas.abel@ifi.lmu.de>> wrote: > > > class Semiring a where > > zero :: a > > plus :: a -> a -> a > > one :: a > > times :: a -> a -> a > > fromNatural :: Natural -> a > > I think `fromNatural` should not be part of the `Semiring` class, > but we > could have an extension (NaturalSemiring) that adds this method. > > In the Agda code base, we have, for lack of a standard, rolled our own > semiring class, > >

https://github.com/agda/agda/blob/master/src/full/Agda/Utils/SemiRing.hs

...
> > and we use it for several finite semirings, e.g., > > >

https://github.com/agda/agda/blob/64c0c2e813a84f91b3accd7c56efaa53712bc3f5/s...

...
> > Cheers, > Andreas > > On 2020-02-03 22:34, Carter Schonwald wrote: > > Andrew: could you explain the algebra notation you were using for > short > > hand? I think I followed, but for people the libraries

list

...
> might be > > their first exposure to advanced / graduate abstract algebra (which > > winds up being simpler than most folks expect ;) ) > > > > On Fri, Jan 31, 2020 at 4:36 PM Carter Schonwald > > mailto:carter.schonwald@gmail.com
carter.schonwald@gmail.com>>

...
> mailto:carter.schonwald@gmail.com > mailto:carter.schonwald@gmail.com>>> wrote: > > > > that actually sounds pretty sane. I think! > > > > On Fri, Jan 31, 2020 at 3:38 PM Andrew Lelechenko > > mailto:andrew.lelechenko@gmail.com > mailto:andrew.lelechenko@gmail.com> > mailto:andrew.lelechenko@gmail.com > mailto:andrew.lelechenko@gmail.com>>> > > wrote: > > > > On Tue, 28 Jan 2020, Dannyu NDos wrote: > > > > > Second, I suggest to move `abs` and `signum` from `Num` to > > `Floating` > > > > I can fully relate your frustration with `abs` and > `signum` (and > > numeric type classes in Haskell altogether). But IMO breaking > > both in `Num` and in `Floating` at once is not a > promising way > > to make things proper. > > > > I would rather follow the beaten track of

Applicative

...
> Monad and > > Semigroup Monoid proposals and - as a first step - > introduce a > > superclass (probably, borrowing the design from `semirings` > > package): > > > > class Semiring a where > > zero :: a > > plus :: a -> a -> a > > one :: a > > times :: a -> a -> a > > fromNatural :: Natural -> a > > class Semiring a => Num a where ... > > > > Tangible benefits in `base` include: > > a) instance Semiring Bool, > > b) a total instance Semiring Natural (in contrast

to a

...
> partial > > instance Num Natural), > > c) instance Num a => Semiring (Complex a) (in contrast to > > instance RealFloat a => Num (Complex a)), > > d) newtypes Sum and Product would require only Semiring > > constraint instead of Num. > > > > Best regards, > > Andrew > > > > > > _______________________________________________ > > Libraries mailing list > > Libraries@haskell.org mailto:Libraries@haskell.org mailto:Libraries@haskell.org> > mailto:Libraries@haskell.org mailto:Libraries@haskell.org>> > >

http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

...
> > > > > > _______________________________________________ > > Libraries mailing list > > Libraries@haskell.org mailto:Libraries@haskell.org mailto:Libraries@haskell.org> > >

http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

...
> > > _______________________________________________ > Libraries mailing list > Libraries@haskell.org mailto:Libraries@haskell.org mailto:Libraries@haskell.org> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries >

Carter Schonwald

7:24 p.m.

New subject: Break `abs` into two aspects

ok, so would you make the case that "fromNatural" always can have a definition thats sound/satisfactory, even fro those ones that Andreas Abel is saying we're ignoring? On Wed, Feb 5, 2020 at 2:00 PM Zemyla wrote:

...

If your semiring is idempotent, then you can simply have

fromNatural = idempotentFromNatural

where

idempotentFromNatural :: Semiring a => Natural -> a idempotentFromNatural n = if n == 0 then zero else one

It's like stimes in Semigroup. The default implementation is almost always sensible, and sometimes it can have more meaning (like how the Sum monoid allows negative values as the repeat argument in stimes).

And again, it's an operation that can be defined by default on all Semirings, and can be vastly faster than the default on some. That, in my opinion, justifies its inclusion. If you don't feel it's meaningful for your Semiring, just let it be defined by default. But it's definitely useful for numeric and derived ones.

On Wed, Feb 5, 2020, 12:51 Carter Schonwald wrote:

...
ooo, thats a good point about lattices/partial orders! (we like those here too, but sometimes forget :) )

On Wed, Feb 5, 2020 at 1:34 PM Andreas Abel wrote:

...
Well, I see your arguments, but cannot help the feeling that you are reasoning from a specific instance family of semirings, namely numerical ones (N, Z, Q, ...).

For idempotent semirings (e.g. the example I gave), repetitively adding one gets you nowhere. (Cf. also lattices, many of which are semirings.)

I'd be convinced if Natural was something like the free semiring, but this is certainly not the case.

Semirings are really diverse, I don't think the Semiring class should be hijacked for a particular flavor of semirings. We do not have any such pretext for Semigroup or Monoid either.

Enjoy the diversity at https://en.wikipedia.org/wiki/Semiring

...
It really doesn't matter if it's not "interesting" or not surjective for some Semirings. It should be included, because:

(a) Even for semirings where it is "interesting", it's not surjective (for instance, Rational or Double) (b) It's a method with a default definition, so you don't have to expend any mental effort on it (c) A lot of instances have uninteresting methods: for instance, (*>) and (<*) for Applicative ((->) e) are const id and const respectively. Haskell adds methods to classes when they're always possible and sometimes useful/interesting/faster, rather than when they're always interesting. (d) It's useful for Semiring-generic methods and instances. (e) It can achieve an asymptotic speedup on some instances. Like, if you have Semiring a => Semiring (f a) for some type f, then you can have fromNatural n = pure (fromNatural n) instead of doing the whole O(log n) song and dance with the default definition. Also, your example admits a simple definition: fromNatural n = if n == 0 then S.empty else S.singleton True (f) "zero" and "one" can be defined in terms of fromNatural, for programmers who only need to define that: zero = fromNatural 0 one = fromNatural 1 This leads to the MINIMAL pragma on Semiring being {-# MINIMAL plus, times, (zero, one | fromNatural) #-} (g) If it's not included in the class, but in some subclass (NaturalSemiring, you proposed), but it's possible from the class,

...
people will just define and use the O(log n) version instead of requiring the subclass, leading to wasted effort and duplicated code.

On Tue, Feb 4, 2020, 09:20 Andreas Abel mailto:andreas.abel@ifi.lmu.de> wrote:

> There is a homomorphism from the Naturals to any Semiring

Sure, but there are many finite semirings where I would not care about such a homomorphism, thus, why force me to define it?

> fromNatural 0 = zero > fromNatural 1 = one > fromNatural (m + n) = fromNatural m `plus` fromNatural n > fromNatural (m * n) = fromNatural m `times` fromNatural n

This might not be surjective, and also not very interesting. For instance consider the semiring

Set Bool zero = Set.empty one = Set.singleton True plus = Set.union times s t = { x == y | x <- s, y <- t }

This semiring models variances (covariant = {True}, contravariant = {False}, constant = {}, dontknow = {True,False}). times is for function composition and plus combination of information.

The fromNatural targets only the zero/one-fragment since plus is idempotent. I conjecture there is not a single surjective semiring-hom from Nat to Set Bool. Thus, a function fromNatural is totally uninteresting for the general case of semirings.

On 2020-02-04 13:42, Zemyla wrote: > There is a homomorphism from the Naturals to any Semiring, which obeys: > > fromNatural 0 = zero > fromNatural 1 = one > fromNatural (m + n) = fromNatural m `plus` fromNatural n > fromNatural (m * n) = fromNatural m `times` fromNatural n > > The simplest implementation is this, but it's nowhere near the most > efficient: > > fromNatural :: Semiring a => Natural -> a > fromNatural 0 = zero > fromNatural n = one `plus` fromNatural (n - 1) > > One which takes O(log n) time instead of O(n) would go like

On 2020-02-04 17:32, Zemyla wrote: then this:

...
> > fromNatural :: Semiring a => Natural -> a > fromNatural = go 0 zero one > go i s m n | i `seq` s `seq` m `seq` n `seq` False =

undefined

...
> go _ s _ 0 = s > go i s m n > | testBit n i = go (i + 1) (plus s m) (plus m m) (clearBit

n i)

...
> | otherwise = go (i + 1) s (plus m m) n > > On Tue, Feb 4, 2020, 02:21 Andreas Abel <

andreas.abel@ifi.lmu.de

...
mailto:andreas.abel@ifi.lmu.de > mailto:andreas.abel@ifi.lmu.de>> wrote: > > > class Semiring a where > > zero :: a > > plus :: a -> a -> a > > one :: a > > times :: a -> a -> a > > fromNatural :: Natural -> a > > I think `fromNatural` should not be part of the `Semiring`

class,

...
> but we > could have an extension (NaturalSemiring) that adds this

method.

...
> > In the Agda code base, we have, for lack of a standard, rolled our own > semiring class, > >

https://github.com/agda/agda/blob/master/src/full/Agda/Utils/SemiRing.hs

...
> > and we use it for several finite semirings, e.g., > > >

https://github.com/agda/agda/blob/64c0c2e813a84f91b3accd7c56efaa53712bc3f5/s...

...
> > Cheers, > Andreas > > On 2020-02-03 22:34, Carter Schonwald wrote: > > Andrew: could you explain the algebra notation you were using for > short > > hand? I think I followed, but for people the libraries

list

...
> might be > > their first exposure to advanced / graduate abstract algebra (which > > winds up being simpler than most folks expect ;) ) > > > > On Fri, Jan 31, 2020 at 4:36 PM Carter Schonwald > > mailto:carter.schonwald@gmail.com
carter.schonwald@gmail.com>>

...
> mailto:carter.schonwald@gmail.com > mailto:carter.schonwald@gmail.com>>> wrote: > > > > that actually sounds pretty sane. I think! > > > > On Fri, Jan 31, 2020 at 3:38 PM Andrew Lelechenko > > mailto:andrew.lelechenko@gmail.com > mailto:andrew.lelechenko@gmail.com> > mailto:andrew.lelechenko@gmail.com > mailto:andrew.lelechenko@gmail.com>>> > > wrote: > > > > On Tue, 28 Jan 2020, Dannyu NDos wrote: > > > > > Second, I suggest to move `abs` and `signum` from `Num` to > > `Floating` > > > > I can fully relate your frustration with `abs`

and

...
> `signum` (and > > numeric type classes in Haskell altogether). But IMO breaking > > both in `Num` and in `Floating` at once is not a > promising way > > to make things proper. > > > > I would rather follow the beaten track of

Applicative

...
> Monad and > > Semigroup Monoid proposals and - as a first step

-

...
> introduce a > > superclass (probably, borrowing the design from `semirings` > > package): > > > > class Semiring a where > > zero :: a > > plus :: a -> a -> a > > one :: a > > times :: a -> a -> a > > fromNatural :: Natural -> a > > class Semiring a => Num a where ... > > > > Tangible benefits in `base` include: > > a) instance Semiring Bool, > > b) a total instance Semiring Natural (in

contrast to a

...
> partial > > instance Num Natural), > > c) instance Num a => Semiring (Complex a) (in contrast to > > instance RealFloat a => Num (Complex a)), > > d) newtypes Sum and Product would require only Semiring > > constraint instead of Num. > > > > Best regards, > > Andrew > > > > > > _______________________________________________ > > Libraries mailing list > > Libraries@haskell.org mailto:Libraries@haskell.org mailto:Libraries@haskell.org> >
mailto:Libraries@haskell.org>> > >

http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

...
> > > > > > _______________________________________________ > > Libraries mailing list > > Libraries@haskell.org mailto:Libraries@haskell.org mailto:Libraries@haskell.org> > >

http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

...
> > > _______________________________________________ > Libraries mailing list > Libraries@haskell.org mailto:Libraries@haskell.org mailto:Libraries@haskell.org> > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries >

Mario Blažević

8:18 p.m.

New subject: Break `abs` into two aspects

On 2020-02-04 11:32 a.m., Zemyla wrote:

...

It really doesn't matter if it's not "interesting" or not surjective for some Semirings. It should be included, because:

I fully agree, and I'll add another reason you left out. The presence of fromNatural would allow defaulting of Num's fromInteger as

...

fromInteger i | i >= 0 = fromNatural (fromInteger i) | otherwise = negate . fromInteger . negate $ i

...

(a) Even for semirings where it is "interesting", it's not surjective (for instance, Rational or Double) (b) It's a method with a default definition, so you don't have to expend any mental effort on it (c) A lot of instances have uninteresting methods: for instance, (*>) and (<*) for Applicative ((->) e) are const id and const respectively. Haskell adds methods to classes when they're always possible and sometimes useful/interesting/faster, rather than when they're always interesting. (d) It's useful for Semiring-generic methods and instances. (e) It can achieve an asymptotic speedup on some instances. Like, if you have Semiring a => Semiring (f a) for some type f, then you can have fromNatural n = pure (fromNatural n) instead of doing the whole O(log n) song and dance with the default definition. Also, your example admits a simple definition: fromNatural n = if n == 0 then S.empty else S.singleton True (f) "zero" and "one" can be defined in terms of fromNatural, for programmers who only need to define that: zero = fromNatural 0 one = fromNatural 1 This leads to the MINIMAL pragma on Semiring being {-# MINIMAL plus, times, (zero, one | fromNatural) #-} (g) If it's not included in the class, but in some subclass (NaturalSemiring, you proposed), but it's possible from the class, then people will just define and use the O(log n) version instead of requiring the subclass, leading to wasted effort and duplicated code.

Carter Schonwald

6 Feb 6 Feb

1:19 a.m.

New subject: Break `abs` into two aspects

Num doesn't have Ord as a parent constraint any more ... Though i suppose that works as a default signature instance? On Wed, Feb 5, 2020 at 3:19 PM Mario Blažević wrote:

...

On 2020-02-04 11:32 a.m., Zemyla wrote:

...
It really doesn't matter if it's not "interesting" or not surjective for some Semirings. It should be included, because:

I fully agree, and I'll add another reason you left out. The presence of fromNatural would allow defaulting of Num's fromInteger as

...
fromInteger i | i >= 0 = fromNatural (fromInteger i) | otherwise = negate . fromInteger . negate $ i

...
(a) Even for semirings where it is "interesting", it's not surjective (for instance, Rational or Double) (b) It's a method with a default definition, so you don't have to expend any mental effort on it (c) A lot of instances have uninteresting methods: for instance, (*>) and (<*) for Applicative ((->) e) are const id and const respectively. Haskell adds methods to classes when they're always possible and sometimes useful/interesting/faster, rather than when they're always interesting. (d) It's useful for Semiring-generic methods and instances. (e) It can achieve an asymptotic speedup on some instances. Like, if you have Semiring a => Semiring (f a) for some type f, then you can have fromNatural n = pure (fromNatural n) instead of doing the whole O(log n) song and dance with the default definition. Also, your example admits a simple definition: fromNatural n = if n == 0 then S.empty else S.singleton True (f) "zero" and "one" can be defined in terms of fromNatural, for programmers who only need to define that: zero = fromNatural 0 one = fromNatural 1 This leads to the MINIMAL pragma on Semiring being {-# MINIMAL plus, times, (zero, one | fromNatural) #-} (g) If it's not included in the class, but in some subclass (NaturalSemiring, you proposed), but it's possible from the class, then people will just define and use the O(log n) version instead of requiring the subclass, leading to wasted effort and duplicated code.

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Zemyla

2:08 a.m.

New subject: Break `abs` into two aspects

"i" is an Integer there, which has an Ord instance. On Wed, Feb 5, 2020, 19:20 Carter Schonwald wrote:

...

Num doesn't have Ord as a parent constraint any more ... Though i suppose that works as a default signature instance?

On Wed, Feb 5, 2020 at 3:19 PM Mario Blažević wrote:

...
On 2020-02-04 11:32 a.m., Zemyla wrote:

...
It really doesn't matter if it's not "interesting" or not surjective for some Semirings. It should be included, because:

I fully agree, and I'll add another reason you left out. The presence of fromNatural would allow defaulting of Num's fromInteger as

...
fromInteger i | i >= 0 = fromNatural (fromInteger i) | otherwise = negate . fromInteger . negate $ i

...
(a) Even for semirings where it is "interesting", it's not surjective (for instance, Rational or Double) (b) It's a method with a default definition, so you don't have to expend any mental effort on it (c) A lot of instances have uninteresting methods: for instance, (*>) and (<*) for Applicative ((->) e) are const id and const respectively. Haskell adds methods to classes when they're always possible and sometimes useful/interesting/faster, rather than when they're always interesting. (d) It's useful for Semiring-generic methods and instances. (e) It can achieve an asymptotic speedup on some instances. Like, if you have Semiring a => Semiring (f a) for some type f, then you can have fromNatural n = pure (fromNatural n) instead of doing the whole O(log n) song and dance with the default definition. Also, your example admits a simple definition: fromNatural n = if n == 0 then S.empty else S.singleton True (f) "zero" and "one" can be defined in terms of fromNatural, for programmers who only need to define that: zero = fromNatural 0 one = fromNatural 1 This leads to the MINIMAL pragma on Semiring being {-# MINIMAL plus, times, (zero, one | fromNatural) #-} (g) If it's not included in the class, but in some subclass (NaturalSemiring, you proposed), but it's possible from the class, then people will just define and use the O(log n) version instead of requiring the subclass, leading to wasted effort and duplicated code.

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Carter Schonwald

7 Feb 7 Feb

3:01 p.m.

New subject: Break `abs` into two aspects

Derp. :) On Wed, Feb 5, 2020 at 9:08 PM Zemyla wrote:

...

"i" is an Integer there, which has an Ord instance.

On Wed, Feb 5, 2020, 19:20 Carter Schonwald wrote:

...
Num doesn't have Ord as a parent constraint any more ... Though i suppose that works as a default signature instance?

On Wed, Feb 5, 2020 at 3:19 PM Mario Blažević wrote:

...
On 2020-02-04 11:32 a.m., Zemyla wrote:

...
It really doesn't matter if it's not "interesting" or not surjective for some Semirings. It should be included, because:

I fully agree, and I'll add another reason you left out. The presence of fromNatural would allow defaulting of Num's fromInteger as

...
fromInteger i | i >= 0 = fromNatural (fromInteger i) | otherwise = negate . fromInteger . negate $ i

...
(a) Even for semirings where it is "interesting", it's not surjective (for instance, Rational or Double) (b) It's a method with a default definition, so you don't have to expend any mental effort on it (c) A lot of instances have uninteresting methods: for instance, (*>) and (<*) for Applicative ((->) e) are const id and const respectively. Haskell adds methods to classes when they're always possible and sometimes useful/interesting/faster, rather than when they're always interesting. (d) It's useful for Semiring-generic methods and instances. (e) It can achieve an asymptotic speedup on some instances. Like, if you have Semiring a => Semiring (f a) for some type f, then you can have fromNatural n = pure (fromNatural n) instead of doing the whole O(log n) song and dance with the default definition. Also, your example admits a simple definition: fromNatural n = if n == 0 then S.empty else S.singleton True (f) "zero" and "one" can be defined in terms of fromNatural, for programmers who only need to define that: zero = fromNatural 0 one = fromNatural 1 This leads to the MINIMAL pragma on Semiring being {-# MINIMAL plus, times, (zero, one | fromNatural) #-} (g) If it's not included in the class, but in some subclass (NaturalSemiring, you proposed), but it's possible from the class, then people will just define and use the O(log n) version instead of requiring the subclass, leading to wasted effort and duplicated code.

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Zemyla

8 Feb 8 Feb

7:36 p.m.

New subject: Break `abs` into two aspects

Should we move the Semiring discussion to a new proposal? On Fri, Feb 7, 2020, 09:01 Carter Schonwald wrote:

...

Derp. :)

On Wed, Feb 5, 2020 at 9:08 PM Zemyla wrote:

...
"i" is an Integer there, which has an Ord instance.

On Wed, Feb 5, 2020, 19:20 Carter Schonwald wrote:

...
Num doesn't have Ord as a parent constraint any more ... Though i suppose that works as a default signature instance?

On Wed, Feb 5, 2020 at 3:19 PM Mario Blažević wrote:

...
On 2020-02-04 11:32 a.m., Zemyla wrote:

...
It really doesn't matter if it's not "interesting" or not surjective for some Semirings. It should be included, because:

I fully agree, and I'll add another reason you left out. The presence of fromNatural would allow defaulting of Num's fromInteger as

...
fromInteger i | i >= 0 = fromNatural (fromInteger i) | otherwise = negate . fromInteger . negate $ i

...
(a) Even for semirings where it is "interesting", it's not surjective (for instance, Rational or Double) (b) It's a method with a default definition, so you don't have to expend any mental effort on it (c) A lot of instances have uninteresting methods: for instance, (*>) and (<*) for Applicative ((->) e) are const id and const respectively. Haskell adds methods to classes when they're always possible and sometimes useful/interesting/faster, rather than when they're always interesting. (d) It's useful for Semiring-generic methods and instances. (e) It can achieve an asymptotic speedup on some instances. Like, if you have Semiring a => Semiring (f a) for some type f, then you can have fromNatural n = pure (fromNatural n) instead of doing the whole O(log n) song and dance with the default definition. Also, your example admits a simple definition: fromNatural n = if n == 0 then S.empty else S.singleton True (f) "zero" and "one" can be defined in terms of fromNatural, for programmers who only need to define that: zero = fromNatural 0 one = fromNatural 1 This leads to the MINIMAL pragma on Semiring being {-# MINIMAL plus, times, (zero, one | fromNatural) #-} (g) If it's not included in the class, but in some subclass (NaturalSemiring, you proposed), but it's possible from the class, then people will just define and use the O(log n) version instead of requiring the subclass, leading to wasted effort and duplicated code.

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Carter Schonwald

8:32 p.m.

New subject: Break `abs` into two aspects

Please do. On Sat, Feb 8, 2020 at 2:36 PM Zemyla wrote:

...

Should we move the Semiring discussion to a new proposal?

On Fri, Feb 7, 2020, 09:01 Carter Schonwald wrote:

...
Derp. :)

On Wed, Feb 5, 2020 at 9:08 PM Zemyla wrote:

...
"i" is an Integer there, which has an Ord instance.

On Wed, Feb 5, 2020, 19:20 Carter Schonwald wrote:

...
Num doesn't have Ord as a parent constraint any more ... Though i suppose that works as a default signature instance?

On Wed, Feb 5, 2020 at 3:19 PM Mario Blažević wrote:

...
On 2020-02-04 11:32 a.m., Zemyla wrote:

...
It really doesn't matter if it's not "interesting" or not surjective for some Semirings. It should be included, because:

I fully agree, and I'll add another reason you left out. The presence of fromNatural would allow defaulting of Num's fromInteger as

...
fromInteger i | i >= 0 = fromNatural (fromInteger i) | otherwise = negate . fromInteger . negate $ i

...
(a) Even for semirings where it is "interesting", it's not surjective (for instance, Rational or Double) (b) It's a method with a default definition, so you don't have to expend any mental effort on it (c) A lot of instances have uninteresting methods: for instance, (*>) and (<*) for Applicative ((->) e) are const id and const respectively. Haskell adds methods to classes when they're always possible and sometimes useful/interesting/faster, rather than when they're always interesting. (d) It's useful for Semiring-generic methods and instances. (e) It can achieve an asymptotic speedup on some instances. Like, if you have Semiring a => Semiring (f a) for some type f, then you can have fromNatural n = pure (fromNatural n) instead of doing the whole O(log n) song and dance with the default definition. Also, your example admits a simple definition: fromNatural n = if n == 0 then S.empty else S.singleton True (f) "zero" and "one" can be defined in terms of fromNatural, for programmers who only need to define that: zero = fromNatural 0 one = fromNatural 1 This leads to the MINIMAL pragma on Semiring being {-# MINIMAL plus, times, (zero, one | fromNatural) #-} (g) If it's not included in the class, but in some subclass (NaturalSemiring, you proposed), but it's possible from the class, then people will just define and use the O(log n) version instead of requiring the subclass, leading to wasted effort and duplicated code.

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

1976

Age (days ago)

1987

Last active (days ago)

List overview

Download

20 comments

5 participants

participants (5)

Andreas Abel
Andrew Lelechenko
Carter Schonwald
Mario Blažević
Zemyla