w*      !"#$%&'()*+,-./0123456789:;<= > ? @ A B C D E F G H I J K L M N O P Q R S T U V W XYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ !!!"""#$$$$$$$$$$$$%&''''(((())********++++++++++,,,,,-----...../////00000111111111111111111111111122222222223 3 3 4 4 4555555555555666777 7!8"8#8$9%9&9'9(9)9>         *: 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. 0A multiplicative semigroup 1234567,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 0The tensor Hopf algebra 1The tensor Hopf algebra 2NEvery 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. 3The tensor algebra 4The tensor algebra "#$%&'()*+,-./01234567012354/)*'(&"#$%67-.+,"#$%#$%&'(()**+,,-../0123123456789:;<89:;<89:;<89:;<9:;< =`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. >5=>=>=>> ?=A bialgebra is both a unital algebra and counital coalgebra  where the . and C$ are compatible in some sense with  the , and A. That is to say that  . and C7 are a coalgebra homomorphisms or (equivalently) that  , and A are an algebra homomorphisms. @ABIAn associative unital algebra over a semiring, built using a free module CDEFGH ?@ABCDEFGH DEFGHBC@A? ?@AABCCDEFGEFGH IJKL<An multiplicative semigroup with idempotent multiplication.  a * a = a MNIJKLMNLMNKJIIJKLMN;LMNLMN OPQRSTUOPQRSTUQRSTUOPOPPQRSTURSTU V?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 WVWVWVWWXYBb 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 Z[XYZ[XYZ[XYYZ[\]^_`a\]^_`a\]^_`a\]^_]^_`abcbcbcbccdA Ring without (n)egation efgdefgdefgdeefghi67j8k9NB: we'4re using the boolean semiring, not the boolean ring hijkhijkhiijklA Ring without an i dentity. lllmnomnomnomnnopppp<&'()*)*'(&q7a 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 rqrqrqrrs*An integral semiring has no zero divisors $ a * b = 0 implies a == 0 || b == 0 ssstuvw'A commutative multiplicative semigroup tuvwwvuttuvw xyz{|}~  adjoint = id (adjoint (x + y) = adjoint x + adjoint y An semigroup with involution ) adjoint a * adjoint b = adjoint (b * a) xyz{|}~ ~{|y}zx xyz{||}~= 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 &'();>  !"#$%&'()*+,-./012346789:;<=>?@ABCDEFGHIKLMNOPQRSTUVWX\bdehijklmnptuvwxyz{|}~ !7"#$%689:;<01234wDEFGHLMNQRSTU=>/ldemnp)*'(&-.+,BC@A?~{|y}zxKIvtuOPVWhijk b\X*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. 01@AB2 0Cayley-Dickson quaternion isomorphism (one way) C!dual quaternion comultiplication Dthe trivial diagonal algebra  3          4              5 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 E, or build them l by using the monad instance for Map r b. As a consequence Map is an instance of, well, almost everything. F.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    67=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.    8!http:en.wikipedia.orgwikiOpposite_ring "#!"#!"#!"#"#9$\The endomorphism ring of an abelian group or the endomorphism semiring of an abelian monoid http:en.wikipedia.orgwikiEndomorphism_ring %&'()G$%&'()$%&'()$%&%&'()H?@ABBCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz { | } ~             !!!"""#$$$$$$$$$$$$%&''''(((())********++++++++++,,,,,-----. . . . . / / ///0000011111111111111111 1!1"1#1$1%1&1'1(2)2)2*2+2,2-2.2/202132323344444556565758595:5;5<5=5>5?5@6A6A6B7C7C7D7E8F8F8G9H9H9I9J9K9LMNOPQRSTUVW NXXYZ[)\+]+^._.`1a1b1c2d2efgh5i9jk algebra-0.8.0Numeric.Natural.InternalNumeric.Order.ClassNumeric.Partial.SemigroupNumeric.Partial.MonoidNumeric.Partial.GroupNumeric.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.Coalgebra.CategoricalNumeric.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.Order.LocallyFiniteNumeric.Algebra.IncidenceNumeric.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 comparableorderOrdPartialSemigrouppadd PartialMonoidpzero PartialGrouppnegatepminus psubtract 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 CommutativeTriviallyInvolutiveBialgebraInvolutiveBialgebraTriviallyInvolutiveCoalgebraInvolutiveCoalgebracoinvTriviallyInvolutiveAlgebraInvolutiveAlgebrainvTriviallyInvolutiveInvolutiveSemiringInvolutiveMultiplicationadjointFieldMorphismCovectormultMunitMcomultMcounitM convolveMinvMcoinvM antipodeMmemoM Distinguishede Complicatedi Hamiltonianjk Infinitesimald Hyperboliccoshsinh TrigonometriccossinDioidaddRepreplicate1pRepzeroRep replicateRep negateRepminusRep subtractReptimesRepmulReponeRepfromNaturalRepfromIntegerRep AdditiveOrder OrderedRigLocallyFiniteOrderrange rangeSizemoebiusInversionIntervalzetamoebius Quadrance quadranceComplex ComplexBasisIErealPartimagPart uncomplicate QuaternionQuaternionBasisKJ complicate scalarPart vectorPartDual DualBasisDHyper' HyperBasis'Sinh'Cosh'Hyper HyperBasisSinhCoshDual' DualBasis'Trig TrigBasisSinCos Euclidean 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 frobeniuspaddNumconcat$fCoalgebrarIntMap$fCoalgebrarMap$fCoalgebrarIntSet$fCoalgebrarSet$fCoalgebrarSeq$fCoalgebrar[]$fCoalgebrar(->) $fAlgebrarSeq $fAlgebrar[]Proxy asProxyTypeOf$fCharacteristicBool$*sq$fCoalgebrarQuaternionBasis$fAlgebrarQuaternionBasis$fCoalgebrakHyperBasis$fAlgebrakHyperBasislsb m1powTimesreorder$fCoalgebrarQuaternionBasis'$fAlgebrarQuaternionBasis'base Control.Arrowarr$#ofRing