Верно ли мое понимание моноида?
Итак, сейчас я изучаю Хаскель, и я хотел бы подтвердить или опровергнуть мое понимание моноида.
Из курса CIS194 я понял, что monoid - это, по сути, "API" для определения пользовательской двоичной операции над пользовательским набором.
Затем я пошла, чтобы проинформировать себя, и наткнулась на огромное количество очень запутанных уроков, пытающихся прояснить ситуацию, так что я больше не уверена.
У меня приличный математический фон, но я просто запутался во всех метафорах и ищу четкий ответ да / нет на мое понимание моноида.
3 ответа
В абстрактной алгебре, ветви математики, моноид представляет собой алгебраическую структуру с одной ассоциативной двоичной операцией и единичным элементом.
Я думаю, что ваше понимание верно. С точки зрения программирования, Monoid представляет собой интерфейс с двумя "методами", которые должны быть реализованы.
Единственный фрагмент, который, по-видимому, отсутствует в вашем описании - это "идентичность", без которой вы описываете полугруппу.
Все, что имеет "ноль" или "пусто" и способ объединения двух значений, может быть моноидом. Следует отметить, что для набора / типа может быть возможно сделать Monoid более чем одним способом, например, числами через addition с личностью 0, или же multiplication с личностью 1,
От Вольфрама:
Моноид - это множество, замкнутое относительно ассоциативной бинарной операции и имеющее единичный элемент I в S, такой что для всех a в S Ia=aI=a.
из вики:
В абстрактной алгебре, ветви математики, моноид представляет собой алгебраическую структуру с одной ассоциативной двоичной операцией и единичным элементом.
так что ваша интуиция более или менее верна.
Вы должны только помнить, что он не определен для "пользовательского набора" в Haskell, а для типа. Различие небольшое (потому что типы в теории типов очень похожи на наборы в теории множеств), но типы, для которых вы можете определить экземпляр Monoid, не обязательно должны быть типами, представляющими математические множества.
Другими словами: тип описывает набор всех значений этого типа. Monoid - это "интерфейс", который утверждает, что любой тип, который утверждает, что придерживается этого интерфейса, должен предоставлять значение идентификатора, двоичную операцию, объединяющую два значения этого типа, и существуют некоторые уравнения, которым они должны удовлетворять, чтобы все общие операции Monoid могли работать по назначению (например, общее суммирование списка значений моноидов) и не давать нелогичных / противоречивых результатов.
Также обратите внимание, что наличие элемента идентичности в этом наборе (типе) требуется для того, чтобы тип был экземпляром класса Monoid.
Например, натуральные числа образуют моноид при обоих сложении (identity = 0):
0 + n = n
n + 0 = n
а также умножение (личность = 1):
1 * n = n
n * 1 = n
также списки образуют моноид под ++ (личность = []):
[] ++ xs = xs
xs ++ [] = xs
также функции типа a -> a образуют моноид под композицией (идентичность = id)
id . f = f
f . id = f
поэтому важно иметь в виду, что Monoid не о типах, которые представляют наборы, а о типах, которые рассматриваются как наборы, так сказать.
В качестве примера неправильно построенного экземпляра Monoid рассмотрим:
import Data.Monoid
newtype MyInt = MyInt Int deriving Show
instance Monoid MyInt where
mempty = MyInt 0
mappend (MyInt a) (MyInt b) = MyInt (a * b)
если вы сейчас попытаетесь mconcat список MyInt ценности, вы всегда получите MyInt 0 в результате, потому что значение идентичности 0 и бинарная операция * не играйте хорошо вместе
λ> mconcat [MyInt 1, MyInt 2]
MyInt 0
На базовом уровне вы правы - это просто API для бинарного оператора, который мы обозначим как <>,
Однако ценность моноидного понятия заключается в его связи с другими типами и классами. В культурном плане мы решили, что <> это естественный способ соединения / добавления двух вещей одного типа вместе.
Рассмотрим этот пример:
{-# LANGUAGE OverloadedStrings #-}
import Data.Monoid
greet x = "Hello, " <> x
Функция greet чрезвычайно полиморфный - x может быть String, ByteString или Text, просто чтобы назвать несколько возможностей. Более того, в каждом из этих случаев он делает в основном то, что вы ожидаете - он добавляет x в строку `" Привет ".
Кроме того, существует множество алгоритмов, которые будут работать со всем, что может быть накоплено, и они являются хорошими кандидатами для обобщения на моноид. Например, рассмотрим foldMap функция от Foldable учебный класс:
foldMap :: Monoid m => (a -> m) -> t a -> m
Не только делает foldMap обобщить идею сворачивания над структурой, но я могу обобщить, как выполняется накопление, заменив правильный экземпляр Monoid.
Если у меня складная конструкция t содержащие Ints, я могу использовать foldMap с Sum моноид, чтобы получить сумму Ints, или с Product чтобы получить продукт и т. д.
Наконец, используя <> предоставляет удобство. Например, существует множество различных реализаций Set, но для всех них s <> t всегда объединение двух множеств s а также t (того же типа). Это позволяет мне писать код, который не зависит от базовой реализации набора, тем самым упрощая мой код. То же самое можно сказать и о многих других структурах данных, например, последовательностях, деревьях, картах, приоритетных очередях и т. Д.