Является ли Monoid[String] действительно моноидом в scala?

В настоящее время я изучаю теорию категорий в scala, и закон ассоциативности говорит

(x + y) + z = x + (y + z)

Это нормально при работе с более чем двумя значениями

("Foo" + "Bar") + "Test" == "Foo" + ("Bar" + "Test") // true

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

3+1==1+3 // True
("Foo" + "Bar") == ("Bar" + "Foo") // Not commuative

Так законно ли говорить, что ассоциативность требует коммудативности для выполнения моноидного закона? Итак, действителен ли String Monoid в любом случае?


person Jay    schedule 05.10.2015    source источник
comment
Моноидная операция не обязательно должна быть коммутативной.   -  person Lee    schedule 05.10.2015


Ответы (1)


Так законно ли говорить, что ассоциативность требует коммутативности для выполнения закона моноида?

Нет. Бинарная операция не обязательно должна быть коммутативной, чтобы быть ассоциативной. Тот факт, что ("Foo" + "Bar") == ("Bar" + "Foo") ложно, не имеет отношения к тому факту, что + является ассоциативным для String..

Итак, действителен ли String Monoid в любом случае?

Да, вы можете иметь Monoid[String].

По определению:

Моноид — это множество, замкнутое ассоциативной бинарной операцией + и имеющее элемент идентичности I в S так, что для всех a в S выполняется I + a = a + I = a.

Моноид должен содержать хотя бы один элемент.

Пусть + будет бинарной операцией для Monoid[String]. Для любых двух строк, a и b, a + b также является String, поэтому бинарная операция закрывается над типом String. Без строгого доказательства мы также знаем, что оно ассоциативно.

то есть для всех строк a, b и c:

(a + b) + c == a + (b + c)

У нас также есть элемент идентификации "" (пустая строка), потому что для любой строки a, a + "" == a и "" + a == a.

Моноид, бинарная операция которого также является коммутативной, называется коммутативным моноидом. И у вас явно не может быть коммутативного моноида для String с помощью операции +.

person Michael Zajac    schedule 05.10.2015
comment
Еще один вопрос. Для чего на самом деле используется этот элемент идентификации? - person Jay; 06.10.2015
comment
Например, чтобы избежать особых случаев. Рассмотрите возможность объединения списка строк. Вы продолжаете добавлять последовательные строки к строке аккумулятора. Простейшая реализация начинается с того, что аккумулятор представляет собой пустую строку. Сравните это с инициализацией аккумулятора с использованием первой строки. Что делать, если нет первой строки (список пуст)? Другой пример — завершение рекурсии. Если я закончу, верните пустую строку (или идентификатор для общего моноида). - person Bartosz Milewski; 09.10.2015