ekmett / algebra Goto Github PK

It would be nice if algebra were updated to require containers <0.7 instead of <0.6. It seems to compile correctly with the new version of containers.

in particular,

-- assuming n /= 0, find the index of the least significant set bit in a basis blade
lsb :: BasisCoblade m -> Int
lsb n = fromIntegral $ ix ! shiftR ((n .&. (-n)) * 0x07EDD5E59A4E28C2) 58
  where 
    -- a 64 bit deBruijn multiplication table
    ix :: UArray (BasisCoblade m) Word8
    ix = listArray (0, 63)
      [ 63,  0, 58,  1, 59, 47, 53,  2
      , 60, 39, 48, 27, 54, 33, 42,  3
      , 61, 51, 37, 40, 49, 18, 28, 20
      , 55, 30, 34, 11, 43, 14, 22,  4
      , 62, 57, 46, 52, 38, 26, 32, 41
      , 50, 36, 17, 19, 29, 10, 13, 21
      , 56, 45, 25, 31, 35, 16,  9, 12
      , 44, 24, 15,  8, 23,  7,  6,  5
      ]

can be replaced with

findFirstSet x = 1 + countTrailingZeros x

and it'll work with Base as far back as 4.8 ,which would include ghc 7.10

Why does your definition of group require that the type also be an instance of left and right module? Your definition of PartialGroup doesn't require this, only that it is an instance of monoidal. This seems more correct to me.

At least for the type Complex (Fraction Integer), the inverse recip i returns i and not -i; see minimal example. As a consequence, recip i * i is -1, and not 1.

I think this is caused by not negating the imaginary part in (Complex.hs):

instance (Commutative r, InvolutiveSemiring r, DivisionRing r) => Division (Complex r) where
recip q@(Complex a b) = Complex (qq \\ a) (qq \\ b)
where qq = quadrance q

I hope, I am not misinterpreting the functions, or gave Complex (Fraction Integer) the wrong instances in the linked example.

I didn't try it on my own system since it didn't compile there. I'm using the previous version instead now.

A group is only a Z-module when the group is abelian, as you need (x*y)^2 == x^2 * y^2. However, ZeroRng has instance Group r => LeftModule Integer (ZeroRng r). The context should also require Abelian r. Similarly with the LeftModule Natural (ZeroRng r) declaration, and with RightModule.

It might be beneficial to add Abelian m to the requirements of LeftModule, as normally modules are required to have abelian addition. However, that isn't strictly speaking implied by the module axioms unless r is unital.

In particular, algebra uses the Control.Categorical.* namespace.

algebra depends on representable-functors (which you deprecated), and this leads to dependency hell: Currently, with ghc 7.8.2,

• cabal install algebra only finds a plan involving array-0.4.0.1, which apparently gives a conflict with regard to template-haskell,
• cabal install algebra --allow-newer is too optimistic and leads to genuine compile errors.

This started with problems I was having with the "instance (Additive m) => LeftModule () m" instance. Since what I'm trying to create is coordinate systems, I'd like to be able to say "instance (Semiring a) => LeftModule a (ThreeD a)" and "instance (Semiring a) => LeftModule a (Polar2D a)" and so on and so forth.

Whilst both the ThreeD and Polar2D instances make sense, they're obvious horribly incompatible with both each other and the existing "() m" instance. This would be resolved by making the Semiring type a functional dependency of the module type. What I don't know is what's likely to be broken by a change like this. Are there many cases where people are treating a type as a module over multiple rings at once?

I tried using your algebra's definitions of +,-,*,/ and hiding the one's from Prelude. But this doesn't work well because Double is not an instance of Division. Is there a reason for this?

It suffices to assume ZeroProductSemiring (ie the semiring variant of
Domain). Then Natural can be given a Euclidean instance.
Possibly doable by splitting Euclidean into EuclideanSemiring containing
the functions and Euclidean containing the PID superclass.

The PID constraint does make sense the moment we actually have a Ring,
since all euclidean domains are PIDs.

splitUnit is currently specified as follows:

let (u, n) = splitUnit r in r == u * n && fst (splitUnit n) == one && isUnit u

This condition is too weak and can be always be satsified by splitUnit r = (one,r). EuclideanDomain should inherit from DecidableAssociates and, letting (u',n') = splitUnit r', the specification should require that n == n' <-> isAssociate r r'.

Hi,

with GHC 7.6.1, Bits no longer imply Num and I get

[53 of 62] Compiling Numeric.Coalgebra.Geometric ( src/Numeric/Coalgebra/Geometric.hs, dist-ghc/build/Numeric/Coalgebra/Geometric.o )

src/Numeric/Coalgebra/Geometric.hs:125:12:
    Could not deduce (Num n) arising from the literal `1'
    from the context (Bits n, Group r)
      bound by the type signature for
                 m1powTimes :: (Bits n, Group r) => n -> r -> r
      at src/Numeric/Coalgebra/Geometric.hs:123:15-46
    Possible fix:
      add (Num n) to the context of
        the type signature for
          m1powTimes :: (Bits n, Group r) => n -> r -> r
    In the second argument of `(.&.)', namely `1'
    In the first argument of `(==)', namely `(n .&. 1)'
    In the expression: (n .&. 1) == 0
make: *** [build-ghc-stamp] Error 1

semigroupoids-6 is the first series compatible with GHC 9.6, and transformers-0.6 is the release shipped with GHC 9.6. See also

• commercialhaskell/stackage#6909
• commercialhaskell/stackage#6857

EDIT: also need to bump mtl

You don't have to have a Euclidean domain to have a GCD. In the polynomial library I'm working on, I currently have this instance:

instance (Euclidean a) => Euclidean (Poly a)

But it's a dirty lie. R[x] is a Euclidean domain if R is a field, but if R is only a Euclidean domain then R[x] is only a UFD. To make this instance work, I have to modify the default definition of euclid to factor out the content and primitive part of the polynomial and then run the standard Euclidean algorithm in polynomials over the fraction field.

Much of what's currently in Euclidean belongs in weaker structures, like a GCD domain or a UFD. I'll follow up with a concrete proposal once I have one.

due to the use of ConstraintKinds which are only available starting with GHC 7.4 (maybe add a base >= 4.5 constraint to future releases)

gcd' [x] = leadingUnit x — Huh? Shouldn't it be normalize x?

We spoke on IRC the other day about adding a newtype to represent the multiplicative group of a field. I've since generalized this slightly to separate Additively and Units types, so that if f is a field, its multiplicative group can be written as Additively (Units f).

I'm not sure how you want to organize this stuff into your module hierarchy, so rather than send a pull request I'll just paste my code here.

{-# LANGUAGE NoImplicitPrelude, GeneralizedNewtypeDeriving,
             FlexibleInstances, MultiParamTypeClasses #-}
module AlgebraExtras 
    (Additively(..), 
     Units(), fromUnits, toUnits, uncheckedToUnits
    ) where

import Prelude hiding (Num(..),recip)
import Data.Functor((<$>))
import Data.Maybe(fromJust)
import Numeric.Additive.Class
import Numeric.Additive.Group
import Numeric.Algebra
import Numeric.Decidable.Units
import Numeric.Partial.Group
import Numeric.Partial.Monoid
import Numeric.Partial.Semigroup

newtype Additively f = Additively f
    deriving (Eq,Ord,Show,Read)

instance (Multiplicative f) => Additive (Additively f) where
    (Additively x) + (Additively y) = Additively (x * y)

instance (Unital f) => LeftModule Natural (Additively f) where
    i .* (Additively x) = Additively (pow x i)

instance (Unital f) => RightModule Natural (Additively f) where
    (Additively x) *. i = Additively (pow x i)

instance (Unital f) => Monoidal (Additively f) where
    zero = Additively one

instance (Multiplicative f) => PartialSemigroup (Additively f) where
    padd x y = Just (x + y)

instance (Unital f) => PartialMonoid (Additively f) where
    pzero = zero

instance (DecidableUnits f) => PartialGroup (Additively f) where
    pnegate (Additively x) = Additively <$> recipUnit x

instance (Commutative f) => Abelian (Additively f)

newtype Units f = Units { fromUnits :: f }
    deriving (Eq,Ord,Show,Read,Multiplicative,Unital,Commutative,DecidableUnits)

toUnits :: (DecidableUnits f) => f -> Maybe (Units f)
toUnits x | isUnit x = Just $ Units x
          | otherwise = Nothing

uncheckedToUnits :: f -> Units f
uncheckedToUnits = Units

instance (DecidableUnits f) => Division (Units f) where
    recip (Units x) = Units (fromJust $ recipUnit x)

instance (DecidableUnits f) => LeftModule Integer (Additively (Units f)) where
    i .* (Additively (Units x)) = Additively (Units (fromJust $ x ^? i))

instance (DecidableUnits f) => RightModule Integer (Additively (Units f)) where
    (Additively (Units x)) *. i = Additively (Units (fromJust $ x ^? i))

instance (DecidableUnits f) => Group (Additively (Units f)) where
    negate (Additively x) = Additively (recip x)

The only sort of norm defined is Quadrance, and its name makes it seem like it should satisfy the parallelogram identity and so define an inner product. It would be useful to have a class for inner product spaces, i.e. modules with a symmetric sesquilinear form.