Ассоциативная бинарная операция для Option в Scala

(Этот ответ украл его определения из https://stackoverflow.com/a/3870310/200266 и только пытается чтобы дать приблизительное объяснение. Мои познания в теории категорий довольно базовые.)

В общем случае утверждение, что монада также является моноидом, справедливо только в том случае, если вы рассматриваете функтор (например, T => Option[T]), а не значения (например, Some(3) или None).

В качестве примера моноида над значениями давайте посмотрим на List[T].

У нас есть бинарная операция • : S × S -> S:

def append[T](list1: List[T], list2: List[T]): List[T] = list1 append list2

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

Теперь в приведенном выше случае × можно рассматривать как возвращающий кортеж входных значений:

List[T] × List[T] => (List[T], List[T])

И наша функция append получает на вход этот кортеж.

Однако мы можем изменить операцию кортежа × на ∘, что теперь означает композицию функторов.

(K => List[K]) ∘ (K => List[K]) => (K => List[List[K]])

Итак, мы ищем функцию, выполняющую μ : T ∘ T -> T или более конкретную

(K => List[List[K]]) => (K => List[K])

Эта операция известна в Scala как flatten (join в Haskell). Элемент идентификации моноида — это конструктор монады, который не имеет общего имени в Scala (return в Haskell), но существует для каждой монады. Например. x => List(x).

Подводя итог, учитывая этот и другие ответы на этот вопрос, есть три возможности того, как монада может быть моноидом:

A) Каждая монада также является моноидом в указанном выше смысле при функторной композиции.

Б) Каждая монада M[T] имеет моноид, если также существует моноид (с некоторой бинарной операцией ~+~) для T: for {x <- ma; y <- mb} yield x ~+~ y

C) Некоторые монады могут иметь один или несколько специфических моноидов, которые отличаются от моноидов в B. Например, добавление List или orElse Option.

Я думаю, что orElse является допустимым ассоциативным бинарным оператором:

def test(a: Option[Int], b: Option[Int], c: Option[Int]): Boolean =
  ((a orElse b) orElse c) == (a orElse (b orElse c))

Seq(Option(1), Option(2), None).permutations.forall {
  case Seq(a, b, c) => test(a, b, c)
}

Это верно. Я использовал это свойство в реализации FingerTree, оно было предложено Hinze & Paterson в их версии Haskell, оно используется для реализации интервального дерева.

Option сам по себе не является моноидом, так же как Integer сам по себе не является моноидом. Моноид — это тип И ассоциативная бинарная операция.

Вы можете рассматривать тип Integer и добавление моноида. Целое число и умножение тоже являются моноидами. Преобразование двух Integer в String и их конкатенация ("2" + "3" = "23") также является допустимой ассоциативной операцией, которая может создать моноид с целыми числами: фактически ("2" concat "3") concat "4" = "2" concat ("3" concat "4") = "234".

Дело в том, что вы должны определить ассоциативную операцию, которая завершает определение «моноида» для типа, поэтому ваш вопрос «что такое ассоциативная операция…» не совсем корректен.

Как и в случае с целыми числами, Option[Int] и сложение или умножение могут быть моноидами, но Option[Int] как таковое - нет.

Как и @senia в своем ответе, вы можете сказать: «Я могу определить моноид на основе Option [T], если T сам является моноидом». В этом случае ассоциативная операция может использовать операцию, определенную для T, а Some[a] append Some[b] может быть Some[a append b].

Или, как это сделал @0__, вы можете найти конкретную операцию (orElse), которая вместе с Option[Int] образует моноид. Это тоже верно (но обратите внимание, что ответ начинается с «orElse — это действительный ассоциативный бинарный оператор»).

Вообще-то нет. Monad для Option не является Monoid для Option[T]. Monad определяется для M[_], а Monoid определяется для T.

Вы можете создать Monoid для Option[T], если у вас есть Monoid для T следующим образом:

def optionMonoid[T: Monoid]: Monoid[Option[T]] = new Monoid {
  def zero: Option[T] = None
  def append(f1: Option[T], f2: => Option[T]): Option[T] = (fi, f2) match {
    case (None, None) => None
    case (Some(a), Some(b)) => Some(a |+| b)
    case (r @ Some(_), None) => r
    case (None, r @ Some(_)) => r
  }
}

Есть два разных смысла моноида. Монада — это моноидный объект в смысле теории категорий (см. последний пример там ); это не моноид в смысле абстрактной алгебры (о котором говорится в большинстве других ответов).