В чем основное отличие Free Monoid от Monoid?

Question

Похоже, у меня есть довольно четкое понимание того, что такое Monoid в Хаскеле, но в последний раз я слышал о чем-то, что называется свободным моноидом.

Что такое свободный моноид и как он связан с моноидом?

Можете ли вы привести пример на Haskell?

Answer 1

Как вы уже знаете, моноид - это набор с элементом e и операцией <>, удовлетворяющий

e <> x = x <> e = x  (identity)
(x<>y)<>z = x<>(y<>z)  (associativity)

Теперь, моноид free , интуитивно, является моноидом, который удовлетворяет только тем уравнениям, приведенным выше, и, очевидно, всем их последствиям.

Например, моноид списка Haskell ([a], [], (++)) свободен.

Напротив, моноид суммы Хаскелла (Sum Int, Sum 0, \(Sum x) (Sum y) -> Sum (x+y)) не является свободным, поскольку он также удовлетворяет дополнительным уравнениям. Например, это коммутативно

x<>y = y<>x

и это не следует из первых двух уравнений.

Обратите внимание, что в математике можно доказать, что все свободные моноиды изоморфны моноиду списка [a]. Таким образом, «свободный моноид» в программировании - это всего лишь причудливый термин для любой структуры данных, которая 1) может быть преобразована в список, и обратно, без потери информации, и 2) наоборот, список может быть преобразован в него, и обратно, без потери информации.

В Хаскеле вы можете мысленно заменить «свободный моноид» на «тип списка».

Answer 2

В контексте программирования я обычно переводю свободный моноид на [a]. В своей превосходной серии статей о теории категорий для программистов Бартош Милевский описывает свободных моноидов в Haskell как список моноидов (предполагая, что некоторые проблемы с бесконечными списками игнорируются).

Элемент identity - это пустой список, а двоичная операция - конкатенация списка:

Prelude Data.Monoid> mempty :: [Int]
[]
Prelude Data.Monoid> [1..3] <> [7..10]
[1,2,3,7,8,9,10]

Интуитивно, я думаю, что этот моноид является «свободным», потому что это моноид, к которому вы можете всегда применять, независимо от типа значения, с которым вы хотите работать (точно так же, как свободная монада Монаду можно всегда создавать из любого функтора).

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

Если у вас есть два (или более целых) числа, и вы знаете, что вы можете их агрегировать, но вы еще не решили, какой тип агрегации вы хотите применить, вы можете вместо этого «агрегировать» их, используя бесплатный monoid - практически это означает внесение их в список:

Prelude Data.Monoid> [3,7]
[3,7]

Если позже вы решите, что хотите добавить их вместе, это возможно:

Prelude Data.Monoid> getSum $ mconcat $ Sum <$> [3,7]
10

Если вместо этого вы хотите умножить их, вы также можете сделать это:

Prelude Data.Monoid> getProduct $ mconcat $ Product <$> [3,7]
21

В этих двух примерах я сознательно решил поднять каждое число до типа (Sum, Product), который воплощает более конкретный моноид, а затем использовать mconcat для выполнения агрегации.

Для сложения и умножения есть более краткие способы сделать это, но я сделал это таким образом, чтобы показать, как вы можете использовать более специфический моноид для интерпретации свободного моноида.

Answer 3

Моноид (M,•,1) - это математическая структура, такая что:

1. M это набор
2. 1 является членом M
3. • : M * M -> M
4. a•1 = a = 1•a
5. Учитывая элементы a, b и c в M, мы имеем a•(b•c) = (a•b)•c.

Свободный моноид на множестве M - это моноид (M',•,0) и функция e : M -> M', такая, что для любого моноида (N,*,1) при заданной (установленной) карте f : M -> N мы можем расширить это до морфизма моноидов. f' : (M',•,0) -> (N,*,1), т.е.

f a = f' (e a)
f' 0 = 1
f' (a•b) = (f' a) • (f' b)

Другими словами, это моноид, который не делает ничего особенного.

Примером моноида являются целые числа с добавляемой операцией и тождеством, равным 0. Другой моноид - это последовательности целых чисел с объединенной операцией, а тождество - пустая последовательность. Теперь добавляемые целые числа не являются свободным моноидом на целых числах. Рассмотрим карту на последовательности целых чисел, принимающих от n до (n). Тогда для того, чтобы это было бесплатным, нам нужно было бы распространить это на карту, взяв n + m до (n,m), т.е. это должно занять 0 до (0) и до (0,0) и до (0,0,0) и так далее.

С другой стороны, если мы попытаемся рассматривать последовательности целых чисел как свободный моноид на целых числах, мы увидим, что в этом случае это работает. Расширение карты на целые числа с добавлением - это то, которое принимает сумму последовательности (с суммой (), равной 0).

Так что же такое свободный моноид на множестве S? Ну, одну вещь, которую мы могли бы попробовать, это просто произвольные двоичные деревья S. В типе Haskell это будет выглядеть так:

data T a = Unit | Single a | Conc (T a) (T a)

И он будет иметь идентичность Unit, e = Single и (•) = Conc.

И мы можем написать функцию, чтобы показать, как она бесплатна:

-- here the second argument represents a monoid structure on b
free :: (a -> b) -> (b -> b -> b, b) -> T a -> b
free f ((*),zero) = f' where
  f' (Single a) = f a
  f' Unit = zero
  f' (Conc a b) = f' a * f' b

Должно быть совершенно очевидно, что это удовлетворяет требуемым законам для свободного моноида на a. За исключением одного: T a не является моноидом, потому что оно не совсем соответствует законам 4 или 5.

Так что теперь мы должны спросить, можем ли мы превратить это в более простой свободный моноид, то есть тот, который является настоящим моноидом. Ответ - да. Одним из способов является наблюдение, что Conc Unit a и Conc a Unit и Single a должны быть одинаковыми. Итак, давайте сделаем первые два типа непредставимыми:

data TInner a = Single a | Conc (TInner a) (TInner a)
data T a = Unit | Inner (TInner a)

Второе наблюдение, которое мы можем сделать, заключается в том, что не должно быть никакой разницы между Conc (Conc a b) c и Conc a (Conc b c). Это связано с законом 5 выше. Затем мы можем сгладить наше дерево:

data TInner a = Single a | Conc (a,b,[a])
data T a = Unit | Inner (TInner a)

Странная конструкция с Conc силами состоит в том, чтобы иметь только один способ представлять Single a и Unit. Но мы видим, что мы можем объединить их все вместе: измените определение Conc на Conc [a], а затем мы можем изменить Single x на Conc [x] и Unit на Conc [], чтобы мы получили:

data T a = Conc [a]

Или мы можем просто написать:

type T a = [a]

И операции:

unit = []
e a = [a]
(•) = append

free f ((*),zero) = f' where
  f' [] = zero
  f' (x:xs) = f x * f' xs

Так что в Хаскеле тип списка называется свободным моноидом.

Answer 4

Свободный моноид - это особый тип моноида. В частности, это моноид, который вы получаете, принимая некоторый фиксированный набор элементов в качестве символов, а затем формируя все возможные строки из этих элементов. Эти строки, основной операцией которых является конкатенация строк, образуют моноид, и этот моноид называется свободным моноидом.