I "<" monoid did

Some time ago in one cozy chamber meeting I made a report on its development — scripting language lipoptena Liscript. Started with the basics semantics the computation of the lists, prefix notation... Reached the standard of arbitrary arity operations:

the

+ 1 2 3
=> 6

everything is intuitive, questions arise. Talk about Boolean values here is an example:

the

< 1 2
=> true

all too clear. And then the question from the audience: "and if 3 arguments to tell you how to calculate?" I think it's a good excuse to show off smart terms, and the answer is: "exactly the same as a convolution in the monoid" :) And then while recuperating — "although the comparison is not a monoid", write for example:

the

< 1 2 3
=> true
< 1 2 3 4 1 2
=> false

Still, it is intuitively clear, questions arise and continue (wisely leaving without consideration of the calculation of primitive operations on one argument and generally in the absence thereof, and subtraction/division and other demonically operations :)). Successfully passing the report of such stones, after a while, I thought — is it possible somehow to contrive, and still do the comparison operation is a monoid (in any sense)? And I think I succeeded. Interested please under cat.

the

Introduction about monoids for the kids

As is well known, monoid is called an associative binary operation on the given set with the neutral element. Means for determining the monoid we need to ask 3 things:

the

the
• many defining our mission
the
• the operation itself with the associativity
the
• the neutral element (of videopreteen set)

Brush up on the terms "neutral" and "associative". Let our binary operation mappend, neutral mempty (to make it easier to read koscelny cat and to latex in the markdown not to pull), then the neutral element defined as:

the

mappend x mempty = x
mappend x mempty = x

what can be transferred to the fingers as if one of the operands of our operations is a neutral element, the result of the operation is the second operand, in other words the neutral element does not change the result. Associativity is defined as:

the

mappend x (mappend y z) = mappend (mappend x y) z

That is, when computing the composition of two (and, as a consequence, an arbitrary number) operations, the result does not depend on the order of calculations, or, in other words, no matter how you put parentheses in a long expression (and therefore can generally be omitted).

Generally speaking, a monoid is a rather General notion of abstract algebra and category theory (because it is widely known that even those the monad is monoids by definition), but in this article we are not going to dive deeply into theoretical aspects. Let's start with a couple simple examples: the addition operation on the set of integers (or natural/real/complex) numbers. Associativity is present as a neutral element to take 0 from a given set. The multiplication operation is also a monoid, with neutral element 1. Another example is the operation of concatenation on multiple lines, with neutral element the empty string. Also all the laws of the monoid are performed, although the operation of concatenation is not commutative — but this is not required. The implementation of monoids addition/multiplication in Haskell is trivial:

the

newtype Sum a = Sum a deriving (Eq, Ord, Show)

instance Num a = > Monoid (Sum a) where
mempty = Sum 0
mappend (Sum x) (Sum y) = Sum $ x + y


newtype Product a = Product a deriving (Eq, Ord, Show)

instance Num a = > Monoid (Product a) where
mempty = Product 1
mappend (Product x) (Product y) = Product $ x * y

Here we actually define a concrete implementation of mempty and mappend the rules described above. Class Monoid automatically gives us the convolution operation mconcat any container (list, tree, — of any, which defined the operation of convolution) for any monoid: the case of the list — we start with the neutral element of mempty as the result of the convolution and go sequentially through the list, updating the result in our monoidal binary operation mappend with the current element of the list. For example, a numeric list, it's the convolution monoid Sum will give us the sum of the elements of the list, and the Product is a work. Exactly the same remarks apply design:
the

+ 4 5 6 7
=> 22
* 2 3 4 5
=> 120

In Lisp (leaving aside the question of the calculation of no arguments). Check haskeline implementation:

the

*MyMonoid> mconcat $ map Sum []
Sum 0
*MyMonoid> mconcat $ map Sum [1..10]
Sum 55
*MyMonoid> mconcat $ map Product []
Product 1
*MyMonoid> mconcat $ map Product [1..10]
Product 3628800

As you can see, it works.

the

Operation minimum

Now take the example a little more interesting — the binary operation of at least a numeric set. Is it a monoid? The operation is associative, multiple set. The only problem is the definition of neutral element. We need this element in our set, which was not less than any other element. If this is an accurate top face (e.g., uint8 has a maximum value of 255), then we can take this value as the neutral element of our monoid. But if we type unlimited integers? The solution is quite simple — we expand our type another special value (let's call it "plus infinity") and we define the operation so as to fulfill the laws.

Implement this in your code and check for empty and non-empty lists

the

data Min a =
HighInf -- the neutral element of the monoid (+ infinity)
| Min -- a Packed value
deriving (Eq, Ord, Show)

instance Ord a = > Monoid (Min a) where
mempty = HighInf

mappend HighInf v = v
mappend HighInf v = v
mappend (Min x) (Min y) = Min $ min x y

*MyMonoid> mconcat $ map Min []
HighInf
*MyMonoid> mconcat $ map Min [5..10]
5 Min

All as expected — at least on an empty list gives plus infinity, to a non-empty, the minimum element.

the

compare

We now turn to the final goal, try to implement monoid for comparison operations. And immediately we have a problem — the comparison operation, in contrast to the previous discussed surgeries, is not an operation defined on a set. That is, the type of its result is Boolean, not type belongs to the numerous arguments on which it is defined. Is a binary predicate, not an operation. But, as always, we can solve this problem by introducing an additional level of abstraction (similar to how we did in the last example) it is necessary to construct such a type, to generalized comparison operation was defined on the set of this type. We also need a rule of transformation of the initial set values of this type and values of this type to a Boolean type. Thus, the generalized comparison as monoidal operation will look like this: we translate the list of source values in the value list for the type implemented by a convolution of this list via the monoidal operation, and then converting the result to a Boolean value — that is required from the compare operation.

Let's think about what values should provide this new type. We need a neutral element, with the implementation of the relevant laws. We need a value characterizing about the result of any comparison — if we in the convolution monoidal in the chain of operations comparison was found this value, we drags it to the end, ignoring the other comparisons. And we need a value characterizing the true result of the comparison. It must contain the value of our original type — for later comparisons. But as the following comparison can use it as on the left (from the symbol <) and right, we have enough of the same values — we want the extreme values of the processed range (minimum and maximum over the whole chain of comparisons). Thus, the value of our type will be a pair of 2 elements, specifying a collapsed range. Write an implementation of the monoid and for all official functions:

the

data Asc a =
EmptyAsc -- the neutral element of the monoid
| RangeAsc a a -- a range of values (comparison true)
| FailAsc -- the comparison is false

deriving (Eq, Ord, Show)

instance Ord a = > Monoid (a Asc) where
mempty = EmptyAsc

mappend EmptyAsc v = v
mappend EmptyAsc v = v

mappend FailAsc v = FailAsc
mappend v FailAsc = FailAsc

mappend (RangeAsc a b) (c RangeAsc d)
| b < c = RangeAsc a d
| otherwise = FailAsc


valToAsc x = RangeAsc x x

ascToBool FailAsc = False
ascToBool _ = True

and let's check our work:

the

*MyMonoid> mconcat $ map valToAsc []
EmptyAsc
*MyMonoid> mconcat $ map valToAsc [3,4,7,10]
RangeAsc 3 10
*MyMonoid> mconcat $ map valToAsc [1,2,3,4,1,2]
FailAsc
*MyMonoid> isAscList []
True
*MyMonoid> isAscList [1..10]
True
*MyMonoid> isAscList $ [1,2,3,4,1,2]
False

Everything works as required — our monoid checks order the list in ascending — that is exactly what makes the same design in Lisp. It is easy to write several similar monoids, checking the list for non-strict ascending order (operation soft comparison <=), decreasing (strict and nonstrict) and the equality of all elements of the list. To do this, simply replace the appropriate binary predicate in the definition of the function mappend.

the

the long Awaited conclusion

Now I'm relaxed — I did not deceive the listeners during the lecture :) the comparison Operation itself is not a monoid, but can introduce a level of abstraction in which its generalized analogue will be the same.

If you are interested — video report (stream on YouTube) Links to my github repository with the implementation of interpreters can be found in my previous articles on habré.

Article based on information from habrahabr.ru