Моноиды

Эта главейка — блёклая тень лекций мисс-моноид, но мы провернём всё по-колхозному. Моноид — это абстракция, для которой заданы ассоциативная операция и нейтральный элемент. Ассоциативность разрешает разбивать работу на части и группировать результаты разными способами, не меняя порядок данных, — отсюда параллельная агрегация (map-reduce) и свёртки.

В Haskell моноид задаётся парой классов: Semigroup даёт ассоциативную операцию, а Monoid добавляет к ней нейтральный элемент:

class Semigroup a where
  (<>) :: a -> a -> a          -- ассоциативная операция

class Semigroup a => Monoid a where
  mempty :: a                  -- нейтральный элемент

Экземпляры обязаны соблюдать два закона — ассоциативность операции и нейтральность $\mathtt{mempty}$:

(x <> y) <> z == x <> (y <> z)   -- ассоциативность

mempty <> x == x                 -- нейтральный элемент
x <> mempty == x                 -- с обеих сторон

Экземпляров в стандартной библиотеке множество:

-- списки: (<>) = (++), mempty = []
[1, 2] <> [3]                    -- [1, 2, 3]

-- числа — моноид двумя способами, поэтому нужны обёртки:
Sum 2     <> Sum 3               -- Sum 5      (mempty = Sum 0)
Product 2 <> Product 3           -- Product 6  (mempty = Product 1)

-- булевы значения:
Any True <> Any False            -- Any True   (||, mempty = Any False)
All True <> All False            -- All False  (&&, mempty = All True)

-- минимум и максимум:
Min 5 <> Min 2                   -- Min 2
Max 5 <> Max 2                   -- Max 5

Теперь пару слов о reduce: $\mathtt{mconcat}$ — его моноидный вариант. Он сворачивает список моноидных значений, ничего не зная о конкретном типе:

mconcat :: Monoid a => [a] -> a
mconcat = foldr (<>) mempty

mconcat [[1], [2, 3], []]        -- [1, 2, 3]

Законы Monoid позволяют безопасно разбить данные на части, обработать части параллельно, а затем собрать частичные результаты через (<>), сохранив исходный порядок.

Например, каждый рабочий поток может независимо накопить свой кусок лога, после чего куски склеиваются как списки. Точно так же можно параллельно посчитать суммы отдельных порций данных, а затем сложить частичные суммы:

-- логи трёх независимых рабочих потоков
workerLogs = ["worker 1: done\n", "worker 2: done\n", "worker 3: done\n"]
fullLog = mconcat workerLogs

-- суммы, независимо посчитанные на разных порциях данных
partialSums = [Sum 120, Sum 95, Sum 143]
total = getSum (mconcat partialSums)  -- 358

Ассоциативность гарантирует, что результат не зависит от группировки частичных результатов: слева направо, попарно деревом или по числу доступных ядер.