search

Bodigrim / arithmoi

Number theory: primes, arithmetic functions, modular computations, special sequences
http://hackage.haskell.org/package/arithmoi
MIT License
147 stars 40 forks source link

Wrap output of splitIntoCoprimes into newtype #89

Closed Bodigrim closed 6 years ago

Bodigrim commented 6 years ago

Currently splitIntoCoprimes guarantees certain properties of its output, but still returns a plain [(a, b)]. Such return type is easily corruptible by other functions. It would be much better to return something like 

newtype Coprimes a b = Coprimes (Map a b)

The interface should not expose Coprimes constructor outside. Here is a quick draft of API:

instance Semigroup (Coprimes a b) where ...

instance Monoid (Coprimes a b) where ...

insert :: a -> b -> Coprimes a b -> Coprimes a b 

toList :: Coprimes a b -> [(a, b)]

Another vaguely related idea is to keep coprimes, which are known to be prime, separately. This can potentially speed up certain computations, especially with Prefactored. Like 

data Coprimes a b = Coprimes (Map (Prime a) b) (Map a b)
cartazio commented 6 years ago

Style wise I like to use record fields to document what different positions in a tuple mean. (One of my fave party tricks Is showing that you can mix record and fast syntax. Though that’s not relevant here ;) )

On Tue, Jan 2, 2018 at 5:16 PM Bodigrim notifications@github.com wrote:

Currently splitIntoCoprimes https://github.com/cartazio/arithmoi/blob/master/Math/NumberTheory/GCD.hs#L267 guarantees certain properties of its output, but still returns a plain [(a, b)]. Such return type is easily corruptible by other functions. It would be much better to return something like

newtype Coprimes a b = Coprimes (Map a b)

The interface should not expose Coprimes constructor outside. Here is a quick draft of API:

instance Semigroup (Coprimes a b) where ... instance Monoid (Coprimes a b) where ... insert :: a -> b -> Coprimes a b -> Coprimes a b toList :: Coprimes a b -> [(a, b)]

Another vaguely related idea is to keep coprimes, which are known to be prime, separately. This can potentially speed up certain computations, especially with Prefactored. Like

data Coprimes a b = Coprimes (Map (Prime a) b) (Map a b)

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/cartazio/arithmoi/issues/89, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAQwpoXD9xxn5LBbmRijtJQ7wlrCC1Gks5tGqrPgaJpZM4RRJFB .