[Haskell-cafe] Re: Numeric type classes
David Menendez
zednenem at psualum.com
Thu Sep 14 01:11:56 EDT 2006
Ross Paterson writes:
> Such features would be useful, but are unlikely to be available for
> Haskell'. If we concede that, is it still desirable to make these
> changes to the class hierarchy?
>
> I've collected some notes on these issues at
>
>
http://haskell.galois.com/cgi-bin/haskell-prime/trac.cgi/wiki/
StandardClasses
Coincidentally, I spent some time last week thinking about a replacement
for the Num class. I think I managed to come up with something that's
more flexible than Num, but still mostly comprehensible.
----
> class Monoid a where
> zero :: a
> (+) :: a -> a -> a
Laws:
identity : zero + a == a == a + zero
associativity : a + (b + c) == (a + b) + c
Motivation:
Common superclass for Group and Semiring.
> class Monoid a => Group a where
> negate :: a -> a
> (-) :: a -> a -> a
>
> a - b = a + negate b
> negate a = zero - a
Laws:
negate (negate a) == a
a + negate a == zero == negate a + a
Motivation:
Money, dimensional quantities, vectors.
An Abelian group is just a group where (+) is commutative. If there's a
need, we can declare a subclass.
For non-Abelian groups, it's important to note that (-) provides right
subtraction.
> class Monoid a => Semiring a where
> one :: a
> (*) :: a -> a -> a
Laws:
identity : one * a == a == a * one
associativity : a * (b * c) == (a * b) * c
zero annihilation : zero * a == zero == a * zero
Motivation:
Natural numbers support addition and multiplication, but not
negation.
Unexpectedly, instances of MonadPlus and ArrowPlus can also be
considered Semirings, with (>>) and (>>>) being the multiplication.
Since Semiring is a subclass of Monoid, we get the (+,0) instance for
free. The following wrapper implements the (*,1) monoid.
> newtype Prod a = Prod { unProd :: a }
>
> instance (Semiring a) => Monoid (Prod a) where
> zero = Prod one
> Prod a + Prod b = Prod (a * b)
> class (Semiring a, Group a) => Ring a where
> fromInteger :: Integer -> a
Placing 'fromInteger' here is similar to Num in spirit, but perhaps
undesirable.
I'm not sure what the contract is for fromInteger. Perhaps something
like,
fromInteger 0 = zero
fromInteger 1 = one
fromInteger n | n < 0 = negate (fromInteger (negate n))
fromInteger n = one + fromInteger (n-1)
Which, actually, could also be a default definition.
The original Num class is essentially a Ring with abs, signum, show, and
(==).
> class (Ring a, Eq a, Show a) => Num a where
> abs :: a -> a
> signum :: a -> a
These are probably best put in a NormedRing class or something.
----
I don't have enough math to judge the classes like Integral, Real,
RealFrac, etc, but Fractional is fairly straightforward.
> class Ring a => DivisionRing a where
> recip :: a -> a
> (/) :: a -> a -> a
> fromRational :: Rational -> a
>
> a / b = a * recip b
> recip a = one / a
Laws:
recip (recip a) == a, unless a == zero
a * recip a == one == recip a * a, unless a == zero
Motivation:
A division ring is essentially a field that doesn't require
multiplication to commute, which allows us to include quaternions and
other non-commuting division algebras.
Again, (/) represents right division.
----
These show up a lot, but don't have standard classes.
> class (Group g) => GroupAction g a | a -> g where
> add :: g -> a -> a
Laws:
add (a + b) c == add a (add b c)
add zero c == c
Motivation:
Vectors act on points, durations act on times, groups act on
themselves (another wrapper can provide that, if need be).
> class (GroupAction g a) => SymmetricGroupAction g a | a -> g where
> diff :: a -> a -> g
Laws:
diff a b == negate (diff b a)
diff (add a b) b == a
Motivation:
I'm not sure whether this is the correct class name, but it's
certainly a useful operation when applicable.
> class (Ring r, Group a) => Module r a | a -> r where
> mult :: r -> a -> a
Laws:
mult (a * b) c == mult a (mult b c)
mult one c == c
Motivation:
Scalar multiplication is fairly common. A module is essentially a
vector space over a ring, instead of a field.
It's fairly trivial to write an adapter to produce a GroupAction
instance for any Module.
----
For illustration, here's an example with vectors and points:
> data Pt a = Pt a a deriving (Eq, Show)
> data Vec a = Vec a a deriving (Eq, Show)
>
> instance (Ring a) => Monoid (Vec a) where
> zero = Vec 0 0
> Vec x y + Vec x' y' = Vec (x + x') (y + y')
>
> instance (Ring a) => Group (Vec a) where
> Vec x y - Vec x' y' = Vec (x - x') (y - y')
>
> instance (Ring a) => Module a (Vec a) where
> mult a (Vec x y) = Vec (a * x) (a * y)
>
> instance (Ring a) => GroupAction (Vec a) (Pt a) where
> add (Vec dx dy) (Pt x y) = Pt (dx + x) (dy + y)
>
> instance (Ring a) => SymmetricGroupAction (Vec a) (Pt a) where
> diff (Pt x y) (Pt x' y') = Vec (x - x') (y - y')
>
> midpoint p1 p2 = add (mult 0.5 (diff p1 p2)) p2
The type of midpoint is something like
(DivisionRing a, Module a b, SymmetricGroupAction b c) => c -> c -> c
--
David Menendez <zednenem at psualum.com> | "In this house, we obey the laws
<http://www.eyrie.org/~zednenem> | of thermodynamics!"
More information about the Haskell-Cafe
mailing list