Пусть есть полугруппа с двусторонней единицей, левыми нулями и правыми нулями. Допустим, нам уже вторую неделю известен хаскелл, посему можно выдавить следущий фекалокод (первое приближение, видимо, неверное полностью).
import Prelude hiding ((*))
data SGelement = SGe -- two-sided identity element
| SGr -- right zero element
| SGl -- left zero element
instance Show SGelement where
show SGe = "1"
show SGr = "0r"
show SGl = "0l"
(*) :: SGelement -> SGelement -> SGelement
SGl * _ = SGl
_ * SGr = SGr
SGe * x = x
x * SGe = x
_ * _ = error "*>: undefined behavior"
Дескать, определили классик SGelement (sg - semigroup), дата-объектиками которого может быть только либо двусторонняя единица, левый ноль или правый ноль. Иное нас не интересует. Ну и определили операцию (пускай, умножение) над этими элементиками.
> SGe Main.* SGr
0r
it :: SGelement
Ого, круто, умножили единицу на правый ноль, получили правый ноль. Удивительно.
> SGr Main.* SGr
0r
it :: SGelement
Ого, круто, умножили правый ноль на правый ноль, получили правый ноль. Непонятно только, какой из двух. То есть, с данным убогим классиком однозначно идентифицировать какой из правых нулей получился в результате, нельзя. А получился, очевидно, второй.
К чему это всё?
Допустим, есть полугруппа левых нулей с единицей, состоящая из трёх элементов, L = {e,l1,l2}. Есть полугруппа правых нулей без единицы, состоящая из двух элементов, R = {r1,r2}.
Рассмотрим их прямое произведение A = LxR = { (e;r1), (l1;r1), (l2;r1), (e;r2), (l1;r2), (l2;r2) }.
Как для каждого элемента x из A найти A*x?
Допустим, для (e;r1):
(e;r1) * (e;r1) = (e;r1)
(l1;r1) * (e;r1) = (l1;r1)
(l2;r1) * (e;r1) = (l2;r1)
(e;r2) * (e;r1) = (e;r1)
(l1;r2) * (e;r1) = (l1;r1)
(l2;r2) * (e;r1) = (l2;r1)
Иными словами, (e,r1) можно представить как некоторое отображение из A в A с помощью поэлементного соответствия. То есть, (1,2,3,4,5,6) * (e,r1) = (1,2,3,1,2,3).
Вопрос - если для (e,r1) мы получили (1,2,3,1,2,3), то как получить ответы для остальных элементов A?
Допустим, даже получится всё это нахардкодить. 6 элементов ещё немного. А если потребуется подсчитать перестановочки для произведения аналогичных десятиэлементных полугрупп?
Подытоживая. Чувствуется, что можно очень ловко и нативно описать данную структуру. Но пока не представляю как.
С радостью бы научился как надо.
