Re: Break `abs` into two aspects

4 Feb 2020

      ...
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