!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFG H I J K L M N O P Q R S T U V W X Y Z [ \]^_`abcdefghijklmnopqrstuvwxyz{|}~ !"##$$$$$$$$%%%%%%%%%%&&&&&'''''((((()))))*****+++++++++++++++++++++++,,,,,,,,,,---...////////////000 1 1 1 1 2223333338         4 0An additive semigroup with idempotent addition.  a + a = a an additive abelian semigroup a + b = b + a UpartitionWith f c returns a list containing f a b for each a b such that a + b = c,   (a + b) + c = a + (b + c)  replicate 1 a = a 5 replicate (2 * n) a = replicate n a + replicate n a = replicate (2 * n + 1) a = replicate n a + replicate n a + a &replicate1p n r = replicate (1 + n) r    An additive monoid  zero + a = a = a + zero  !"#$%@An associative algebra built with a free module over a semiring &'eA pair of an additive abelian semigroup, and a multiplicative semigroup, with the distributive laws:  E a(b + c) = ab + ac -- left distribution (we are a LeftNearSemiring) I (a + b)c = ac + bc -- right distribution (we are a [Right]NearSemiring) XCommon notation includes the laws for additive and multiplicative identity in semiring. If you want that, look at Rig instead.  Ideally we'd use the cyclic definition:  ` class (LeftModule r r, RightModule r r, Additive r, Abelian r, Multiplicative r) => Semiring r Nto enforce that every semiring r is an r-module over itself, but Haskell doesn' t like that. (A multiplicative semigroup )*+,-./2the free commutative coalgebra over a set and Int @the free commutative coalgebra over a set and a given semigroup -the free commutative band coalgebra over Int $the free commutative band coalgebra The tensor Hopf algebra The tensor Hopf algebra NEvery coalgebra gives rise to an algebra by vector space duality classically. N Sadly, it requires vector space duality, which we cannot use constructively. ~ The dual argument only relies in the fact that any constructive coalgebra can only inspect a finite number of coefficients,  which we CAN exploit. The tensor algebra The tensor algebra  !"#$%&'()*+,-./()*+-,'!" ./%&#$ !""#$$%&&'()*+)*+,-./0123401234012340123412345`factorWith f c`% returns a non-empty list containing `f a b` for all `a, b` such that ` a * b = c`. _Results of factorWith f 0 are undefined and may result in either an error or an infinite list. 6 5656566 7=A bialgebra is both a unital algebra and counital coalgebra  where the & and ;$ are compatible in some sense with  the $ and 9. That is to say that  & and ;7 are a coalgebra homomorphisms or (equivalently) that  $ and 9 are an algebra homomorphisms. 89:IAn associative unital algebra over a semiring, built using a free module ;<=>?@ 789:;<=>?@ <=>?@:;897 7899:;;<=>?=>?@ABCD<An multiplicative semigroup with idempotent multiplication.  a * a = a EFABCDEFDEFCBAABCDEF5DEFDEF GHIJKLMGHIJKLMIJKLMGHGHHIJKLMJKLM N?A HopfAlgebra algebra on a semiring, where the module is free. When antipode . antipode = idM and antipode is an antihomomorphism then we are an InvolutiveBialgebra with inv = antipode as well ONONONOO PQBb is an associate of a if there exists a unit u such that b = a*u UThis relationship is symmetric because if u is a unit, u^-1 exists and is a unit, so  b*u^-1 = a*u*u^-1 = a RSPQRSPQRSPQQRS TUVWXYTUVWXYTUVWXYTUVWUVWXY Z[Z[Z[Z[[\A Ring without (n)egation ]^_\]^_\]^_\]]^_`a!"b#c$NB: we'4re using the boolean semiring, not the boolean ring `abc`abc`aabcdA Ring without an i dentity. dddefgefgefgeffghhhh6 !"!" i7a rectangular band is a nowhere commutative semigroup. = That is to say, if ab = ba then a = b. From this it follows = classically that aa = a and that such a band is isomorphic  to the following structure jijijijjk*An integral semiring has no zero divisors $ a * b = 0 implies a == 0 || b == 0 kkklmno'A commutative multiplicative semigroup lmnoonmllmno pqrstuvwx  adjoint = id y(adjoint (x + y) = adjoint x + adjoint y zAn semigroup with involution ) adjoint a * adjoint b = adjoint (b * a) { pqrstuvwxyz{ z{yvwstqxurp pqrsttuvwwxyz{{7yy|||| }JLinear functionals from elements of an (infinite) free module to a scalar ~%TconvolveM antipodeM return = convolveM return antipodeM = comultM >=> uncurry joinM }~ }~ }~~ ` Additive.(+)` default definition Additive.replicate1p default definition  Monoidal.zero default definition Monoidal.replicate default definition  Group.negate default definition ` Group.(-)` default definition Group.subtract default definition  Group.times default definition `Multiplicative.(*)` default definition  Unital.one default definition Rig.fromNatural default definition Ring.fromInteger default definition !z + x < = z + y = x < = y = x + z <= y + z "#&8  !"#$%&'()*+,./0123456789:;<=>?@ACDEFGHIJKLMNOPTZ\]`abcdefhlmnopqrstuvwxyz{|}~/.01234()*+,o<=>?@DEFIJKLM56z{x'yd\]efh|!" %&#$:;897vwstqurpCAnlmGHNO`abc ZTP}~$3half of the Cayley-Dickson quaternion isomorphism % 0Cayley-Dickson quaternion isomorphism (one way) 'the trivial diagonal coalgebra (the quaternion algebra  &dual number basis, D^2 = 0. D /= 0. '()'the hyperbolic trigonometric coalgebra *the trivial diagonal algebra )dual number basis, D^2 = 0. D /= 0. *++,-./, 0Cayley-Dickson quaternion isomorphism (one way) 0!dual quaternion comultiplication 1the trivial diagonal algebra  -./ Ilinear maps from elements of a free module to another free module over r  " f $# x + y = (f $# x) + (f $# y)  f $# (r .* x) = r .* (f $# x)  Map r b a; represents a linear mapping from a free module with basis a over r to a free module with basis b over r. ]Note well the reversed direction of the arrow, due to the contravariance of change of basis! ]This way enables we can employ arbitrary pure functions as linear maps by lifting them using 2, or build them l by using the monad instance for Map r b. As a consequence Map is an instance of, well, almost everything. 3.extract a linear functional from a linear map M(inefficiently) combine a linear combination of basis vectors to make a map. 4 arrMap :: (Monoidal r, Semiring r) => (b -> [(r, a)]) -> Map r b a  arrMap f = Map $ k b -> sum [ r * k a | (r, a) <- f b ] 'Memoize the results of this linear map Econvolution given an associative algebra and coassociative coalgebra    01 =The free Ring given a Rng obtained by adjoining Z, such that   RngRing r = n*1 + r "This ring is commonly denoted r^.   )The rng homomorphism from r to RngRing r  igiven a rng homomorphism from a rng r into a ring s, liftRngHom yields a ring homomorphism from the ring `r^` into s.              2 http:en.wikipedia.orgwikiOpposite_ring    3\The endomorphism ring of an abelian group or the endomorphism semiring of an abelian monoid http:en.wikipedia.orgwikiEndomorphism_ring 459:;<<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~        !"##$$$$$$$$%%%%%%%%%%&&&&&'''''((((()))))*****+++++++++++++++ + + + + ++++,,,,,,,,,,---.../// /!/"/#/$/%/&/'/(/)0*0*0+1,1,1-1.2/2/203131323334356789:;<=>?6@@ABC#D%E%F(G(H+I+I+J+K+L,M,NOPQ/R3ST algebra-0.7.1Numeric.Natural.InternalNumeric.Order.ClassNumeric.Additive.ClassNumeric.Algebra.ClassNumeric.Additive.GroupNumeric.Algebra.FactorableNumeric.Algebra.UnitalNumeric.Algebra.IdempotentNumeric.Algebra.DivisionNumeric.Algebra.HopfNumeric.Decidable.AssociatesNumeric.Decidable.UnitsNumeric.Decidable.ZeroNumeric.Rig.ClassNumeric.Rig.CharacteristicNumeric.Rng.ClassNumeric.Ring.ClassNumeric.Ring.DivisionNumeric.Band.RectangularNumeric.Semiring.IntegralNumeric.Algebra.CommutativeNumeric.Algebra.InvolutiveNumeric.Field.ClassNumeric.Covector#Numeric.Algebra.Distinguished.ClassNumeric.Algebra.Complex.Class Numeric.Algebra.Quaternion.ClassNumeric.Algebra.Dual.Class"Numeric.Coalgebra.Hyperbolic.Class%Numeric.Coalgebra.Trigonometric.ClassNumeric.Dioid.ClassNumeric.Module.RepresentableNumeric.Order.AdditiveNumeric.Rig.OrderedNumeric.Quadrance.ClassNumeric.Algebra.ComplexNumeric.Algebra.QuaternionNumeric.Algebra.DualNumeric.Algebra.HyperbolicNumeric.Coalgebra.HyperbolicNumeric.Coalgebra.DualNumeric.Coalgebra.TrigonometricNumeric.Coalgebra.GeometricNumeric.Coalgebra.Quaternion Numeric.Exp Numeric.Log Numeric.MapNumeric.Rng.ZeroNumeric.Ring.RngNumeric.Ring.OppositeNumeric.Ring.EndomorphismNumeric.NaturalNumeric.Band.ClassNumeric.Module.ClassNumeric.Semiring.InvolutiveNumeric.AlgebraWhole toNatural unsafePredNatural runNaturalOrder<~<>~>~~/~order comparableorderOrd IdempotentAbelian Partitionable partitionWithAdditive+ replicate1psumWith1sum1replicate1pIdempotentMonoidalzero replicatesumWithModule RightModule*. LeftModule.* CoalgebracomultAlgebramultSemiringMultiplicative*pow1p productWith1product1 pow1pIntegralsumreplicateIdempotentGroup-negatesubtracttimes Factorable factorWith BialgebraCounitalCoalgebracounit UnitalAlgebraunitUnitalonepow productWithproductIdempotentBialgebraIdempotentCoalgebraIdempotentAlgebraBand pow1pBandpowBandDivisionAlgebra recipriocalDivisionrecip/\\^ HopfAlgebraantipodeDecidableAssociates isAssociateisAssociateIntegralisAssociateWholeDecidableUnits recipUnitisUnit^?recipUnitIntegralrecipUnitWhole DecidableZeroisZeroRig fromNaturalfromNaturalNum fromWholeCharacteristiccharcharIntcharWordRngRing fromInteger fromIntegral DivisionRingRectIntegralSemiringCommutativeBialgebraCocommutativeCoalgebraCommutativeAlgebra CommutativeTriviallyInvolutiveBialgebraInvolutiveBialgebraTriviallyInvolutiveCoalgebraInvolutiveCoalgebracoinvTriviallyInvolutiveAlgebraInvolutiveAlgebrainvTriviallyInvolutiveInvolutiveSemiringInvolutiveMultiplicationadjointFieldCovectormultMunitMcomultMcounitM convolveMinvMcoinvM antipodeMmemoM Distinguishede Complicatedi Hamiltonianjk Infinitesimald Hyperboliccoshsinh TrigonometriccossinDioidaddRepreplicate1pRepzeroRep replicateRep negateRepminusRep subtractReptimesRepmulReponeRepfromNaturalRepfromIntegerRep AdditiveOrder OrderedRig Quadrance quadranceComplex ComplexBasisIErealPartimagPart uncomplicate QuaternionQuaternionBasisKJ complicate scalarPart vectorPartDual DualBasisDHyper' HyperBasis'Sinh'Cosh'Hyper HyperBasisSinhCoshDual' DualBasis'Trig TrigBasisSinCos Comultivector Eigenmetricmetric Eigenbasis euclidean antiEuclideanv BasisCobladerunBasisCobladegrade filterGradereversecliffordConjugategradeInversion geometricouter contractL contractRdothestenes liftProduct Quaternion'QuaternionBasis'K'J'I'E' complicate' scalarPart' vectorPart'ExprunExpLogrunLogMap$@memoMap comultMapmultMap counitMapunitMap convolveMap antipodeMapcoinvMapinvMapZeroRng runZeroRngRngRing rngRingHom liftRngHomOpposite runOppositeEndappEndtoEndfromEnd frobeniusconcat$fCoalgebrarIntMap$fCoalgebrarMap$fCoalgebrarIntSet$fCoalgebrarSet$fCoalgebrarSeq$fCoalgebrar[]$fCoalgebrar(->) $fAlgebrarSeq $fAlgebrar[]Proxy asProxyTypeOf$fCharacteristicBool$*sq$fCoalgebrarQuaternionBasis$fAlgebrarQuaternionBasis$fCoalgebrakHyperBasis$fAlgebrakHyperBasis Euclideanlsb m1powTimesreorder$fCoalgebrarQuaternionBasis'$fAlgebrarQuaternionBasis'base Control.Arrowarr$#ofRing