Различие между классами типов MonadPlus, Alternative и Monoid?

85

Классы типов Haskell стандартной библиотеки MonadPlus, Alternativeи Monoidкаждый предоставляют два метода с практически одинаковой семантикой:

  • Пустое значение: mzero, emptyили mempty.
  • Оператор , a -> a -> aкоторый соединяет значения в классе типов вместе: mplus, <|>или mappend.

Все три указывают эти законы, каких случаев следует придерживаться:

mempty `mappend` x = x
x `mappend` mempty = x

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

( Alternativeтакже предоставляет someи many, но их определений по умолчанию обычно достаточно, поэтому они не слишком важны с точки зрения этого вопроса.)

Итак, мой вопрос: почему эти три чрезвычайно похожих класса? Есть ли между ними какая-то реальная разница, помимо различных ограничений суперкласса?

00дани
источник
Это хороший вопрос. В частности, Applicativeи MonadPlusкажутся точно такими же (по модулю ограничений суперкласса).
Питер
1
Там же ArrowZeroи ArrowPlusдля стрел. Моя ставка: сделать подписи типа уборщика (что делает суперкласс отличаясь ограничений , на реальную разницу).
Cat Plus Plus
2
@CatPlusPlus: ну, ArrowZeroи ArrowPlusесть вид * -> * -> *, что означает, что вы можете передать их для типа стрелки один раз для функции, которая должна использовать их для множества типов, чтобы использовать, Monoidвам нужно будет потребовать экземпляр Monoidдля каждого конкретного создания экземпляра, и у вас не будет гарантии, что они обрабатываются аналогичным образом, экземпляры могут быть не связаны!
Эдвард КМЕТТ

Ответы:

121

MonadPlusи Monoidслужат разным целям.

MonoidПараметр A параметризуется по типу вида *.

class Monoid m where
    mempty :: m
    mappend :: m -> m -> m

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

Однако MonadPlusне только указывает, что у вас есть моноидальная структура, но также и то, что эта структура связана с тем, как она Monadработает, и что эта структура не заботится о значении, содержащемся в монаде, это (частично) указывается фактом это MonadPlusтребует своего рода аргумента * -> *.

class Monad m => MonadPlus m where
    mzero :: m a
    mplus :: m a -> m a -> m a

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

По крайней мере, мы знаем

mzero >>= k = mzero

но есть два других конкурирующих расширения, левый (sic) закон распределения

mplus a b >>= k = mplus (a >>= k) (b >>= k)

и закон левого улова

mplus (return a) b = return a

Таким образом, любой экземпляр MonadPlusдолжен удовлетворять одному или обоим этим дополнительным законам.

Так что насчет Alternative?

Applicativeбыл определен позже Monadи логически принадлежит к суперклассу Monad, но в значительной степени из-за различного давления на разработчиков еще в Haskell 98, даже Functorне был суперклассом Monadдо 2015 года. Теперь у нас, наконец, есть Applicativeсуперкласс MonadGHC (если не пока что в языковом стандарте.)

Фактически, Alternativeэто Applicativeто, что MonadPlusнужно Monad.

Для этого мы получим

empty <*> m = empty

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

К сожалению, даже empty <*> m = emptyзакон слишком силен. Например, он не работает в обратном направлении !

Когда мы смотрим на MonadPlus, нам почти навязывают закон пустой >> = f = пустой. Пустая конструкция не может содержать никаких букв для вызова функции f.

Однако, так как Applicativeэто не суперкласс Monadи Alternativeэто не суперкласс MonadPlus, мы заводиться определения обоих экземпляров отдельно.

Более того, даже если бы это Applicativeбыл суперкласс Monad, вам все MonadPlusравно понадобился бы этот класс, потому что даже если бы мы подчинялись

empty <*> m = empty

этого недостаточно, чтобы доказать, что

empty >>= f = empty

Так что утверждать, что что-то есть, MonadPlusсильнее, чем утверждать, что это так Alternative.

Итак, по соглашению, MonadPlusи Alternativeдля данного типа должны согласовываться, но Monoidмогут быть совершенно разными.

Например, MonadPlusи Alternativeдля Maybeделают очевидную вещь:

instance MonadPlus Maybe where
    mzero = Nothing
    mplus (Just a) _  = Just a
    mplus _        mb = mb

но Monoidэкземпляр поднимает полугруппу в Monoid. К сожалению, поскольку Semigroupв то время в Haskell 98 не существовало класса, он делает это, запрашивая Monoid, но не используя его модуль. ಠ_ಠ

instance Monoid a => Monoid (Maybe a) where
    mempty = Nothing
    mappend (Just a) (Just b) = Just (mappend a b)
    mappend Nothing x = x
    mappend x Nothing = x
    mappend Nothing Nothing = Nothing

TL; DR MonadPlus является более сильным , чем требование Alternative, которое в свою очередь является более сильным , чем требование Monoid, и в то время , MonadPlusи Alternativeэкземпляры для типа должны быть связаны, то Monoidможет быть (а иногда) нечто совершенно иное.

Эдвард КМЕТТ
источник
2
Отличный ответ, однако последнее определение кажется неправильным, оно не удовлетворяет mempty `mappend` x ≡ x.
Витус
2
Отличный ответ. Кто - нибудь знает типа (обычно используется) , который имеет разные MonadPlus и Alternativeреализации?
Питер
7
@EdwardKmett: Ответ на этот вопрос , кажется, подразумевает , что может быть , Monadкоторый является , Alternativeно не MonadPlus. Я задал вопрос о том, чтобы найти конкретный пример этого; если вы знаете такое, я бы с удовольствием его увидел.
Antal Spector-Zabusky
2
Можете ли вы объяснить закон левого улова для monadplus? Очевидно, это нарушено []; должен [] действительно игнорировать свой второй аргумент, если его первый непустой?
ben w
4
@benw левое распределение, возможно, является более разумным законом, но в некоторых случаях он не выполняется. left catch - это альтернативный закон, который эти другие примеры склонны поддерживать, но который не поддерживается большинством других. Следовательно, у нас действительно есть 2 в значительной степени не связанных друг с другом набора законов, реализуемых разными экземплярами, поэтому MonadPlusна самом деле это два класса, замаскированные под один, потому что большинству людей все равно.
Эдвард КМЕТТ