Ответ 1

Я не буду рассматривать MonadPlus, потому что есть несогласие с его законами.

После попытки найти невозможные примеры, в которых структура аппликатора естественно приводит к альтернативному экземпляру, который не согласуется с его экземпляром Monoid *, я, наконец, придумал следующее:

Альтернативные законы более строгие, чем Monoid, потому что результат не может зависеть от внутреннего типа. Это исключает большое количество экземпляров Monoid из альтернатив. Эти типы данных допускают частичное (что означает, что они работают только для некоторых внутренних типов). Моноидные экземпляры, которые запрещены дополнительной "структурой" типа * -> *. Примеры:

• стандартный экземпляр Maybe для Monoid предполагает, что внутренний тип является Monoid = > не альтернативным

• ZipLists, кортежи и функции могут быть сделаны Monoids, если их внутренними типами являются моноиды = > не альтернативы

• последовательности, имеющие хотя бы один элемент, не могут быть альтернативами, потому что нет empty:

  data Seq a
      = End a
      | Cons a (Seq a)
    deriving (Show, Eq, Ord)
  

С другой стороны, некоторые типы данных не могут быть сделаны Альтернативами, поскольку они * -kinded:

• unit - ()
• Ordering
• numbers, booleans

Мой вывод: для типов, имеющих как экземпляр Alternative, так и Monoid, экземпляры должны быть одинаковыми. См. также этот ответ.

_{исключая Может быть, что я утверждаю, не учитывается, потому что его стандартный экземпляр не должен требовать Monoid для внутреннего типа, и в этом случае он будет идентичен Alternative}

Ответ 2

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

• Нет, Alternative и Monoid не означает разные вещи; Alternative для типов, которые имеют структуру как Applicative, так и Monoid. "Сбор" и "объединение" - это две разные интуиции для той же более широкой концепции.

• Alternative содержит empty, а также <|>, потому что дизайнеры полагали, что это будет полезно, и потому что это приводит к моноиду. Что касается выбора, empty соответствует невозможному выбору.

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

• MonadPlus немного сильнее, чем Alternative, так как он должен подчиняться большему количеству законов; эти законы связывают моноидальную структуру с монадической структурой в дополнение к аппликативной структуре. Если у вас есть экземпляры обоих, они должны совпадать.

Не означает Alternative что-то совершенно отличное от Monoid?

Не совсем! Отчасти причиной вашей путаницы является то, что класс Haskell Monoid использует довольно неплохие (ну, недостаточно общие) имена. Так математик определял бы моноид (будучи очень явным в нем):

Определение. Моноид - это множество M, снабженное отмеченным элементом ε ∈ M и бинарным оператором: M × M → M, обозначаемым сопоставлением, так что выполняются следующие два условия:

• ε - тождество: для всех m ∈ M mε = εm = m.
• · является ассоциативным: для всех m₁, m₂, m₃ ∈ M, (m₁m₂) m₃ = m₁ (m₂m₃).

Вот оно. В Haskell ε пишется mempty и · пишется mappend (или, в эти дни, <>), а множество M является типом M в instance Monoid M where ....

Глядя на это определение, мы видим, что он ничего не говорит о "объединении" (или о "сборе", если на то пошло). Он говорит о вещах и о ε, но это так. Теперь, безусловно, верно, что комбинирование вещей хорошо работает с этой структурой: ε соответствует отсутствию вещей, и m₁m₂ говорит, что если я буду глотать m₁ и m₂s вместе, я могу получить новую вещь, содержащую все их вещи. Но heres альтернативная интуиция: ε не соответствует никаким выборам, а m₁m₂ соответствует выбору между m₁ и m₂. Это "собирающая" интуиция. Заметим, что оба подчиняются моноидным законам:

• Не имея ничего и не имея выбора, они идентичны.
  • Если у меня нет материала и сглаживаю его вместе с некоторыми вещами, я снова получаю то же самое.
  • Если у меня есть выбор между выбором вообще (что-то невозможное) и некоторым другим выбором, я должен выбрать другой (возможный) выбор.
• Совместное собрание коллекций и выбор - оба являются ассоциативными.
  • Если у меня есть три коллекции вещей, это не имеет значения, если я glom первые два вместе, а затем третий, или последние два вместе, а затем первый; в любом случае, я получаю ту же самую общую коллекцию.
  • Если у меня есть выбор между тремя вещами, не имеет значения, если я (а) сначала выбираю между первым и вторым и третьим, а затем, если мне нужно, между первым и вторым или (б) сначала выберите между первый и второй или третий, а затем, если потребуется, между вторым и третьим. В любом случае, я могу выбрать то, что хочу.

(Примечание: Im играет быстро и свободно здесь, вот почему его интуиция. Например, важно помнить, что · не обязательно должно быть коммутативным, что выше этого глянца: вполне возможно, что m₁m₂ ≠ m₂m₁.)

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

И самое главное, что эти обе эти интуиции могут быть интерпретированы одной и той же самой несущей! Пусть M - некоторое множество множеств (а не множество всех множеств!), Содержащих пустое множество, пусть ε - пустое множество ∅, и пусть be задано объединение ∪. Легко видеть, что ∅ является тождеством для ∪ и что ∪ ассоциативно, поэтому можно заключить, что (M, ∅, ∪) является моноидом. Сейчас:

• Если мы думаем о множествах как о коллекциях вещей, то ∪ соответствует их объему, чтобы получить больше вещей - "сочетание" интуиции.
• Если мы думаем о множествах как о возможных действиях, то ∪ соответствует увеличению вашего пула возможных действий, чтобы выбрать из "интуиции" выбора.

И это именно то, что происходит с [] в Haskell: [a] является Monoid для всех a, а [] как прикладной функтор (и монада) используется для представления недетерминированности. И комбинация, и собирающая интуиция совпадают в одном типе: mempty = empty = [] и mappend = (<|>) = (++).

Таким образом, класс Alternative предназначен для представления объектов, которые (а) являются аппликативными функторами, и (b) при создании экземпляра в типе имеют значение и двоичную функцию, которые следуют некоторым правилам. Какие правила? Моноидные правила. Зачем? Потому что это оказывается полезным: -)

Почему Alternative нужен пустой метод/член?

Ну, snarky ответ "потому что Alternative представляет моноидную структуру". Но реальный вопрос: почему моноидная структура? Почему не только полугруппа, моноид без ε? Один из них - утверждать, что моноиды более полезны. Я думаю, что многие люди (но, возможно, не Эдвард Кемт) согласились бы с этим; почти все время, если у вас есть разумный (<|>)/mappend/·, вы сможете определить разумный empty/mempty/ε. С другой стороны, наличие дополнительной общности приятное, поскольку оно позволяет размещать больше вещей под зонтиком.

Вы также хотите знать, как это связано с "собирающей" интуицией. Имея в виду, что в некотором смысле правильный ответ "знаю, когда отказаться от" собирающей интуиции ", я думаю, вы можете объединить их. Рассмотрим [], аппликативный функтор для недетерминизма. Если я комбинирую два значения типа [a] с (<|>), что соответствует недетерминированному выбору либо действия слева, либо действия справа. Но иногда у вас не будет никаких возможных действий с одной стороны - и это прекрасно. Аналогично, если мы рассматриваем синтаксические анализаторы, (<|>) представляет собой синтаксический анализатор, который анализирует либо то, что слева, либо что-то справа (оно" выбирает"). И если у вас есть парсер, который всегда терпит неудачу, это становится личностью: если вы его выберете, вы сразу же отклоните этот выбор и попробуйте другой.

Все это сказало, помните, что вполне возможно иметь класс, почти похожий на Alternative, но не имеющий empty. Это было бы совершенно правдоподобно - оно могло быть даже суперклассом Alternative, но не так, как это делал Хаскелл. Предположительно, это не догадывается о том, что полезно.

Почему класс типа Alternative нуждается в ограничении Applicative и зачем ему нужен * -> *?... Почему не просто [использовать] liftA2 mappend?

Хорошо, рассмотрим каждое из этих трех предложенных изменений: избавление от ограничения Applicative для Alternative; изменение типа аргумента Alternative s; и используя liftA2 mappend вместо <|> и pure mempty вместо empty. Хорошо посмотрите на это третье изменение сначала, так как оно самое разное. Предположим, что мы полностью избавились от Alternative и заменили класс на две простые функции:

fempty :: (Applicative f, Monoid a) => f a
fempty = pure mempty

(>|<) :: (Applicative f, Monoid a) => f a -> f a -> f a
(>|<) = liftA2 mappend

Мы могли бы даже сохранить определения some и many. И это дает нам моноидную структуру, ее истинность. Но похоже, что это дает нам неправильный. Должен ли Just fst >|< Just snd сбой, поскольку (a,a) -> a не является экземпляром Monoid? Нет, но это то, что привело бы к указанному выше коду. Моноидный экземпляр, который мы хотим, - это тот, который является агностиком внутреннего типа (для использования терминологии Matthew Farkas-Dyck in очень связанная дискуссия по haskell-cafe, которая задает некоторые очень похожие вопросы); структура Alternative представляет собой моноид, определяемый структурой f s, а не структурой аргумента f s.

Теперь, когда мы думаем, что мы хотим оставить Alternative как своего рода класс типа, рассмотрим два предлагаемых способа его изменения. Если мы изменим вид, нам нужно избавиться от ограничения Applicative; Applicative говорит только о вещах рода * -> *, и поэтому theres никак не ссылаться на него. Это оставляет два возможных изменения; первое, более незначительное изменение состоит в том, чтобы избавиться от ограничения Applicative, но оставить только один:

class Alternative' f where
  empty' :: f a
  (<||>) :: f a -> f a -> f a

Другое, большее, изменение - избавиться от ограничения Applicative и изменить вид:

class Alternative'' a where
  empty'' :: a
  (<|||>) :: a -> a -> a

В обоих случаях нам нужно избавиться от some/many, но это ОК; мы можем определить их как автономные функции с типом (Applicative f, Alternative' f) => f a -> f [a] или (Applicative f, Alternative'' (f [a])) => f a -> f [a].

Теперь, во втором случае, когда мы меняем тип переменной типа, мы видим, что наш класс точно такой же, как Monoid (или, если вы все еще хотите удалить empty'', Semigroup), поэтому у них нет преимущества иметь отдельный класс. И фактически, даже если оставить только переменную вида, но удалить ограничение Applicative, Alternative просто станет forall a. Monoid (f a), хотя мы не можем записать эти количественные ограничения в Haskell, даже не со всеми фантастическими расширениями GHC. (Обратите внимание, что это выражает агностицизм внутреннего типа, упомянутый выше). Таким образом, если мы сможем сделать одно из этих изменений, то у нас нет причин держать Alternative (за исключением возможности выразить это количественное ограничение, но это вряд ли кажется убедительным).

Итак, вопрос сводится к "есть ли связь между частями Alternative и Applicative частями f, которая является экземпляром обоих?" И пока в документации нет ничего, я собираюсь встать и сказать "да" или, по крайней мере, должно быть. Я думаю, что Alternative должен подчиняться некоторым законам, относящимся к Applicative (в дополнение к моноидным законам); в частности, я думаю, что эти законы похожи на

• Правильная дистрибутивность (<*>): (f <|> g) <*> a = (f <*> a) <|> (g <*> a)
• Правильное поглощение (для <*>): empty <*> a = empty
• Левая дистрибутивность (fmap): f <$> (a <|> b) = (f <$> a) <|> (f <$> b)
• Левое поглощение (для fmap): f <$> empty = empty

Эти законы верны для [] и Maybe, и (притворяясь, что его экземпляр MonadPlus является экземпляром Alternative) IO, но я не делал никаких доказательств или исчерпывающего тестирования. (Например, я изначально считал, что левая дистрибутивность поддерживается для <*>, но это "выполняет эффекты" в неправильном порядке для [].) Однако, по аналогии, верно, что MonadPlus ожидается подчиняться аналогичным законам (хотя есть, по-видимому, какая-то двусмысленность, о которой). Я изначально хотел потребовать третий закон, который кажется естественным:

• Левое поглощение (для <*>): a <*> empty = empty

Однако, хотя я считаю, что [] и Maybe подчиняются этому закону, IO doesnt, и я думаю (по причинам, которые станут очевидными в следующих параграфах), лучше всего не требовать этого.

И действительно, похоже, что Edward Kmett имеет несколько слайдов, где он придерживается аналогичного мнения; Чтобы понять это, нужно взять краткое отступление, в котором участвуют еще более математический жаргон. Заключительный слайд "Я хочу больше структуры" говорит, что "моноид относится к аппликативной, как правая семинепремия, к альтернативе" и "Если вы выбросите аргумент аппликативного, вы получите моноид, если вы выбросите проведите аргумент Альтернативы, которую вы получите RightSemiNearRing.

Правые семерки? "Как в нее вошли правые семернички?" Я слышу, как вы плачете. Ну,

Определение.. Прямоугольное полукольцо (также правое семантипирование, но первое, похоже, больше используется в Google) представляет собой четверку (R, +, ·, 0), где (R, +, 0) является моноидом, (R, ·) является полугруппой и выполнены следующие два условия:

• · является правым дистрибутивным над +: для всех r, s, t ∈ R, (s + t) r = sr + tr.
• 0 является правым поглощением для:: для всех r ∈ R, 0r = 0.

Аналогично определяется левое полубликовое.

Теперь это не работает, потому что <*> не является действительно ассоциативным или двоичным оператором - типы не совпадают. Я думаю, что это то, о чем Эдвард Кметт справляется, когда говорит о "отбросе аргумента". Другой вариант может заключаться в том, чтобы сказать (Im unsure, если это правильно), что мы действительно хотим (f a, <|>, <*>, empty), чтобы сформировать правое околополумерное, где суффикс "-oid" указывает, что бинарные операторы могут применяться только к конкретным парам элементов (à la groupoids). И wed также хотят сказать, что (f a, <|>, <$>, empty) был левым почти полуреалистичным, хотя это, возможно, следовало бы из комбинации законов Applicative и правого ближнего порядка, полуреалистичная структура. Но теперь я нахожусь над моей головой, и это в действительности не имеет большого значения.

Во всяком случае, эти законы, будучи более сильными, чем моноидные законы, означают, что вполне допустимые экземпляры Monoid становятся недействительными экземплярами Alternative. В стандартной библиотеке есть (по крайней мере) два примера: Monoid a => (a,) и Maybe. Давайте посмотрим на каждого из них быстро.

Учитывая любые две моноиды, их продукт является моноидом; следовательно, кортежи можно сделать очевидным способом экземпляра Monoid (переформатирование источника базовых пакетов):

instance (Monoid a, Monoid b) => Monoid (a,b) where
  mempty = (mempty, mempty)
  (a1,b1) `mappend` (a2,b2) = (a1 `mappend` a2, b1 `mappend` b2)

Аналогично, мы можем создавать кортежи, первый компонент которых является элементом моноида в экземпляр Applicative путем накопления моноидных элементов (переформатирование базовых пакетов источник):

instance Monoid a => Applicative ((,) a) where
  pure x = (mempty, x)
  (u, f) <*> (v, x) = (u `mappend` v, f x)

Тем не менее, кортежи представляют собой экземпляр Alternative, потому что они не могут быть: моноидальная структура над Monoid a => (a,b) не присутствует для всех типов b, а моноидальная структура Alternative должна быть агностиком внутреннего типа. Не обязательно b быть монадой, чтобы выразить (f <> g) <*> a, нам нужно использовать экземпляр Monoid для функций, который для функций вида Monoid b => a -> b. И даже в случае, когда у нас есть вся необходимая моноидальная структура, она нарушает все четыре закона Alternative. Чтобы убедиться в этом, пусть ssf n = (Sum n, (<> Sum n)) и пусть ssn = (Sum n, Sum n). Затем, набрав (<>) для mappend, мы получим следующие результаты (которые можно проверить в GHCi с случайной аннотацией типа):

• Правильная дистрибутивность:
  • (ssf 1 <> ssf 1) <*> ssn 1 = (Sum 3, Sum 4)
  • (ssf 1 <*> ssn 1) <> (ssf 1 <*> ssn 1) = (Sum 4, Sum 4)
• Правильное поглощение:
  • mempty <*> ssn 1 = (Sum 1, Sum 0)
  • mempty = (Sum 0, Sum 0)
• Левая дистрибутивность:
  • (<> Sum 1) <$> (ssn 1 <> ssn 1) = (Sum 2, Sum 3)
  • ((<> Sum 1) <$> ssn 1) <> ((<> Sum 1) <$> ssn 1) = (Sum 2, Sum 4)
• Левое всасывание:
  • (<> Sum 1) <$> mempty = (Sum 0, Sum 1)
  • mempty = (Sum 1, Sum 1)

Затем рассмотрим Maybe. Как бы то ни было, Maybe s Monoid и Alternative экземпляры не согласны. (Хотя обсуждение haskell-cafe Я упоминаю, что в начале этого раздела предлагается изменить это, theres a Option newtype из пакета полугрупп, который даст тот же эффект.) Как Monoid, Maybe поднимает полугруппы в моноиды, используя Nothing как тождество; поскольку базовый пакет не имеет полугруппового класса, он просто поднимает моноиды, и поэтому мы получаем (переформатирование источника базовых пакетов):

instance Monoid a => Monoid (Maybe a) where
  mempty = Nothing
  Nothing `mappend` m       = m
  m       `mappend` Nothing = m
  Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)

С другой стороны, как Alternative, Maybe представляет приоритетный выбор с ошибкой, и поэтому мы получаем (снова переформатируем источник базовых пакетов):

instance Alternative Maybe where
  empty = Nothing
  Nothing <|> r = r
  l       <|> _ = l

И получается, что только последний удовлетворяет законам Alternative. Экземпляр Monoid выходит менее неудачно, чем (,) s; он подчиняется законам относительно <*>, хотя почти случайно - он возникает из поведения единственного экземпляра Monoid для функций, который (как упоминалось выше) поднимает функции, возвращающие моноиды в аппликативный функтор читателя, Если вы это сделаете (все очень механически), вы обнаружите, что справедливая дистрибутивность и правильное поглощение для <*> сохраняются как для экземпляров Alternative, так и для Monoid, равно как и левое поглощение для fmap. А левая дистрибутивность для fmap выполняется для экземпляра Alternative следующим образом:

f <$> (Nothing <|> b)
  = f <$> b                          by the definition of (<|>)
  = Nothing <|> (f <$> b)            by the definition of (<|>)
  = (f <$> Nothing) <|> (f <$> b)    by the definition of (<$>)

f <$> (Just a <|> b)
  = f <$> Just a                     by the definition of (<|>)
  = Just (f a)                       by the definition of (<$>)
  = Just (f a) <|> (f <$> b)         by the definition of (<|>)
  = (f <$> Just a) <|> (f <$> b)     by the definition of (<$>)

Однако это не работает для экземпляра Monoid; пишу (<>) для mappend, имеем:

• (<> Sum 1) <$> (Just (Sum 0) <> Just (Sum 0)) = Just (Sum 1)
• ((<> Sum 1) <$> Just (Sum 0)) <> ((<> Sum 1) <$> Just (Sum 0)) = Just (Sum 2)

Теперь в этом примере есть одна оговорка. Если требуется только Alternative быть совместимым с <*>, а не с <$>, то Maybe в порядке. Эдвард Кемтс слайды, упомянутые выше, не ссылаются на <$>, но я думаю, что разумно также требовать от него законов; тем не менее, я не могу найти что-либо, чтобы поддержать меня.

Таким образом, мы можем заключить, что если a Alternative является более сильным требованием, чем a Monoid, и поэтому он требует другого класса. Самым чистым примером этого может быть тип с агностическим экземпляром Monoid внутреннего типа и экземпляром Applicative, которые несовместимы друг с другом; однако в базовом пакете таких типов нет, и я не могу думать о них. (Его возможного нет, хотя Id удивлен.) Тем не менее, эти гностические примеры внутреннего типа демонстрируют, почему два типа классов должны быть разными.

Какова точка класса типа MonadPlus?

MonadPlus, как Alternative, является усилением Monoid, но по сравнению с Monad вместо Applicative. По словам Эдварда Кемта в его ответе на вопрос "Различие между классами MonadPlus, Alternative и Monoid?" , MonadPlus также сильнее, чем Alternative: например, закон empty <*> a не означает, что empty >>= f. AndrewC содержит два примера: Maybe и его двойственный. Проблема осложняется тем, что существуют два потенциальных набора законов для MonadPlus. Общепризнано, что MonadPlus должен образовывать моноид с mplus и mempty, и его предполагается удовлетворять левому закону нулевого уровня, mempty >>= f = mempty. Hhowever, некоторые MonadPlus ses удовлетворяют левому распределению, mplus a b >>= f = mplus (a >>= f) (b >>= f); и другие удовлетворяют левому улову, mplus (return a) b = return a. (Заметим, что левое нуль/распределение для MonadPlus аналогично правильному распределению/поглощению для Alternative; (<*>) более похоже на (=<<) чем (>>=).) Левое распределение, вероятно, "лучше", поэтому любой MonadPlus, который удовлетворяет левому улову, например Maybe, является Alternative, но не первым типом MonadPlus. И так как левый улов зависит от упорядочивания, вы можете представить оболочку newtype для Maybe, где экземпляр Alternative имеет правую смещенность вместо левого смещения: a <|> Just b = Just b. Это не будет удовлетворять ни левому распределению, ни левому улову, но будет вполне достоверным Alternative.

Однако, поскольку любой тип, который является MonadPlus, должен иметь свой экземпляр, совпадающий с его экземпляром Alternative (я считаю, что это требуется так же, как требуется, чтобы ap и (<*>) равны для Monad, которые являются Applicative s), вы могли бы представить определение класса MonadPlus вместо

class (Monad m, Alternative m) => MonadPlus' m

Класс не должен объявлять новые функции; это просто обещание о законах, соблюдаемых empty и (<|>) для данного типа. Этот метод проектирования не используется в стандартных библиотеках Haskell, но используется в некоторых более ориентированных на математику пакетах для аналогичных целей; например, пакет lattices использует его, чтобы выразить идею о том, что lattice - это просто присоединиться к полурешетке, а встретить полурешетку по тому же типу, которые связаны законами поглощения.

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

class (Applicative f, forall a. Monoid (f a)) => Alternative''' f

но (как уже упоминалось выше) даже GHC Haskell не поддерживает количественные ограничения.

Кроме того, обратите внимание, что наличие Alternative как суперкласса MonadPlus потребует, чтобы Applicative был суперклассом Monad, поэтому удача в том, чтобы это произошло. Если вы столкнулись с этой проблемой, всегда существует WrappedMonad newtype, который превращает любой Monad в Applicative очевидным образом; theres instance MonadPlus m => Alternative (WrappedMonad m) where ..., который делает именно то, что вы ожидаете.

Ответ 3

import Data.Monoid
import Control.Applicative

Проследите пример того, как Monoid и Alternative взаимодействуют с функтором Maybe и функтором ZipList, но пусть начинаются с нуля, отчасти, чтобы получить все определения, свежие в нашем сознании, отчасти, чтобы перестать переключать вкладки до хлама все время, но в основном я могу запустить это прошлое ghci, чтобы исправить мои опечатки!

(<>) :: Monoid a => a -> a -> a
(<>) = mappend -- I'll be using <> freely instead of `mappend`.

Здесь может быть клоун:

data Perhaps a = Yes a | No  deriving (Eq, Show)

instance Functor Perhaps where
   fmap f (Yes a) = Yes (f a)
   fmap f No      = No

instance Applicative Perhaps where
   pure a = Yes a
   No    <*> _     = No
   _     <*> No    = No
   Yes f <*> Yes x = Yes (f x)

и теперь ZipList:

data Zip a = Zip [a]  deriving (Eq,Show)

instance Functor Zip where
   fmap f (Zip xs) = Zip (map f xs)

instance Applicative Zip where
   Zip fs <*> Zip xs = Zip (zipWith id fs xs)   -- zip them up, applying the fs to the xs
   pure a = Zip (repeat a)   -- infinite so that when you zip with something, lengths don't change

Структура 1: объединение элементов: Monoid

Возможно, клон

Сначала посмотрим на Perhaps String. Есть два способа их комбинирования. Во-первых, конкатенация

(<++>) :: Perhaps String -> Perhaps String -> Perhaps String
Yes xs <++> Yes ys = Yes (xs ++ ys)
Yes xs <++> No     = Yes xs
No     <++> Yes ys = Yes ys
No     <++> No     = No

Конкатенация работает по умолчанию на уровне String, а не на уровне Maybe, обрабатывая No, как будто это Yes []. Он равен liftA2 (++). Это разумно и полезно, но, возможно, мы могли бы обобщить только использование ++ для использования любого способа объединения - любой Monoid then!

(<++>) :: Monoid a => Perhaps a -> Perhaps a -> Perhaps a
Yes xs <++> Yes ys = Yes (xs `mappend` ys)
Yes xs <++> No     = Yes xs
No     <++> Yes ys = Yes ys
No     <++> No     = No

Эта моноидная структура для Perhaps пытается работать как можно больше на уровне a. Обратите внимание на ограничение Monoid a, говорящее, что мы используем структуру с уровня a. Это не альтернативная структура, это производная (поднятая) моноидная структура.

instance Monoid a => Monoid (Perhaps a) where
   mappend = (<++>)
   mempty = No

Здесь я использовал структуру данных a, чтобы добавить структуру ко всему предмету. Если бы я сочетал Set s, я мог бы добавить вместо него Ord a.

Клон ZipList

Итак, как мы должны комбинировать элементы с zipList? Что они должны делать, если мы их объединяем?

   Zip ["HELLO","MUM","HOW","ARE","YOU?"] 
<> Zip ["this", "is", "fun"]
=  Zip ["HELLO" ? "this",   "MUM" ? "is",   "HOW" ? "fun"]

mempty = ["","","","",..]   -- sensible zero element for zipping with ?

Но что мы должны использовать для ?. Я говорю, что единственным разумным выбором здесь является ++. На самом деле, для списков (<>) = (++)

   Zip [Just 1,  Nothing, Just 3, Just 4]
<> Zip [Just 40, Just 70, Nothing]
 =  Zip [Just 1 ? Just 40,    Nothing ? Just 70,    Just 3 ? Nothing]

mempty = [Nothing, Nothing, Nothing, .....]  -- sensible zero element

Но что мы можем использовать для ? Я говорю, что мы собираемся объединить элементы, поэтому мы снова должны использовать оператор объединения элементов из Monoid: <>.

instance Monoid a => Monoid (Zip a) where
   Zip as `mappend` Zip bs = Zip (zipWith (<>) as bs) -- zipWith the internal mappend
   mempty = Zip (repeat mempty)  -- repeat the internal mempty

Это единственный разумный способ комбинирования элементов с использованием zip - так что это единственный разумный экземпляр моноида.

Интересно, что это не работает для примера Maybe, описанного выше, потому что Haskell не знает, как объединить Int - следует ли использовать + или *? Чтобы получить экземпляр Monoid для числовых данных, вы завершаете их в Sum или Product, чтобы указать, какой моноид использовать.

Zip [Just (Sum 1),   Nothing,       Just (Sum 3), Just (Sum 4)] <> 
Zip [Just (Sum 40),  Just (Sum 70), Nothing]
= Zip [Just (Sum 41),Just (Sum 70), Just (Sum 3)]

   Zip [Product 5,Product 10,Product 15] 
<> Zip [Product 3, Product 4]
 =  Zip [Product 15,Product 40]

Ключевые моменты

Обратите внимание на тот факт, что тип в моноиде имеет вид *, что позволяет нам помещать здесь контекст Monoid a - мы могли бы также добавить Eq a или Ord a. В моноиде важны необработанные элементы. Экземпляр Monoid предназначен для управления и объединения данных внутри структуры.

Структура 2: выбор более высокого уровня: Альтернативный

Оператор выбора аналогичен, но также и другим.

Возможно, клон

(<||>) :: Perhaps String -> Perhaps String -> Perhaps String
Yes xs <||> Yes ys = Yes xs   -- if we can have both, choose the left one
Yes xs <||> No     = Yes xs
No     <||> Yes ys = Yes ys
No     <||> No     = No  

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

(<||>) :: Perhaps a -> Perhaps a -> Perhaps a
Yes xs <||> Yes ys = Yes xs   -- if we can have both, choose the left one
Yes xs <||> No     = Yes xs
No     <||> Yes ys = Yes ys
No     <||> No     = No  

Обратите внимание на отсутствие ограничений - мы не используем структуру с уровня a, просто структуру на уровне Perhaps. Это альтернативная структура.

instance Alternative Perhaps where
   (<|>) = (<||>)
   empty = No  

Клон ZipList

Как мы можем выбрать между двумя ziplists?

Zip [1,3,4] <|> Zip [10,20,30,40] = ????

Было бы очень заманчиво использовать <|> для элементов, но мы не можем, потому что тип элементов недоступен для нас. Начните с empty. Он не может использовать элемент, потому что мы не знаем тип элементов при определении Альтернативы, поэтому он должен быть Zip []. Нам нужно, чтобы он был левым (и предпочтительно правильным) идентификатором для <|>, поэтому

Zip [] <|> Zip ys = Zip ys
Zip xs <|> Zip [] = Zip xs

Есть два разумных выбора для Zip [1,3,4] <|> Zip [10,20,30,40]:

• Zip [1,3,4], потому что сначала - в соответствии с Maybe
• Zip [10,20,30,40], потому что он длиннее - в соответствии с Zip [] отбрасывается

Хорошо, что легко решить: поскольку pure x = Zip (repeat x), оба списка могут быть бесконечными, поэтому сравнение их длины может никогда не прекратиться, поэтому нужно выбрать первый. Таким образом, единственный разумный альтернативный пример:

instance Alternative Zip where
   empty = Zip []
   Zip [] <|> x = x
   Zip xs <|> _ = Zip xs

Это единственная разумная альтернатива, которую мы могли бы определить. Обратите внимание, насколько это отличается от экземпляра Monoid, потому что мы не могли возиться с элементами, мы даже не могли смотреть на них.

Ключевые точки

Обратите внимание, что, поскольку Alternative принимает конструктор вида * -> *, нет возможности добавить контекст Ord a или Eq a или Monoid a. Альтернатива не разрешена, чтобы использовать любую информацию о данных внутри структуры. Вы не можете, независимо от того, сколько вы хотели бы сделать, что-либо сделать с данными, за исключением, возможно, выбросить его.

Ключевые моменты: какая разница между альтернативой и моноидом?

Не много - они оба моноиды, но суммировать последние два раздела:

Monoid * экземпляры позволяют объединять внутренние данные. Alternative (* -> *) экземпляры делают невозможным. Monoid обеспечивает гибкость, Alternative предоставляет гарантии. Виды * и (* -> *) являются основными причинами этой разницы. Имея их оба, вы можете использовать оба вида операций.

Это правильная вещь, и наши два вкуса подходят друг другу. Экземпляр Monoid для Perhaps String представляет собой объединение всех символов, альтернативный экземпляр представляет собой выбор между строками.

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

Экземпляр Monoid для Zip объединяет его элементы. Альтернативный экземпляр для Zip вынужден выбрать один из списков - первый непустой.

Хорошо быть в состоянии сделать и то и другое.

Каким образом применимый контекст используется?

Там какое-то взаимодействие между выбором и применением. См. законы Антала S-Z, изложенные в его вопросе, или в середине его ответа здесь.

С практической точки зрения это полезно, потому что Alternative - это то, что используется для некоторых аппликативных функторов. Функциональность была использована для применения, и поэтому был изобретен общий класс интерфейса. Аппликативные функторы хороши для представления вычислений, которые производят значения (IO, Parser, Input UI element,...), а некоторые из них должны обрабатывать сбой - требуется альтернатива.

Почему альтернатива имеет empty?

зачем Альтернативе нужен пустой метод/член? Возможно, я ошибаюсь, но, похоже, он вообще не используется... по крайней мере, в коде, который я мог найти. И это, похоже, не соответствует теме класса - если у меня есть две вещи, и вам нужно выбрать один, для чего мне нужен "пустой" для?

Это, как и спрашивать, почему добавление нуждается в 0 - если вы хотите добавить что-то, то что нужно иметь что-то, что ничего не добавляет? Ответ заключается в том, что 0 - ключевое ключевое число, вокруг которого все вращается дополнительно, так же, как 1 имеет решающее значение для умножения, [] имеет решающее значение для списков (и y=e^x имеет решающее значение для исчисления). В практическом плане вы используете эти элементы do-nothing для запуска своего здания:

sum = foldr (+) 0
concat = foldr (++) []
msum = foldr (`mappend`) mempty          -- any Monoid
whichEverWorksFirst = foldr (<|>) empty  -- any Alternative

Не можем ли мы заменить MonadPlus на Monad + Alternative?

какая точка класса типа MonadPlus? Разве я не могу разблокировать все его доброту, просто используя что-то как Монаду и Альтернативу? Почему бы просто не остановить его? (Я уверен, что я ошибаюсь, но у меня нет контрпримеров)

Ты не ошибаешься, нет контрпримеров!

Ваш интересный вопрос получил Antal S-Z, Петр Пудлак, и я вникал в то, что на самом деле отношения между MonadPlus и Applicative. Ответ, здесь и здесь заключается в том, что все, что a MonadPlus (в левом смысле распределения - следуйте за ссылками для деталей) также является Alternative, но не наоборот.

Это означает, что если вы делаете экземпляр Monad и MonadPlus, он удовлетворяет условиям для Аппликации и Альтернативы в любом случае. Это означает, что если вы соблюдаете правила MonadPlus (слева), вы также можете сделать свою Монаду аппликативной и используемой Альтернативой.

Если мы удалим класс MonadPlus, мы удалим разумное место для документирования правил, и вы потеряете возможность указать что-то альтернативное без MonadPlus (что технически мы должны были сделать для Maybe). Это теоретические причины. Практическая причина заключается в том, что он нарушит существующий код. (Именно поэтому ни Аппликативные, ни Функторы не являются суперклассами Монады.)

Не являются альтернативными и моноидальными? Не являются ли альтернативы и моноиды совершенно разными?

"pedia" говорит, что "класс альтернативного типа предназначен для аппликативных функторов, которые также имеют моноидную структуру". Я не понимаю, не означает ли альтернатива что-то совершенно отличное от Monoid? т.е. я понял смысл класса типа Alternative как выбор между двумя вещами, тогда как я понял, что моноиды связаны с объединением вещей.

Моноид и альтернатива - два способа получить один объект из двух разумным способом. Математики не заботятся о том, выбираете ли вы, комбинируете, смешиваете или взрываете свои данные, поэтому Alternative была названа моноидой для аппликации. Теперь вы, кажется, дома с этой концепцией, но теперь говорите

для типов, имеющих экземпляр Alternative и Monoid, экземпляры должны быть одинаковыми

Я не согласен с этим, и я думаю, что мои примеры Maybe и ZipList тщательно объясняются, почему они разные. Во всяком случае, я думаю, что это должно быть редко, что они одинаковы. Я могу только думать о одном примере, простых списках, где это уместно. Это потому, что списки являются фундаментальным примером моноида с ++, но также списки используются в некоторых контекстах как неопределенный выбор элементов, поэтому <|> также должен быть ++.

Ответ 4

Резюме

• Нам нужно определить (экземпляры, которые предоставляют те же операции, что и) экземпляры Monoid для некоторых аппликативных функторов, которые действительно объединяются на уровне аппликативного функтора, а не просто поднимают моноиды нижнего уровня. Пример ошибки ниже litvar = liftA2 mappend literal variable показывает, что <|> вообще не может быть определен как liftA2 mappend; <|> работает в этом случае путем объединения парсеров, а не их данных.

• Если мы использовали Monoid напрямую, нам нужны языковые расширения для определения экземпляров. Alternative более высокий, поэтому вы можете создавать эти экземпляры, не требуя языковых расширений.

Пример: Parsers

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

import Text.Parsec
import Text.Parsec.String
import Control.Applicative ((<$>),(<*>),liftA2,empty)
import Data.Monoid
import Data.Char

и подумайте о том, как мы будем разбирать тип. Выберем упрощенное:

data Type = Literal String | Variable String  deriving Show
examples = [Literal "Int",Variable "a"]

Теперь напишите синтаксический анализатор для литералов:

literal :: Parser Type
literal = fmap Literal $ (:) <$> upper <*> many alphaNum

Значение: parse a upper case character, затем many alphaNum eric символы, объединяют результаты в одну строку с чистой функцией (:). Затем примените чистую функцию Literal, чтобы превратить те String в Type s. Мы будем разбирать типы переменных точно так же, за исключением начала с буквой case lower:

variable :: Parser Type
variable = fmap Variable $ (:) <$> lower <*> many alphaNum

Это здорово, и parseTest literal "Bool" == Literal "Bool" точно так, как мы надеялись.

Вопрос 3a: Если он сочетает аппликативные эффекты с поведением Monoid, почему бы не просто liftA2 mappend

Изменить: Oops - забыли использовать <|>!

Теперь позвольте объединить эти два парсера с помощью Alternative:

types :: Parser Type
types = literal <|> variable

Это может анализировать любой тип: parseTest types "Int" == Literal "Bool" и parseTest types "a" == Variable "a". Это объединяет два парсера, а не два значения. Тот смысл, в котором он работает на уровне Applicative Functor, а не на уровне данных.

Однако, если мы попытаемся:

litvar = liftA2 mappend literal variable

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

No instance for (Monoid Type)
  arising from a use of `mappend'
Possible fix: add an instance declaration for (Monoid Type)
In the first argument of `liftA2', namely `mappend'
In the expression: liftA2 mappend literal variable
In an equation for `litvar':
    litvar = liftA2 mappend literal variable

Итак, мы выяснили первое; Альтернативный класс делает что-то действительно отличное от liftA2 mappend, потому что он объединяет объекты на другом уровне - он объединяет синтаксические анализаторы, а не анализируемые данные. Если вам нравится думать об этом таким образом, это сочетание на действительно высоком уровне, а не просто лифте. Мне не нравится говорить это так, потому что Parser Type имеет добрый *, но верно, что мы объединяем Parser s, а не Type s.

(Даже для типов с экземпляром Monoid, liftA2 mappend не даст вам тот же синтаксический анализатор, что и <|>. Если вы попробуете его на Parser String, вы получите liftA2 mappend, который анализирует один за другим, тогда concatenates, по сравнению с <|>, который попытается использовать первый синтаксический анализатор и по умолчанию будет вторым, если он не удался.)

Вопрос 3b: Чем альтернатива <|> :: f a -> f a -> f a отличается от Monoid mappend :: b -> b -> b?

Во-первых, вы правильно заметили, что он не предоставляет новые функции над экземпляром Monoid.

Во-вторых, однако, проблема с использованием Monoid напрямую: Попробуем использовать mappend для парсеров, в то же время показывая ему ту же структуру, что и Alternative:

instance Monoid (Parser a) where
    mempty = empty
    mappend = (<|>)

Oops! Получаем

Illegal instance declaration for `Monoid (Parser a)'
  (All instance types must be of the form (T t1 ... tn)
   where T is not a synonym.
   Use -XTypeSynonymInstances if you want to disable this.)
In the instance declaration for `Monoid (Parser a)'

Итак, если у вас есть аппликативный функтор f, экземпляр Alternative показывает, что f a является моноидом, но вы можете только объявить это как Monoid с расширением языка.

Как только мы добавим {-# LANGUAGE TypeSynonymInstances #-} в начало файла, мы в порядке и можем определить

typeParser = literal `mappend` variable

и к нашему удовольствию, он работает: parseTest typeParser "Yes" == Literal "Yes" и parseTest typeParser "a" == Literal "a".

Даже если у вас нет синонимов (Parser и String являются синонимами, поэтому они отсутствуют), вам все равно потребуется {-# LANGUAGE FlexibleInstances #-}, чтобы определить экземпляр, подобный этому:

data MyMaybe a = MyJust a | MyNothing deriving Show
instance Monoid (MyMaybe Int) where
   mempty = MyNothing
   mappend MyNothing x = x
   mappend x MyNothing = x
   mappend (MyJust a) (MyJust b) = MyJust (a + b)

(Моноидный экземпляр Maybe может обойти это, сняв основной моноид.)

Создание стандартной библиотеки, излишне зависящей от языковых расширений, явно нежелательно.

Итак, у вас это есть. Альтернатива - это просто моноид для аппликативных функторов (и это не просто лифтинг моноида). Он нуждается в более высоком типе f a -> f a -> f a, чтобы вы могли определить один без языковых расширений.

Ваши другие вопросы, для полноты:

• Почему Alternative нужен пустой метод/член?
  Потому что иногда бывает полезно иметь идентификатор для операции. Например, вы можете определить anyA = foldr (<|>) empty без использования утомительных случаев.

• какая точка класса типа MonadPlus? Разве я не могу разблокировать все его доброту, просто используя что-то как Монаду и Альтернативу? Нет. Я отсылаю вас к вопросу который вы связали с:

Кроме того, даже если Applicative был суперклассом Monad, вы все равно нуждаетесь в классе MonadPlus, потому что подчинение empty <*> m = empty не является достаточно строгим, чтобы доказать, что empty >>= f = empty.

.... и я придумал пример: Может быть. Я объясняю подробно, с доказательством в этом ответе на вопрос Анталя. Для целей этого ответа стоит отметить, что я смог использовать → =, чтобы сделать экземпляр MonadPlus, который нарушил альтернативные законы.

Моноидная структура полезна. Альтернатива - лучший способ предоставить его для аппликативных функторов.

Ответ 5

Я понял смысл класса Alternative type как выбор между двумя вещами, тогда как я понял, что моноиды связаны с объединением вещей.

Если вы думаете об этом на мгновение, они будут одинаковыми.

+ объединяет вещи (обычно числа), а подпись типа Int -> Int -> Int (или что-то еще).

Оператор <|> выбирает между альтернативами, а подпись типа тоже одинакова: возьмите две подходящие вещи и верните комбинированную вещь.