# Break `abs` into two aspects

Carter Schonwald carter.schonwald at gmail.com
Wed Feb 5 19:24:19 UTC 2020

```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 <zemyla at gmail.com> 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 <carter.schonwald at gmail.com>
> 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 <andreas.abel at ifi.lmu.de>
>> 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 <andreas.abel at ifi.lmu.de
>>> > <mailto:andreas.abel at 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 <
>>> andreas.abel at ifi.lmu.de
>>> >     <mailto:andreas.abel at ifi.lmu.de>
>>> >      > <mailto:andreas.abel at ifi.lmu.de
>>> >     <mailto:andreas.abel at 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/src/full/Agda/TypeChecking/Positivity/Occurrence.hs#L127-L155
>>> >      >
>>> >      >     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
>>> >      >      > <carter.schonwald at gmail.com
>>> >     <mailto:carter.schonwald at gmail.com>
>>> >     <mailto:carter.schonwald at gmail.com <mailto:
>>> carter.schonwald at gmail.com>>
>>> >      >     <mailto:carter.schonwald at gmail.com
>>> >     <mailto:carter.schonwald at gmail.com>
>>> >      >     <mailto:carter.schonwald at gmail.com
>>> >     <mailto:carter.schonwald at gmail.com>>>> wrote:
>>> >      >      >
>>> >      >      >     that actually sounds pretty sane. I think!
>>> >      >      >
>>> >      >      >     On Fri, Jan 31, 2020 at 3:38 PM Andrew Lelechenko
>>> >      >      >     <andrew.lelechenko at gmail.com
>>> >     <mailto:andrew.lelechenko at gmail.com>
>>> >      >     <mailto:andrew.lelechenko at gmail.com
>>> >     <mailto:andrew.lelechenko at gmail.com>>
>>> >      >     <mailto:andrew.lelechenko at gmail.com
>>> >     <mailto:andrew.lelechenko at gmail.com>
>>> >      >     <mailto:andrew.lelechenko at gmail.com
>>> >     <mailto:andrew.lelechenko at 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 at haskell.org <mailto:Libraries at haskell.org>
>>> >     <mailto:Libraries at haskell.org <mailto:Libraries at haskell.org>>
>>> >      >     <mailto:Libraries at haskell.org <mailto:Libraries at haskell.org
>>> >
>>> >     <mailto:Libraries at haskell.org <mailto:Libraries at haskell.org>>>
>>> >      >      >
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>> >      >      >
>>> >      >      >
>>> >      >      > _______________________________________________
>>> >      >      > Libraries mailing list
>>> >      >      > Libraries at haskell.org <mailto:Libraries at haskell.org>
>>> >     <mailto:Libraries at haskell.org <mailto:Libraries at haskell.org>>
>>> >      >      >
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>> >      >      >
>>> >      >     _______________________________________________
>>> >      >     Libraries mailing list
>>> >      > Libraries at haskell.org <mailto:Libraries at haskell.org>
>>> >     <mailto:Libraries at haskell.org <mailto:Libraries at haskell.org>>
>>> >      > http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>> >      >
>>> >
>>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/libraries/attachments/20200205/2e13bfe3/attachment.html>
```

More information about the Libraries mailing list