Смущен значением класса типа 'Alternative' и его отношением к классам других типов

Question

Смущен значением класса типа 'Alternative' и его отношением к классам других типов

Я изучал Typeclassopedia, чтобы выучить классы типов. Я застрял понимание Alternative (а также MonadPlus, в этом отношении).

Проблемы, которые у меня возникают:

"Педиа" говорит, что "класс альтернативных типов предназначен для аппликативных функторов, которые также имеют моноидную структуру". Я не понимаю, не означает ли "Альтернатива" нечто совершенно отличное от "Моноида"? то есть я понимал смысл класса типа Alternative как выбор между двумя вещами, тогда как я понимал моноиды как объединение вещей.
почему Альтернатива нужна empty Способ / член? Возможно, я ошибаюсь, но, похоже, он вообще не используется... по крайней мере, в коде, который я смог найти. И это, кажется, не соответствует теме класса - если у меня есть две вещи, и мне нужно выбрать одну, для чего мне нужен "пустой"?
почему классу типа Alternative требуется аппликативное ограничение, и почему ему нужен вид * -> *? Почему бы просто не иметь <|> :: a -> a -> a? Все экземпляры могут быть реализованы одинаково... Я думаю (не уверен). Какую ценность это обеспечивает, что Monoid не делает?
какой смысл MonadPlus тип класс? Разве я не могу открыть все его достоинства, просто используя что-то как Monad а также Alternative? Почему бы просто не бросить это? (Я уверен, что ошибаюсь, но у меня нет контрпримеров)

Надеюсь, все эти вопросы являются связными...!

Обновление Bounty: @ Ответ Антала - отличное начало, но Q3 все еще открыт: что предлагает Альтернатива, чего нет у Monoid? Я нахожу этот ответ неудовлетворительным, поскольку в нем отсутствуют конкретные примеры и конкретное обсуждение того, как высшая доброта Альтернативы отличает его от моноида.

Если это объединить аппликативные эффекты с поведением Моноида, почему бы просто:

liftA2 mappend

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

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

76

haskell typeclass

Источник

user894284 26 окт '12 в 04:11

5 ответов

Решение

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

Нет, 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 ₃).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Что ж, давайте рассмотрим каждое из этих трех предложенных изменений: избавление от Applicative ограничение для Alternative; меняя вид Alternative аргумент; и используя 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? Нет, но это то, к чему приведет приведенный выше код. Мы хотим получить моноидный экземпляр, который не зависит от внутреннего типа (заимствуя терминологию у Мэтью Фаркаша-Дика в очень связанном обсуждении в haskell-cafe, где задаются некоторые очень похожие вопросы); Alternative структура около моноида определяется f структура, а не структура f аргумент.

Теперь, когда мы думаем, что хотим уйти Alternative как некоторый класс типов, давайте посмотрим на два предложенных способа его изменения. Если мы изменим вид, мы должны избавиться от Applicative ограничение; Applicative говорит только о вещах * -> * и поэтому нет никакого способа сослаться на это. Это оставляет два возможных изменения; первое, более незначительное изменение состоит в том, чтобы избавиться от 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 нет, и я думаю (по причинам, которые станут понятны в следующих парах параграфов), лучше этого не требовать.

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

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

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

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

Левое почти полукольцо определяется аналогично.

Теперь это не совсем работает, потому что <*> не является действительно ассоциативным или бинарным оператором - типы не совпадают. Я думаю, что это то, к чему стремится Эдвард Кметт, когда он говорит об "отбрасывании аргумента". Другой вариант - сказать (я не уверен, что это правильно), что мы на самом деле хотим (f a, <|>, <*>, empty), чтобы образовать правый околополухериноид, где суффикс "-oid" указывает, что бинарные операторы могут применяться только к определенным парам элементов (например, группоиды). И мы также хотели бы сказать, что (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, которое я упоминал в начале этого раздела, предлагает изменить это, есть 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 Это хорошо. Слайды Эдварда Кметта, упомянутые выше, не ссылаются на <$>, но я думаю, что разумно требовать и законов в отношении этого; тем не менее, я не могу найти ничего, чтобы поддержать меня в этом.

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

Какой смысл MonadPlus тип класс?

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

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

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

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

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

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

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

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

92

Источник

user237428 26 окт '12 в 06:03

import Data.Monoid
import Control.Applicative

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

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

Вот клон Maybe:

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: комбинирующие элементы: моноид

Может быть клон

Сначала давайте посмотрим на 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

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

(<++>) :: 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

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

Интересно, что это не работает для приведенного выше примера Maybe, потому что Haskell не знает, как комбинировать Int s - это должно использовать + или же *? Чтобы получить экземпляр 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 имеет вид * это именно то, что позволяет нам поставить 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] потому что это первое - в соответствии с Возможно
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 для Perhaps String представляет собой объединение всех символов, экземпляр Alternative представляет выбор между строками.

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

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

Это хорошо, чтобы быть в состоянии сделать оба.

Для чего нужен Аппликативный контекст?

Есть некоторое взаимодействие между выбором и применением. Смотрите законы Antal SZ, изложенные в его вопросе или в середине его ответа здесь.

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

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

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

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

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

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

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

Вы не ошиблись, контрпримеров нет!

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

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

Однако если мы удаляем класс MonadPlus, мы удаляем разумное место для документирования правил, и вы теряете возможность указывать этот альтернативный вариант, не являясь MonadPlus (что технически мы должны были бы сделать для Maybe). Это теоретические причины. Практическая причина в том, что это сломало бы существующий код. (Именно поэтому ни Applicative, ни Functor не являются суперклассами Monad.)

Разве Альтернатива и Моноид не одно и то же? Разве Альтернатива и Моноид не абсолютно разные?

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

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

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

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

20

Источник

user1598537 01 ноя '12 в 10:03

Резюме

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

Пример: парсеры

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

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

Значение: разобрать upperрегистр символов, то many alphaNumeric символов, объединить результаты в одну строку с чистой функцией (:), Затем примените чистую функцию Literal превратить эти Stringс в Types. Мы будем анализировать типы переменных точно так же, за исключением того, что начинаем с lowerбуква:

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

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

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

Редактировать: Ой - забыл на самом деле использовать <|>!
Теперь давайте скомбинируем эти два парсера, используя 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с, а не Types.

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

Вопрос 3b: Каким образом Альтернативы `<|> :: f a -> f a -> f a` отличаются от моноида `mappend :: b -> b -> b`?

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

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

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

К сожалению! Мы получаем

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 так что вы можете определить один без языковых расширений.

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

Почему Альтернативе нужен пустой метод / член?
Потому что наличие идентификатора для операции иногда полезно. Например, вы можете определить anyA = foldr (<|>) empty без использования утомительных крайних случаев.
какой смысл в классе типов MonadPlus? Разве я не могу раскрыть все его достоинства, просто используя что-то как Монаду и Альтернативу? Нет. Я возвращаю вас к вопросу, с которым вы связались:

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

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

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

8

Источник

user1598537 29 окт '12 в 02:30

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

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

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

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

2

Источник

user1006010 26 окт '12 в 12:00

Другие вопросы по тегам haskell typeclass

user894284 31 окт '12 в 22:44 2012-10-31 22:44 · Accepted Answer · 2012-10-31 22:44

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

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

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

стандартный экземпляр Maybe для Monoid предполагает, что внутренний тип Monoid =>, а не Alternative
ZipLists, кортежи и функции могут быть сделаны Monoids, если их внутренними типами являются Monoids => not Alternatives
последовательности, которые имеют хотя бы один элемент - не могут быть альтернативами, потому что нет empty:
```
data Seq a
    = End a
    | Cons a (Seq a)
  deriving (Show, Eq, Ord)
```

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

единица измерения -- ()
Ordering
числа, логические

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

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

Смущен значением класса типа 'Alternative' и его отношением к классам других типов

5 ответов

Структура 1: комбинирующие элементы: моноид

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

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

Для чего нужен Аппликативный контекст?

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

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

Разве Альтернатива и Моноид не одно и то же? Разве Альтернатива и Моноид не абсолютно разные?

Резюме

Пример: парсеры

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

Вопрос 3b: Каким образом Альтернативы <|> :: f a -> f a -> f a отличаются от моноида mappend :: b -> b -> b?

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

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

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

Вопрос 3b: Каким образом Альтернативы `<|> :: f a -> f a -> f a` отличаются от моноида `mappend :: b -> b -> b`?