śĪ!õŠļīg      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefNone .4=>?@ACDHMSVXbkīj# numhask-freeinformal test suiteempty expression freeExp "0""0"&plain (with multiplicative precedence)2forget $ parseExp "1+2*3" :: FreeRing RingLaws Int˜FreeR (fromList [Bag {unbag = fromList [(FreeV 1,1),(FreeR (fromList [Bag {unbag = fromList [(FreeV 2,1)]},Bag {unbag = fromList [(FreeV 3,1)]}]),1)]}])freeExp "1+2*3" "(1+(2*3))"Additive unitalfreeExp "0+(2+0)*3+0""(2*3)",General additive associative and commutationfreeExp "(1+2)*3+(4+5)+6*7""(4+5+((1+2)*3)+(6*7))"Multiplicative unitalfreeExp "1*3+4*1+1*(5*6)" "(3+4+(5*6))",Multiplicative association (not commutative)freeExp "(2*6)*((4*5)*2)" "(2*6*4*5*2)" absorbativefreeExp "0*1+3*(3+4)*0""0"additive invertiblefreeExp "(1+2)+(-1+-2)""0" distribution ?a "Å (b + c) = (a · b) + (a · c) (b + c) · a = (b · a) + (c · a)leftfreeExp "2*(3+4)+2*5+2*6""(2*(3+4+5+6))"rightfreeExp "(3+4)*2+5*2+6*2""((3+4+5+6)*2)"mixed (left then right checks)freeExp "2*(3+4)*2+5*2+2*6*2""((5+(2*(3+4))+(2*6))*2)"INote that "(2*(3+4+6)*2+5*2)" is a valid alternative to what the current  % function comes up with.TODO: optional extras:If +one is faster than +a (a . b) + a ==> a . (b + one)If a is scalar ...6lifting an (additive bag) to a multiplication sequence 3+3+3+3 ==> 3*4introducing exponents 3*3*3*3 ==> 3^4 numhask-free.The free ring is a recursive sequence of bags.’aGiven multiplication is monoidal (with the free object a list) and addition is a commutative group (with the free object a bag), it seems intuitively the case that the free object for a ring is a recursive list of bags. It is recursive because the ordering of +'s and *'s does not reduce, so that the tree-like nature of the expression is not forgotten.’EAbstractly, the choice of what goes in what should be an arbitrary one; the free object could also be a (recursive) bag of lists. The addition collection structure feels like it should be within the multiplication structure, however, because of the distribution law equivalence that need to be honoured in the representation: ?a "Å (b + c) = (a · b) + (a · c) (b + c) · a = (b · a) + (c · a)›It is likely, in most endeavours, that multiplication is more expensive than addition, and the left hand side of these equations have less multiplications.WBecause the distribution laws are substitutions to both the left and the right, use of gc is indicated instead of a list (which is isomorphic to a list and thus allowed as an alternative).AThe free ring is the same general shape as the free monad in the  Khttps://hackage.haskell.org/package/free-5.1.4/docs/Control-Monad-Free.htmlfree library ,data Free f a = Pure a | Free (f (Free f a))0which in turn is almost the same shape as Fix eg newtype Fix f = Fix (f (Fix f))OIf Bag could form a Functor instance, then the Free Ring could be expressed as: 2data FreeRing a = 'Free' ('Compose' 'Bag' 'Seq') awhich is a very clean result. numhask-freešWhere an algebra involves two (or more) operators, the initial structure (the expression) is arrived at by grafting new types of branches using sum types. numhask-free Ring Laws ’a + b is closed zero + a = a a + zero = a (a + b) + c = a + (b + c) a + b == b + a a + negate a = zero a * b is closed one * a = a a * one = a (a * b) * c = a * (b * c) a * zero = zero zero * a = zero a * (b + c) = (a * b) + (a * c) (b + c) * a = (b * a) + (c * a)  numhask-freeAdditive Commutative Group Laws fa + b is closed zero + a = a a + zero = a (a + b) + c = a + (b + c) a + b == b + a a + negate a = zero€Adding invertibility to the list of laws for a commutative monoid gets us to the definition of a Commutative (or Abelian) Group.šInvertible (in combination with commutation) means forgetting a value when the inversion of the value is contained somewhere within the expression. For example, armed with a definition of what a negative number is, integer addition such as:  1+2+3+-1+-4+2>Can be represented as a bag of 2 2's, one 3 and minus one 4's.=let exbag = fromList [1,2,3,-1,-4,-2] :: Bag AddCommGroup Intexbag%Bag {unbag = fromList [(3,1),(4,-1)]} toList exbag[3,-4]&exAdd = toTreeL [0,1,2,3,0,-1,-4,-2,0]8putStrLn $ printf (forget exAdd :: Bag AddCommGroup Int)(3+-4)  numhask-free%The Free commutative monoid is a Bag.ĀIn addition to the forgetting needed for the free monoid, forgetting additions of zero and forgetting brackets, a commutative law means forgetting the order of the original expression structure.šA list that has lost it's order is sometimes referred to as a bag. An efficient representation of a bag is a (key,value) pair where the keys are elements in the initial expression and values are the number of times the element has occurred.¤In the usual surface-paradox typical of adjointness, the forgetting of the ordering of the initial structure induces a requirement that the carrier type be ordered.  numhask-freeMultiplicative monoid laws Aa * b is closed one * a = a a * one = a (a * b) * c = a * (b * c) one :: FreeMonoid MultMonoid IntFreeMonoid {leaves = []}ex1: (1 * 2) * (4 * 5) * 1Xlet ex1 = Branch (Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 4) (Leaf 5))) (Leaf 1);putStrLn $ printf (forget ex1 :: FreeMonoid MultMonoid Int)(2*4*5)1algebra (forget ex1 :: FreeMonoid MultMonoid Int)40 numhask-freeThe free monoid is a list.•Applying unital and associativity laws in the context of converting an expression tree into a free monoid, the simplest structure possible, involves:nforgetting whenever an element in the initial structure in the unit (one, say, in the case of multiplication).forgetting the brackets.#So, starting with the initial tree: /data Tree a = Leaf a | Branch (Tree a) (Tree a)6We graft on a sum tag to represent an empty structure: ;data Tree a = EmptyTree | Leaf a | Branch (Tree a) (Tree a)To %® the left/right structure of the tree we force the left side of the branch to be a value rather than another tree branch, so that the whole tree always branches to the right: 4data Tree a = EmptyTree | Leaf a | Branch a (Tree a)LLeaf a can be represented as Branch a EmptyTree, so we can simplify this to: +data Tree a = EmptyTree | Branch a (Tree a)AAnd this is the classical Haskell cons list with different names: data [] a = [] | a : [a] numhask-free 6e "• a == e left absorbing a "• e == e right absorbing"The absorbed element is forgotten.ab1: 0 * (2 * 5) == 0ab2: (2 * 5) * 0 == 0Rlet ab1 = Branch (Leaf (Example 0)) (Branch (Leaf (Example 2)) (Leaf (Example 5)))Rlet ab2 = Branch (Branch (Leaf (Example 2)) (Leaf (Example 5))) (Leaf (Example 0))(forget ab1 :: Tree AbsorbingOnly ExampleLeaf 0(forget ab2 :: Tree AbsorbingOnly ExampleLeaf 0 numhask-free  a "• a = aLImmediately repeated elements are forgotten in the equivalence class object.idem1: (5 "• 5) "• 1 == 5 "• 1#idem2: (1 "• 5) "• (1 "• 5) == (1 "• 5)but!idem3: (1 "• 5) "• 5 == (1 "• 5) "• 5(because we don't yet have associativity.Tlet idem1 = Branch (Branch (Leaf (Example 5)) (Leaf (Example 5))) (Leaf (Example 1))qlet idem2 = Branch (Branch (Leaf (Example 1)) (Leaf (Example 5))) (Branch (Leaf (Example 1)) (Leaf (Example 5)))Tlet idem3 = Branch (Branch (Leaf (Example 1)) (Leaf (Example 5))) (Leaf (Example 5))?putStrLn $ printf (forget idem1 :: Tree IdempotentOnly Example)(5 o 1)?putStrLn $ printf (forget idem2 :: Tree IdempotentOnly Example)(1 o 5)?putStrLn $ printf (forget idem3 :: Tree IdempotentOnly Example) ((1 o 5) o 5)5algebra (forget idem3 :: Tree IdempotentOnly Example)5 numhask-free Tinv a "• (a "• b) == b -- left cancellation (a "• b) "• inv b == a -- right cancellationbut inv a "• a == unit.is not a thing yet without a unit to equal to.ØThe cancellation (or reversal or negation) of a value and the value are both lost in forming the equivalence relationship. Editing and diffing are two obvious examples.QThe data structure for the equivalence class is unchanged, so Tree can be reused.inv1: -1 "• (1 "• 5) == 5inv2: (1 "• 5) "• -5 == 1"inv3: (1 "• 5) "• -1 == (1 "• 5) "• -1Vlet inv1 = Branch (Leaf (Example (-1))) (Branch (Leaf (Example 1)) (Leaf (Example 5)))Vlet inv2 = Branch (Branch (Leaf (Example 1)) (Leaf (Example 5))) (Leaf (Example (-5)))Xlet inv3 = Branch (Branch (Leaf (Example 1)) (Leaf (Example 5))) (Leaf ((Example (-1))))*forget inv1 :: Tree InvertibleOnly ExampleLeaf 5@putStrLn $ printf $ (forget inv3 :: Tree InvertibleOnly Example) ((1"•5)"•-1) numhask-free a "• b == b "• abut non-associative, so (a "• b) "• c == (b "• a) "• cbut (a "• b) "• c /= a "• (b "• c)aCommutation requires a "• b and b "• a to be represented the same, and this induces a preordering: someh form of (arbitrary) ordering is needed to consistently and naturally represent a "• b and b "• a as "ab".ķIn structural terms, a commutative tree is a mobile; a tree that has lost it's left and rightedness. To implement this forgetting, the left element of BranchC is arbitrarily chosen as always being less than or equal to the right element.c1: 3 "• (2 "• 1)c2: 3 "• (1 "• 2)c3: (1 "• 2) "• 3zlet c1 = forget $ Branch (Leaf (Example 3)) (Branch (Leaf (Example 2)) (Leaf (Example 1))) :: Tree CommutativeOnly Examplezlet c2 = forget $ Branch (Leaf (Example 3)) (Branch (Leaf (Example 1)) (Leaf (Example 2))) :: Tree CommutativeOnly Examplezlet c3 = forget $ Branch (Branch (Leaf (Example 1)) (Leaf (Example 2))) (Leaf (Example 3)) :: Tree CommutativeOnly Examplec1 == c2Truec1 == c3True numhask-free–Introduction of an associative law induces an equivalence class where, for example, (1 "• 2) "• 3 and 1 "• (2 "• 3) should be represented in the same way.%‚, the free object constructor, thus needs to forget about the tree shape (the brackets or parentheses of the original expression).ÅAs an algebra consumes an expression one element at a time, branches (or "links") still exist from one element to the next. The free object is still a tree structure, but it is the same tree shape.ĀForcing one side of the branch to be a value provides a tree structure that branches to the other side. The left branch as the value has been chosen in this representation but this is arbitrary.,let exl = toTreeL $ Example <$> [1,4,7,12,0]8putStrLn $ printf (forget exl :: Tree MagmaOnly Example)((((1"•4)"•7)"•12)"•0),let exr = toTreeR $ Example <$> [1,4,7,12,0]8putStrLn $ printf (forget exr :: Tree MagmaOnly Example)(1"•(4"•(7"•(12"•0))))?putStrLn $ printf (forget exl :: TreeA AssociativeOnly Example) 1"•4"•7"•12"•0“(\x -> (forget $ toTreeL x :: TreeA AssociativeOnly Example) == (forget $ toTreeR $ x :: TreeA AssociativeOnly Example)) (Example <$> [1,4,7,12,0])True numhask-free (a "• b) "• c = a "• (b "• c) numhask-freecThe introduction of unital laws to the algebra changes what the free structure is, compared to the ’# case. From this library's point of view, that an algebra is an instruction kit for constructing an object, the unital laws are an instruction to substitute "a" for whenever "unit "• a" occurs. Where an element is combined with the unit element, this operation should be erased and forgotten.ĻFor example, from the point of view of the free algebra, ((0 "• 4) "• 0) "• 12 and 4 "• 12 (say) are the same. The initial structure can be divided into equivalence classes where trees are isomorphic (the same).’In contrast to the MagmaOnly case, the forgetting of unit operations means that an empty tree can result from an initially non-empty initial structure. The easiest way to represent this potential free object is simply to graft an EmptyTree tag to a Tree with a sum type.vAn EmptyTree represents a collapse of an initial structure down to nothing, as a result of applying the unital laws eg?let init = toTreeL $ Example <$> [0,0,0] :: Tree NoLaws Example'forget init :: TreeU UnitalOnly Example EmptyTreešBy forgetting instances of the unital laws in the original expression, the unital laws cannot be violated in the free object because they no longer exist.Hlet init = toTreeL $ Example <$> [0,1,4,0,7,12,0] :: Tree NoLaws Example=putStrLn $ printf $ (forget init :: TreeU UnitalOnly Example)(((1"•4)"•7)"•12) numhask-free unit "• a = a a "• unit = a numhask-freeFree Algebra for a Magma a "• b is closed'Given an initial binary Tree structure: /data Tree a = Leaf a | Branch (Tree a) (Tree a)Y, a closed binary operation (a magma) and no other laws, the free algebra is also a Tree.Dlet init = toTreeL $ Example <$> [1,4,7,12,0] :: Tree NoLaws Example0let free = forget init :: Tree MagmaOnly ExampleputStrLn $ printf $ free((((1"•4)"•7)"•12)"•0) algebra free24 numhask-free example type  numhask-freeKA binary tree is a common initial structure when considering free algebras.›The initial object for a Magma algebra is typically a tree-like structure representing a computation or expression; a series of binary operations, such as: (1 "• 4) "• ((7 "• 12) "• 0)¤let m1 = Branch (Branch (Leaf (Example 1)) (Leaf (Example 4))) (Branch (Branch (Leaf (Example 7)) (Leaf (Example 12))) (Leaf (Example 0))) :: Tree MagmaOnly ExampleputStrLn $ printf m1((1"•4)"•((7"•12)"•0))# numhask-freeóStarting from a particular initial structure, different sets of laws may lead to the same actual structure (or free object). Informal phantom type are included in most structures to help distinguish these cases and supply differeing instances.$ numhask-freegA free algebra is a construction kit of operations and axioms that combine to produce values of a type.% numhask-freeœConvert from a structure (the initial type) to another structure, the free object, forgetting the algebraic laws encapsulated in the free object definition.& numhask-free3Create a free object from a carrier type singleton.' numhask-freeThe algebra of the free object. lift . algebra == id( numhask-freePretty print the free object.) numhask-freeQConvenience function to construct a Tree from a list with left bracket groupings.toTreeL [1,4,7,12,0]OBranch (Branch (Branch (Branch (Leaf 1) (Leaf 4)) (Leaf 7)) (Leaf 12)) (Leaf 0)* numhask-free<Construct a Tree from a list with a right bracket groupings.toTreeR [1,4,7,12,0]OBranch (Leaf 1) (Branch (Leaf 4) (Branch (Leaf 7) (Branch (Leaf 12) (Leaf 0))))+ numhask-free example magma, numhask-freeMThis is a functor from Ord -> Ord but, sadly, not a functor from Hask -> Hask- numhask-freeParse an Exp, forget to the  structure and print.:let t1 = "(4*(1+3)+(3+1)+6*(4+5*(11+6)*(3+2)))+(7+3+11*2)"putStrLn $ freeExp t13(1+3+3+7+(4*(1+3))+(6*(4+(5*(6+11)*(2+3))))+(11*2))h numhask-freeSingle bag a valuei numhask-freeSingle bag a FreeRing. numhask-freeText parser for an expression. Parenthesis is imputed assuming multiplicative precedence and left-to-right default association. \let t1 = "(4*(1+3)+(3+1)+6*(4+5*(11+6)*(3+2)))+(7+3+11*2)" putStrLn . printf . parseExp $ t1?((((4*(1+3))+(3+1))+(6*(4+((5*(11+6))*(3+2)))))+((7+3)+(11*2)))j numhask-freeExp parser > second printf $ A.parseOnly expr " ((1 + 3) + (4 + 5)) * (7 + 3 + 11 * 2)x" Right "(((1+3)+(4+5))*((7+3)+(11*2)))"/ numhask-freeUintercalate elements of an expression with an operator, and put brackets around this.0  !"#$&(%')*+,-./0$&(%'# !")*.- , +/k       !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijkl)numhask-free-0.0.1-5vb6HXEpncG2xKWJdxO6mANumHask.FreeAlgebra InformalTestsFreeRingFreeVFreeRExpValueAddMultRingLaws AddCommGroupBagunbag MultMonoid FreeMonoidleaves AbsorbingOnlyIdempotentOnlyInvertibleOnlyCommutativeOnlyTreeALeafABranchAAssociativeOnlyTreeU EmptyTree NonEmptyTree UnitalOnly MagmaOnlyExampleTreeLeafBranchNoLaws FreeAlgebraforgetliftalgebraprintftoTreeLtoTreeRāŠ•mapBagfreeExpparseExpcalate $fShowExample$fInvertibleExample$fAbsorbingExample$fUnitalExample$fMagmaExample$fFreeAlgebraTreeTreea$fFreeAlgebraTreeTreeUa$fFreeAlgebraTreeTreeAa$fFreeAlgebraTreeTreea0$fFreeAlgebraTreeTreea1$fFreeAlgebraTreeTreea2$fFreeAlgebraTreeTreea3$fFreeAlgebraTreeFreeMonoida$fMultiplicativeFreeMonoid$fFreeAlgebraTreeBaga$fSubtractiveBag $fAdditiveBag $fIsListBag$fFreeAlgebraExpExpa$fFreeAlgebraExpFreeRinga$fSubtractiveFreeRing$fAdditiveFreeRing$fMultiplicativeFreeRing$fExceptionBadExpParse$fEqTree $fOrdTree $fShowTree $fFunctorTree $fEqExample $fOrdExample$fAssociativeExample$fCommutativeExample$fIdempotentExample $fEqTreeU $fOrdTreeU $fShowTreeU$fFunctorTreeU $fEqTreeA $fShowTreeA$fFunctorTreeA$fEqFreeMonoid$fOrdFreeMonoid$fFoldableFreeMonoid$fShowFreeMonoid$fEqBag$fOrdBag $fShowBag$fEqExp$fOrdExp $fShowExp $fFunctorExp $fEqFreeRing $fOrdFreeRing$fShowFreeRing$fShowBadExpParsecontainers-0.6.0.1Data.Sequence.InternalSeqbagVbagRexpr