How I did a "<" monoid

Some time ago, in one cozy chamber meeting, I gave a report on my development - a script lispodobnom language Liscript. He started with the basics - the semantics of calculating lists, prefix notation ... Reached arbitrary arity of standard operations:

+ 1 2 3 => 6 

Everything is intuitive, there are no questions. I tell about boolean values, I give an example:

 < 1 2 => true 

everything is clear too. And here is a question from the audience: “and if I pass 3 arguments, how will it be calculated?” I decide that this is a good reason to show off with clever terms, and I answer: “exactly the same way as a convolution according to a monoid” :) And then straightening out - “ although the comparison operation is not a monoid, ”I am writing an example:
')

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

It is still intuitively clear, there are no questions and we continue further (prudently leaving without consideration the calculation of primitive operations on one argument and generally in the absence of them, as well as subtraction / division and other non-monoidal operations :)). Having successfully passed through such stones in the report, after a while I thought - is it possible to somehow contrive, and still make the comparison operation a monoid (in some sense)? And I think I succeeded. Interested in a subject I ask under kat.

Intro about monoids for the smallest

As everyone is well aware, a monoid is an associative binary operation on a given set that has a neutral element. So, to define a monoid, we need to specify 3 things:

• the set on which our operation is defined
• associative operation itself
• neutral element (from the above defined set)

Let us recall the terms “neutral” and “associative”. We denote our binary operation mappend , the neutral element of mempty (so that later it would be easier to read a haskel cat and not to stretch latex on markaun), then the neutrality of the element is defined as:

 mappend mempty x = x mappend x mempty = x 

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

 mappend x (mappend yz) = mappend (mappend xy) z 

That is, when calculating a composition of two (and, as a result, an arbitrary number) operations, the result does not depend on the order of calculations, or, in other words, it does not matter how to put the brackets in a long expression (therefore, they can be omitted altogether).

Generally speaking, a monoid is a fairly general concept of abstract algebra and category theory (for it is widely known that even those monads are monoids by definition), but in this article we will not dive deep into theoretical aspects. Let's start with a couple of simple examples: the operation of addition on the set of whole (or natural / real / complex) numbers. Associativity is present, as a neutral element we take 0 from the given set. The multiplication operation is also a monoid, with a neutral element 1. Another example is the concatenation operation on a set of strings, with a neutral element in the form of an empty string. Also, all the laws of a monoid are satisfied, although the concatenation operation is not commutative - but this is not required. Implementing monoids of addition / multiplication in Haskell is trivial:

 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 defined specific implementations of mempty and mappend according to the rules described above. The monoid type class automatically provides us with the convolution operation mconcat of any container (list, tree — any that has a convolution operation) for any monoid: using the list as an example, we start with a neutral mempty element as a result of convolution and go sequentially through the list, updating the result through our monoidal binary operation mappend with the current list item. Using the example of a numeric list, convolving it by a monoid Sum will give us the sum of the elements of the list, and Product - the product. The constructions are calculated in exactly the same way:

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

In Lisp (leaving aside the question of calculation without arguments). Check for haskell implementations:

 *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, everything works.

Operation minimum

Now let's take an example more interesting - the binary operation of a minimum on a number set. Is she a monoid? The operation is associative, the set is given. The only problem is the definition of a neutral element. We need such an element in our set that would be no less than any other element. If our set has an exact upper bound (for example, the type uint8 has a maximum value of 255), then we can take this value as a neutral element of our monoid. But if we have the type of unlimited integers? The solution is quite simple - we expand our type with one more special value (let's call it “plus infinity”) and define the operation so that the laws are fulfilled.

Implement it in code and check on empty and non-empty lists.

 data Min a = HighInf --    (+ ) | Min a --   deriving (Eq, Ord, Show) instance Ord a => Monoid (Min a) where mempty = HighInf mappend HighInf v = v mappend v HighInf = v mappend (Min x) (Min y) = Min $ min xy *MyMonoid> mconcat $ map Min [] HighInf *MyMonoid> mconcat $ map Min [5..10] Min 5 

Everything is as expected - the minimum on the empty list gives plus infinity, on a non-empty one - the minimum element.

Comparison operation

We now turn to the final goal - we will try to implement a monoid for the comparison operation. And immediately we have a problem - the comparison operation, unlike the previous operations considered, is not an operation defined on the set. That is, the type of its result is boolean, and does not belong to the type of the set of its arguments on which it is defined. This is a binary predicate, not an operation. But, as always, we can solve this problem by introducing an additional level of abstraction (similar to what we did in the last example with a minimum): we need to construct such a type so that the generalized comparison operation is defined on the set of this type. We also need a rule for transforming the values ​​of the original set into this type and the values ​​of this type into a Boolean type. Thus, a generalized comparison as a monoidal operation will look like this: we translate the list of source values ​​into a list of values ​​of our type, perform a convolution of this list by a monoidal operation, and then translate the result into a boolean value — as required from the comparison operation.

Let's think about what values ​​this new type should provide. We need the value of a neutral element, with the implementation of the relevant laws. We need a value that characterizes a false result of any comparison — if we have met this value in the chain of monoidal comparison operations when convolving, we drag it to the end, ignoring other comparisons. And we need a value that characterizes the true result of the comparison. It should contain the value of our original type - for subsequent comparisons. But since subsequent comparisons can use it both on the left (from the conventional sign <) and on the right, one value is not enough for us - we need extreme values ​​of the processed range (minimum and maximum for the whole chain of comparisons). Thus, the value of our type will be a pair of 2 elements that defines the collapsed range. We write the implementation of the monoid and all service functions:

 data Asc a = EmptyAsc --    | RangeAsc aa --   ( ) | FailAsc --   deriving (Eq, Ord, Show) instance Ord a => Monoid (Asc a) where mempty = EmptyAsc mappend EmptyAsc v = v mappend v EmptyAsc = v mappend FailAsc v = FailAsc mappend v FailAsc = FailAsc mappend (RangeAsc ab) (RangeAsc cd) | b < c = RangeAsc ad | otherwise = FailAsc valToAsc x = RangeAsc xx ascToBool FailAsc = False ascToBool _ = True 

and check the work:

 *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 it is required - our monoid checks the orderliness of the list in ascending order — that is, exactly what the similar construction does in lispahs. It is easy to write a few more similar monoids that check the list for a non-strict increase (on the non-strict comparison operation <=), a decrease (strict and non-strict), and the equality of all the elements of the list. To do this, it suffices to replace the corresponding binary predicate in the definition of the mappend function.

Long awaited conclusion

Now I am calm - I did not deceive the listeners during the report :) The comparison operation itself is not a monoid, but you can enter a level of abstraction, in which its generalized analogue will be one.

If anyone is interested - a video report (stream on YouTube) Links to my githab repository with the implementation of interpreters can be found in my previous articles on Habré.