-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Numerical free algebras
--
-- The Free Num is a Sequence of Bags.
--
-- NumHask.FreeAlgebra explains.
--
-- But when we really delve into the reasons for why we can't let
-- something go, there are only two: an attachment to the past or a fear
-- for the future. ~ Marie Kondo
@package numhask-free
@version 0.0.2
-- | A Free Num is a Sequence of Bags.
--
-- One of the many things that sparks joy in Haskell is the density of
-- expression that can be achieved. If it wasn't for a few quirks of the
-- language, and if Ring is substituted for Num, a free
-- ring could be concretely defined as Free (Compose
-- Bag Seq) a.
--
-- As it stands, the library associates a free algebra with a forgetful
-- functor representing what could be thought of as a robust set of
-- polymorphic fusion rules. There are a lot of things that are
-- number-like computations, and some of them need to go very fast and be
-- very clean.
--
-- I had often heard about a free monoid and had always wondered what
-- else, other than the iconic Haskell list, is a free thing. This
-- library is a rough map of what has been a somewhat shambolic
-- exploration of this notion. I hope you enjoy browsing the haddocks as
-- much as I enjoyed crafting them. Before diving into the module proper,
-- there is a few landmarks worth noting:
--
--
-- - What, exactly, is a Num?
-- - What is an algebra?
-- - The forgotten price that must be paid for an object to be
-- free.
-- - The magic in category theory.
--
--
-- What is a Num?
--
-- Can you truthfully say that you treasure something buried so deeply
-- in a closet or drawer that you have forgotten its existence? If things
-- had feelings, they would certainly not be happy. Free them from the
-- prison to which you have relegated them. Help them leave that deserted
-- isle to which you have exiled them. ~ Marie Kondo
--
-- Num is a dusty, old corner of our Haskell shelf-space. As is
-- usually the case, the exact definition of what a Num is is only
-- ever a λ> :i away.
--
--
-- >>> :i Num
-- type Num :: * -> Constraint
-- class Num a where
-- (GHC.Num.+) :: a -> a -> a
-- (GHC.Num.-) :: a -> a -> a
-- (GHC.Num.*) :: a -> a -> a
-- GHC.Num.negate :: a -> a
-- GHC.Num.abs :: a -> a
-- signum :: a -> a
-- GHC.Num.fromInteger :: Integer -> a
-- ...
--
--
-- So Num is a Haskell class with an interface unchanged since
-- it's specification in the haskell98 standard.
--
-- The other, obvious answer to the question is that a Num is a
-- number; it says so in the name, after all. But, by convention, a
-- Haskell class is more than just the polymorphic type (the a) and the
-- operators (the class interface). By convention, a Haskell class is
-- also a set of laws that the class is expected to adhere to.
--
-- The commentary added since haskell98 mentions the mathematical concept
-- of a ring but there are a few warts:
--
--
-- - zero and one are not included in the interface, but
-- defined via fromInteger, a special function baked into
-- the Haskell language.
-- - abs and signum are not properties of a ring, but of metric
-- analytic branches of math.
--
--
-- The end result is that any notion of a free object applied to a
-- Num is difficult to imagine. If the interface is cleaned up,
-- however, as in Ring from the numhask library, with
-- attention paid to each and every law, then resolution improves, and we
-- are able to sharpen our tools.
--
-- A better definition of what our number systems are can lead to
-- cleaner, faster coding patterns and design. In turn, this might
-- eventually lead to ubiquitous usage of Haskell in numerical computing.
-- As it stands right now, Haskell usage is restricted to only the most
-- stubborn and dreamy of the numeric-analyst crew to which I claim
-- membership of.
--
-- This article-module is, in part, a plea to release the Haskell
-- numerical classes from their existing dusty drawers so we can begin to
-- imagine some sort of future of numerical computation within the halls
-- proper of Haskell. With apologies to Marie Kondo (and unsupported
-- strikeout):
--
-- The prelude (space) within which we code (live) should
-- be for the language (person) we are becoming now, not for the
-- language (person) we were in the past.
--
-- and
--
-- Imagine what it would be like to have a prelude (bookshelf)
-- filled only with functions (books) that you really love. Isn’t
-- that image spellbinding? For someone who loves functions
-- (books), what greater happiness could there be?
--
-- What is an algebra?
--
-- Art is fire plus algebra. ~ Jorge Luis Borges
--
-- or, less succinctly,
--
-- An algebra is a collection of operations which combine values to
-- produce other values. Algebra is a posh way of saying "construction
-- kit". The type of values an algebra combines and produces is called
-- the carrier of the algebra. The collection of operations and
-- specification of their arities is called the signature of the
-- algebra. ~ pigworker reddit comment
--
-- A free algebra then, is a set of instructions for creating a free
-- object from some initial structure or expression. FreeAlgebra
-- can be thought of as a class for busting up a computation into two
-- parts:
--
--
-- - forget: a function that transforms a structure into a Free
-- Object representing an ideal given the (abstract) laws of the algebra
-- being defined, and
-- - algebra: a (concrete) algebra from the Free Object to the
-- carrier type (the type being produced).
--
--
-- The price of a free object is forgetting.
--
-- Maybe if I forgot things once in a while, we'd all be a little bit
-- happier. ~ Jay Asher, Thirteen Reasons Why
--
-- A free object is neither "free as in beer" nor "free as in
-- speech". It is free as in absent the algebraic laws that refer to how
-- the object is constructed. At the heart of what is the free object,
-- the free part of the FreeAlgebra initial free type,
-- is a forgetting that throws away the structural details of the very
-- laws the free object defines.
--
-- A free object over a set forgets everything about that set except
-- some universal properties, specified by the word following free. For
-- example, the free monoid over Integers forgets unique factorization,
-- unique representation in every base, the GCD function, and everything
-- else about the Integers except: they are a set of objects, there is an
-- associative (binary) operation on Integers, and there is a "neutral"
-- Integer; precisely the universal properties of monoids. ~
-- https://www.schoolofhaskell.com/user/bss/magma-tree
--
-- ... informally, a free object over a set A can be thought of as
-- being a "generic" algebraic structure over A: the only equations that
-- hold between elements of the free object are those that follow from
-- the defining axioms of the algebraic structure. ~
-- https://en.wikipedia.org/wiki/Free_object
--
-- Adding a law to an algebra can be thought of as partitioning the
-- carrier of the algebra into equivalence classes induced by that law,
-- and regarding each class as one element. ~ The Boom
-- Hierarchy
--
-- As is becoming well known, the easiest way to ensure that laws are
-- never violated is by making their transgression non-representable.
-- FreeAlgebra represents a technique for achieving this necessary
-- step in constructing a free object from an initial representation.
--
-- The magic in category theory
--
-- Essentially everything that makes category theory nontrivial and
-- interesting ... can be derived from the concept of adjoint
-- functors. ~ nLabs
--
-- What makes the above statement so interesting is when you combine it
-- with their definition of adjunction (the noun to the "adjoint"
-- adverb):
--
-- adjunction : free functor ⊣ forgetful functor ~ nLabs
--
-- That's it! That's as far as they are prepared to discuss things,
-- cascading definitions notwithstanding.
--
-- There's something very 17th century medicine about 21st century
-- category theory. "An overabundance of the yellow humours can be fixed
-- by an application of leeches" is how I hear much category theoretic
-- prescription. We simply don't yet know enough about applied category
-- theory for it to be distinguishable from magic.
--
-- Which leaves room for amateurs such as myself to do some
-- hack-and-slash exploring. I can take a leap and see adjunctiveness (or
-- is it adjointanality?) as yet another metaphor for this deep dual
-- nature of programming. That is, for every way of considering a
-- problem, you can "flip the switch" and think about it in an opposite,
-- orthogonal, adjacent or flippin' arrow perspective or context.
--
-- With respect to a FreeAlgebra, the flipped switch is this:
--
-- To arrive at a Free Object (where the only thing that is left are
-- the laws under consideration), you need to forget the very laws
-- encapsulated in the free structure and remember everything else.
--
-- this functor “forgets” the monoidal structure — once we are inside
-- a plain set, we no longer distinguish the unit element or care about
-- multiplication — it’s called a forgetful functor. ~
-- https://bartoszmilewski.com/2015/07/21/free-monoids/
--
-- Future breakthroughs will not be found in quantum theory, mired in the
-- 20th century slide-rules of physics. They will not be gained by
-- applying bio-logic-al constructs to computers with convoluted neural
-- nets and tautological machine learnings. They will certainly never
-- occur within a context of computer science as linguistic endeavour.
-- The future can be seen now, however opaquely and paradoxical, and will
-- be shaped by the binary oppositions and sheer post-modernist
-- confusions of category theory.
module NumHask.FreeAlgebra
-- | A free algebra is a construction kit of operations and axioms that
-- combine to produce values of a type.
class FreeAlgebra initial free a | free -> initial
-- | Convert from a structure (the initial type) to another structure, the
-- free object, forgetting the algebraic laws encapsulated in the free
-- object definition.
forget :: FreeAlgebra initial free a => initial a -> free a
-- | Create a free object from a carrier type singleton.
lift :: FreeAlgebra initial free a => a -> free a
-- | The algebra of the free object.
--
--
-- lift . algebra == id
--
algebra :: FreeAlgebra initial free a => free a -> a
-- | Pretty print the free object.
printf :: FreeAlgebra initial free a => free a -> Text
-- | 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 differing instances.
data NoLaws
-- | A 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 Example
--
-- >>> putStrLn $ printf m1
-- ((1⊕4)⊕((7⊕12)⊕0))
--
data Tree laws a
Leaf :: a -> Tree laws a
Branch :: Tree laws a -> Tree laws a -> Tree laws a
-- | Convenience function to construct a Tree from a list with left bracket
-- groupings.
--
--
-- >>> toTreeL [1,4,7,12,0]
-- Branch (Branch (Branch (Branch (Leaf 1) (Leaf 4)) (Leaf 7)) (Leaf 12)) (Leaf 0)
--
toTreeL :: NonEmpty a -> Tree NoLaws a
-- | Construct a Tree from a list with a right bracket groupings.
--
--
-- >>> toTreeR [1,4,7,12,0]
-- Branch (Leaf 1) (Branch (Leaf 4) (Branch (Leaf 7) (Branch (Leaf 12) (Leaf 0))))
--
toTreeR :: NonEmpty a -> Tree NoLaws a
-- | 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.
data Exp a
Value :: a -> Exp a
Add :: Exp a -> Exp a -> Exp a
Mult :: Exp a -> Exp a -> Exp a
-- | Text 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)))
parseExp :: Text -> Exp Int
-- | Parse an Exp, forget to the free object structure and print.
--
--
-- >>> let t1 = "(4*(1+3)+(3+1)+6*(4+5*(11+6)*(3+2)))+(7+3+11*2)"
--
-- >>> putStrLn $ freeExp t1
-- (1+3+3+7+(4*(1+3))+(6*(4+(5*(6+11)*(2+3))))+(11*2))
--
freeExp :: Text -> Text
-- | Free Algebra for a Magma
--
--
-- a ⊕ b is closed
--
--
-- Given an initial binary Tree structure:
--
--
-- data Tree a = Leaf a | Branch (Tree a) (Tree a)
--
--
-- , a closed binary operation (a magma) and no other laws, the free
-- algebra is also a Tree.
--
--
-- >>> let init = toTreeL $ Example <$> [1,4,7,12,0] :: Tree NoLaws Example
--
-- >>> let free = forget init :: Tree MagmaOnly Example
--
-- >>> putStrLn $ printf $ free
-- ((((1⊕4)⊕7)⊕12)⊕0)
--
--
--
-- >>> algebra free
-- 24
--
data MagmaOnly
-- |
-- unit ⊕ a = a
-- a ⊕ unit = a
--
data UnitalOnly
-- | The introduction of unital laws to the algebra changes what the free
-- structure is, compared to the MagmaOnly 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.
--
-- An 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.
--
--
-- >>> let init = toTreeL $ Example <$> [0,1,4,0,7,12,0] :: Tree NoLaws Example
--
-- >>> putStrLn $ printf $ (forget init :: TreeU UnitalOnly Example)
-- (((1⊕4)⊕7)⊕12)
--
data TreeU laws a
EmptyTree :: TreeU laws a
NonEmptyTree :: Tree MagmaOnly a -> TreeU laws a
-- |
-- (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)
--
data AssociativeOnly
-- | 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.
--
-- forget, 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]
--
-- >>> putStrLn $ printf (forget exl :: Tree MagmaOnly Example)
-- ((((1⊕4)⊕7)⊕12)⊕0)
--
--
--
-- >>> let exr = toTreeR $ Example <$> [1,4,7,12,0]
--
-- >>> putStrLn $ 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
--
data TreeA laws a
LeafA :: a -> TreeA laws a
BranchA :: a -> TreeA laws a -> TreeA laws a
-- |
-- a ⊕ b == b ⊕ a
--
--
-- but non-associative, so
--
--
-- (a ⊕ b) ⊕ c == (b ⊕ a) ⊕ c
--
--
-- but
--
--
-- (a ⊕ b) ⊕ c /= a ⊕ (b ⊕ c)
--
--
-- Commutation requires a ⊕ b and b ⊕ a to be represented the same, and
-- this induces a preordering: some 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) ⊕ 3
--
--
-- >>> let c1 = forget $ Branch (Leaf (Example 3)) (Branch (Leaf (Example 2)) (Leaf (Example 1))) :: Tree CommutativeOnly Example
--
-- >>> let c2 = forget $ Branch (Leaf (Example 3)) (Branch (Leaf (Example 1)) (Leaf (Example 2))) :: Tree CommutativeOnly Example
--
-- >>> let c3 = forget $ Branch (Branch (Leaf (Example 1)) (Leaf (Example 2))) (Leaf (Example 3)) :: Tree CommutativeOnly Example
--
--
--
-- >>> c1 == c2
-- True
--
--
--
-- >>> c1 == c3
-- True
--
data CommutativeOnly
-- |
-- inv a ⊕ (a ⊕ b) == b -- left cancellation
-- (a ⊕ b) ⊕ inv b == a -- right cancellation
--
--
-- but
--
--
-- 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.
--
-- The data structure for the equivalence class is unchanged, so Tree can
-- be reused.
--
-- inv1: -1 ⊕ (1 ⊕ 5) == 5
--
-- inv2: (1 ⊕ 5) ⊕ -5 == 1
--
-- inv3: (1 ⊕ 5) ⊕ -1 == (1 ⊕ 5) ⊕ -1
--
--
-- >>> let inv1 = Branch (Leaf (Example (-1))) (Branch (Leaf (Example 1)) (Leaf (Example 5)))
--
-- >>> let inv2 = Branch (Branch (Leaf (Example 1)) (Leaf (Example 5))) (Leaf (Example (-5)))
--
-- >>> let inv3 = Branch (Branch (Leaf (Example 1)) (Leaf (Example 5))) (Leaf ((Example (-1))))
--
-- >>> forget inv1 :: Tree InvertibleOnly Example
-- Leaf 5
--
--
--
-- >>> putStrLn $ printf $ (forget inv3 :: Tree InvertibleOnly Example)
-- ((1⊕5)⊕-1)
--
data InvertibleOnly
-- |
-- a ⊕ a = a
--
--
-- Immediately 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.
--
--
-- >>> let idem1 = Branch (Branch (Leaf (Example 5)) (Leaf (Example 5))) (Leaf (Example 1))
--
-- >>> let idem2 = Branch (Branch (Leaf (Example 1)) (Leaf (Example 5))) (Branch (Leaf (Example 1)) (Leaf (Example 5)))
--
-- >>> let 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)
--
--
--
-- >>> algebra (forget idem3 :: Tree IdempotentOnly Example)
-- 5
--
data IdempotentOnly
-- |
-- e ⊕ a == e left absorbing
-- a ⊕ e == e right absorbing
--
--
-- The absorbed element is forgotten.
--
-- ab1: 0 * (2 * 5) == 0
--
-- ab2: (2 * 5) * 0 == 0
--
--
-- >>> let ab1 = Branch (Leaf (Example 0)) (Branch (Leaf (Example 2)) (Leaf (Example 5)))
--
-- >>> let ab2 = Branch (Branch (Leaf (Example 2)) (Leaf (Example 5))) (Leaf (Example 0))
--
-- >>> forget ab1 :: Tree AbsorbingOnly Example
-- Leaf 0
--
--
--
-- >>> forget ab2 :: Tree AbsorbingOnly Example
-- Leaf 0
--
data AbsorbingOnly
-- | The 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:
--
--
-- - forgetting 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)
--
--
-- We graft on a sum tag to represent an empty structure:
--
--
-- data Tree a = EmptyTree | Leaf a | Branch (Tree a) (Tree a)
--
--
-- To forget 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:
--
--
-- data Tree a = EmptyTree | Leaf a | Branch a (Tree a)
--
--
-- Leaf a can be represented as Branch a EmptyTree, so we can simplify
-- this to:
--
--
-- data Tree a = EmptyTree | Branch a (Tree a)
--
--
-- And this is the classical Haskell cons list with different names:
--
--
-- data [] a = [] | a : [a]
--
newtype FreeMonoid laws a
FreeMonoid :: [a] -> FreeMonoid laws a
[leaves] :: FreeMonoid laws a -> [a]
-- | Multiplicative monoid laws
--
--
-- a * b is closed
-- one * a = a
-- a * one = a
-- (a * b) * c = a * (b * c)
--
--
--
-- >>> one :: FreeMonoid MultMonoid Int
-- FreeMonoid {leaves = []}
--
--
-- ex1: (1 * 2) * (4 * 5) * 1
--
--
-- >>> let 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)
--
--
--
-- >>> algebra (forget ex1 :: FreeMonoid MultMonoid Int)
-- 40
--
data MultMonoid
-- | 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.
newtype Bag laws a
Bag :: Map a Int -> Bag laws a
[unbag] :: Bag laws a -> Map a Int
-- | This is a functor from Ord -> Ord but, sadly, not a functor from
-- Hask -> Hask
mapBag :: Ord b => (a -> b) -> Bag laws a -> Bag laws b
-- | Additive Commutative Group 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
--
--
-- 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 Int
--
-- >>> exbag
-- Bag {unbag = fromList [(3,1),(4,-1)]}
--
--
--
-- >>> toList exbag
-- [3,-4]
--
--
--
-- >>> exAdd = toTreeL [0,1,2,3,0,-1,-4,-2,0]
--
-- >>> putStrLn $ printf (forget exAdd :: Bag AddCommGroup Int)
-- (3+-4)
--
data AddCommGroup
-- | 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)
--
data RingLaws
-- | The free ring is a recursive sequence of bags.
--
-- Given 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.
--
-- Abstractly, 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.
--
-- Because the distribution laws are substitutions to both the left and
-- the right, use of Seq is indicated instead of a list (which is
-- isomorphic to a list and thus allowed as an alternative).
--
-- The free ring is the same general shape as the free monad in the
-- free library
--
--
-- data Free f a = Pure a | Free (f (Free f a))
--
--
-- which in turn is almost the same shape as Fix eg
--
--
-- newtype Fix f = Fix (f (Fix f))
--
--
-- If Bag could form a Functor instance, then the Free Ring could be
-- expressed as Free (Compose Bag Seq)
-- a
--
-- which is a very clean result.
data FreeRing laws a
FreeV :: a -> FreeRing laws a
FreeR :: Seq (Bag AddCommGroup (FreeRing laws a)) -> FreeRing laws a
-- | example type
newtype Example
Example :: Int -> Example
-- | informal test suite
--
-- empty expression
--
--
-- >>> freeExp "0"
-- "0"
--
--
-- plain (with multiplicative precedence)
--
--
-- >>> forget $ 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 unital
--
--
-- >>> freeExp "0+(2+0)*3+0"
-- "(2*3)"
--
--
-- General additive associative and commutation
--
--
-- >>> freeExp "(1+2)*3+(4+5)+6*7"
-- "(4+5+((1+2)*3)+(6*7))"
--
--
-- Multiplicative unital
--
--
-- >>> freeExp "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)"
--
--
-- absorptive
--
--
-- >>> freeExp "0*1+3*(3+4)*0"
-- "0"
--
--
-- additive invertible
--
--
-- >>> freeExp "(1+2)+(-1+-2)"
-- "0"
--
--
-- distribution
--
--
-- a ⋅ (b + c) = (a · b) + (a · c)
-- (b + c) · a = (b · a) + (c · a)
--
--
-- left
--
--
-- >>> freeExp "2*(3+4)+2*5+2*6"
-- "(2*(3+4+5+6))"
--
--
-- right
--
--
-- >>> freeExp "(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)"
--
--
-- Note that (2*(3+4+6)*2+5*2) is a valid alternative to what
-- the current FreeRing forget function comes up with.
--
-- TODO: optional extras:
--
--
-- - If +one is faster than +a
--
--
--
-- (a . b) + a ==> a . (b + one)
--
--
--
--
-- lifting an (additive bag) to a multiplication sequence
--
--
-- 3+3+3+3 ==> 3*4
--
--
--
-- - introducing exponents
--
--
--
-- 3*3*3*3 ==> 3^4
--
data InformalTests
-- | intercalate elements of an expression with an operator, and put
-- brackets around this.
calate :: Text -> [Text] -> Text
instance GHC.Base.Functor (NumHask.FreeAlgebra.Tree laws)
instance GHC.Show.Show a => GHC.Show.Show (NumHask.FreeAlgebra.Tree laws a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (NumHask.FreeAlgebra.Tree laws a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (NumHask.FreeAlgebra.Tree laws a)
instance NumHask.Algebra.Group.Idempotent NumHask.FreeAlgebra.Example
instance NumHask.Algebra.Group.Commutative NumHask.FreeAlgebra.Example
instance NumHask.Algebra.Group.Associative NumHask.FreeAlgebra.Example
instance GHC.Classes.Ord NumHask.FreeAlgebra.Example
instance GHC.Classes.Eq NumHask.FreeAlgebra.Example
instance GHC.Base.Functor (NumHask.FreeAlgebra.TreeU laws)
instance GHC.Show.Show a => GHC.Show.Show (NumHask.FreeAlgebra.TreeU laws a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (NumHask.FreeAlgebra.TreeU laws a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (NumHask.FreeAlgebra.TreeU laws a)
instance GHC.Base.Functor (NumHask.FreeAlgebra.TreeA laws)
instance GHC.Show.Show a => GHC.Show.Show (NumHask.FreeAlgebra.TreeA laws a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (NumHask.FreeAlgebra.TreeA laws a)
instance GHC.Show.Show a => GHC.Show.Show (NumHask.FreeAlgebra.FreeMonoid laws a)
instance Data.Foldable.Foldable (NumHask.FreeAlgebra.FreeMonoid laws)
instance GHC.Classes.Ord a => GHC.Classes.Ord (NumHask.FreeAlgebra.FreeMonoid laws a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (NumHask.FreeAlgebra.FreeMonoid laws a)
instance GHC.Show.Show a => GHC.Show.Show (NumHask.FreeAlgebra.Bag laws a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (NumHask.FreeAlgebra.Bag laws a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (NumHask.FreeAlgebra.Bag laws a)
instance GHC.Base.Functor NumHask.FreeAlgebra.Exp
instance GHC.Show.Show a => GHC.Show.Show (NumHask.FreeAlgebra.Exp a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (NumHask.FreeAlgebra.Exp a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (NumHask.FreeAlgebra.Exp a)
instance GHC.Show.Show a => GHC.Show.Show (NumHask.FreeAlgebra.FreeRing laws a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (NumHask.FreeAlgebra.FreeRing laws a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (NumHask.FreeAlgebra.FreeRing laws a)
instance GHC.Show.Show NumHask.FreeAlgebra.BadExpParse
instance GHC.Exception.Type.Exception NumHask.FreeAlgebra.BadExpParse
instance (GHC.Classes.Eq a, GHC.Classes.Ord a, NumHask.Algebra.Additive.Subtractive a, NumHask.Algebra.Multiplicative.Multiplicative a) => NumHask.Algebra.Multiplicative.Multiplicative (NumHask.FreeAlgebra.FreeRing NumHask.FreeAlgebra.RingLaws a)
instance (GHC.Classes.Ord a, NumHask.Algebra.Ring.Ring a) => NumHask.Algebra.Additive.Additive (NumHask.FreeAlgebra.FreeRing NumHask.FreeAlgebra.RingLaws a)
instance (GHC.Show.Show a, GHC.Classes.Ord a, NumHask.Algebra.Ring.Ring a) => NumHask.Algebra.Additive.Subtractive (NumHask.FreeAlgebra.FreeRing NumHask.FreeAlgebra.RingLaws a)
instance (GHC.Show.Show a, GHC.Classes.Eq a, GHC.Classes.Ord a, NumHask.Algebra.Ring.Ring a) => NumHask.FreeAlgebra.FreeAlgebra NumHask.FreeAlgebra.Exp (NumHask.FreeAlgebra.FreeRing NumHask.FreeAlgebra.RingLaws) a
instance (GHC.Show.Show a, GHC.Classes.Eq a, NumHask.Algebra.Ring.Ring a, NumHask.Algebra.Group.Magma a) => NumHask.FreeAlgebra.FreeAlgebra NumHask.FreeAlgebra.Exp NumHask.FreeAlgebra.Exp a
instance (GHC.Classes.Ord a, NumHask.Algebra.Additive.Subtractive a) => GHC.Exts.IsList (NumHask.FreeAlgebra.Bag NumHask.FreeAlgebra.AddCommGroup a)
instance GHC.Classes.Ord a => NumHask.Algebra.Additive.Additive (NumHask.FreeAlgebra.Bag NumHask.FreeAlgebra.AddCommGroup a)
instance GHC.Classes.Ord a => NumHask.Algebra.Additive.Subtractive (NumHask.FreeAlgebra.Bag NumHask.FreeAlgebra.AddCommGroup a)
instance (GHC.Show.Show a, GHC.Classes.Eq a, GHC.Classes.Ord a, NumHask.Algebra.Additive.Subtractive a) => NumHask.FreeAlgebra.FreeAlgebra (NumHask.FreeAlgebra.Tree NumHask.FreeAlgebra.NoLaws) (NumHask.FreeAlgebra.Bag NumHask.FreeAlgebra.AddCommGroup) a
instance NumHask.Algebra.Multiplicative.Multiplicative (NumHask.FreeAlgebra.FreeMonoid NumHask.FreeAlgebra.MultMonoid a)
instance (GHC.Show.Show a, GHC.Classes.Eq a, NumHask.Algebra.Multiplicative.Multiplicative a) => NumHask.FreeAlgebra.FreeAlgebra (NumHask.FreeAlgebra.Tree NumHask.FreeAlgebra.NoLaws) (NumHask.FreeAlgebra.FreeMonoid NumHask.FreeAlgebra.MultMonoid) a
instance (GHC.Show.Show a, GHC.Classes.Eq a, NumHask.Algebra.Group.Absorbing a) => NumHask.FreeAlgebra.FreeAlgebra (NumHask.FreeAlgebra.Tree NumHask.FreeAlgebra.NoLaws) (NumHask.FreeAlgebra.Tree NumHask.FreeAlgebra.AbsorbingOnly) a
instance (GHC.Show.Show a, GHC.Classes.Ord a) => NumHask.FreeAlgebra.FreeAlgebra (NumHask.FreeAlgebra.Tree NumHask.FreeAlgebra.NoLaws) (NumHask.FreeAlgebra.Tree NumHask.FreeAlgebra.IdempotentOnly) a
instance (GHC.Show.Show a, GHC.Classes.Eq a, NumHask.Algebra.Group.Invertible a) => NumHask.FreeAlgebra.FreeAlgebra (NumHask.FreeAlgebra.Tree NumHask.FreeAlgebra.NoLaws) (NumHask.FreeAlgebra.Tree NumHask.FreeAlgebra.InvertibleOnly) a
instance (GHC.Show.Show a, GHC.Classes.Ord a, NumHask.Algebra.Group.Commutative a) => NumHask.FreeAlgebra.FreeAlgebra (NumHask.FreeAlgebra.Tree NumHask.FreeAlgebra.NoLaws) (NumHask.FreeAlgebra.Tree NumHask.FreeAlgebra.CommutativeOnly) a
instance (GHC.Show.Show a, NumHask.Algebra.Group.Associative a) => NumHask.FreeAlgebra.FreeAlgebra (NumHask.FreeAlgebra.Tree NumHask.FreeAlgebra.NoLaws) (NumHask.FreeAlgebra.TreeA NumHask.FreeAlgebra.AssociativeOnly) a
instance (GHC.Classes.Eq a, GHC.Show.Show a, NumHask.Algebra.Group.Unital a) => NumHask.FreeAlgebra.FreeAlgebra (NumHask.FreeAlgebra.Tree NumHask.FreeAlgebra.NoLaws) (NumHask.FreeAlgebra.TreeU NumHask.FreeAlgebra.UnitalOnly) a
instance (GHC.Show.Show a, NumHask.Algebra.Group.Magma a) => NumHask.FreeAlgebra.FreeAlgebra (NumHask.FreeAlgebra.Tree NumHask.FreeAlgebra.NoLaws) (NumHask.FreeAlgebra.Tree NumHask.FreeAlgebra.MagmaOnly) a
instance NumHask.Algebra.Group.Magma NumHask.FreeAlgebra.Example
instance NumHask.Algebra.Group.Unital NumHask.FreeAlgebra.Example
instance NumHask.Algebra.Group.Absorbing NumHask.FreeAlgebra.Example
instance NumHask.Algebra.Group.Invertible NumHask.FreeAlgebra.Example
instance GHC.Show.Show NumHask.FreeAlgebra.Example