Data.Algebra

Common library for algebraic structures. Has the advantage of automatically inferring lots of useful structure, especially in the writing of linear programs. For example, here are several ways of writing 3 x - 4 y + z:

 gsum [3 *& x, (-4) *^ var y, var z]
 linCombination [(3, x), (-4, y), (1, z)]
 3 *& x ^-^ 4 *& y ^+^ var z

In addition, if we have two functions f and g, we can construct linear combinations of those functions, using exactly the same syntax. Moreover, we can multiply functions with Double coefficients by Rational values successfully. This module is intended to offer as much generality as possible without getting in your way.

Algebraic structures

class Group g where

The algebraic structure of a group. Written additively. Required functions: zero and (^-^ or (^+^ and neg)).

Methods

zero :: g

(^+^) :: g -> g -> g

(^-^) :: g -> g -> g

neg :: g -> g

Instances

Group Bool

Group Double

Group Int

Group Integer

Integral a => Group (Ratio a)

Group g => Group (IntMap g)

Group g => Group (Poly g)

Group g => Group (a -> g)

(Group g1, Group g2) => Group (g1, g2)

(Ord k, Group g) => Group (Map k g)

(Ord v, Group c) => Group (LinExpr v c)

(Group g1, Group g2, Group g3) => Group (g1, g2, g3)

(Group g1, Group g2, Group g3, Group g4) => Group (g1, g2, g3, g4)

class Group r => Ring r where

The algebraic structure of a unital ring. Assumes that the additive operation forms an abelian group, that the multiplication operation forms a group, and that multiplication distributes.

Methods

one :: r

(*#) :: r -> r -> r

Instances

Ring Bool

Ring Double

Ring Int

Ring Integer

Integral a => Ring (Ratio a)

Ring r => Ring (Poly r)

The polynomial ring.

Ring r => Ring (a -> r)

The function ring.

(Ord g, Group g, Ring r) => Ring (GroupRing r g)

The group ring.

class Ring f => Field f where

Methods

inv :: f -> f

(/#) :: f -> f -> f

Instances

Field Double

Integral a => Field (Ratio a)

class (Ring r, Group m) => Module r m where

The algebraic structure of a module. A vector space is a module with coefficients in a field.

Methods

(*^) :: r -> m -> m

Instances

Module Double Double

Module Int Double

Module Int Int

Module Int Integer

Module Integer Double

Module Integer Integer

Integral a => Module Int (Ratio a)

Integral a => Module Integer (Ratio a)

Module r m => Module r (IntMap m)

(Module r m1, Module r m2) => Module r (m1, m2)

(Ord k, Module r m) => Module r (Map k m)

Module r m => Module r (a -> m)

(Ord v, Module r c) => Module r (LinExpr v c)

(Module r m1, Module r m2, Module r m3) => Module r (m1, m2, m3)

(Module r m1, Module r m2, Module r m3, Module r m4) => Module r (m1, m2, m3, m4)

Integral a => Module (Ratio a) Double

Integral a => Module (Ratio a) (Ratio a)

(Ord g, Group g, Ring r) => Module (GroupRing r g) (GroupRing r g)

class (Module f v, Field f) => VectorSpace f v

Instances

(Module f v, Field f) => VectorSpace f v

type Poly = []

varPoly :: Ring r => Poly r

Returns the polynomial p(x) = x.

type GroupRing r g = Map g r

A way of forming a ring from functions. See http://en.wikipedia.org/wiki/Group_ring.

type LinFunc = Map

LinFunc v c is a linear combination of variables of type v with coefficients from c. Formally, this is the free c-module on v.

Algebraic functions

gsum :: Group g => [g] -> g

Does a summation over the elements of a group.

combination :: Module r m => [(r, m)] -> m

Given a collection of vectors and scaling coefficients, returns this linear combination.

evalPoly :: (Module r m, Ring m) => Poly r -> m -> m

Substitution into a polynomial.

Specialized methods on linear functions

var :: (Ord v, Ring c) => v -> LinFunc v c

Given a variable v, returns the function equivalent to v.

varSum :: (Ord v, Ring c) => [v] -> LinFunc v c

Equivalent to vsum . map var.

(*&) :: (Ord v, Ring c) => c -> v -> LinFunc v c

c *& v is equivalent to c *^ var v.

linCombination :: (Ord v, Num r) => [(r, v)] -> LinFunc v r

Given a set of basic variables and coefficients, returns the linear combination obtained by summing.