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