Хорошие примеры не функтор / функтор / аппликатив / монада?

210

Объясняя кому-то, что такое класс типов X, я стараюсь найти хорошие примеры структур данных, которые в точности X.

Итак, я прошу примеры для:

  • Конструктор типа, который не является Functor.
  • Конструктор типа, который является Functor, но не Applicative.
  • Конструктор типа, который является Аппликативным, но не Монадой.
  • Конструктор типа, который является Монадой.

Я думаю, что есть множество примеров Монады повсюду, но хороший пример Монады с некоторым отношением к предыдущим примерам может завершить картину.

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

Если бы кто-нибудь смог подобрать пример Arrow где-нибудь в этой иерархии (это между Applicative и Monad?), Это тоже было бы здорово!

Rotsor
источник
4
Можно ли сделать конструктор типа ( * -> *) , для которого не существует не подходит fmap?
Оуэн
1
Оуэн, я думаю a -> String, не функтор.
Ротсор
3
@Rotsor @Owen a -> String- математический функтор, но не Хаскелл Functor, чтобы быть ясным.
Дж. Абрахамсон
@J. Абрахамсон, в каком смысле это математический функтор? Вы говорите о категории с перевернутыми стрелками?
Ротсор
4
Для людей, не знающих, у контравариантного функтора есть fmap типа(a -> b) -> f b -> f a
AJFarmar

Ответы:

100

Конструктор типа, который не является Functor:

newtype T a = T (a -> Int)

Из него можно сделать контравариантный функтор, но не (ковариантный) функтор. Попробуйте написать, fmapи у вас ничего не получится. Обратите внимание, что версия контравариантного функтора обратная:

fmap      :: Functor f       => (a -> b) -> f a -> f b
contramap :: Contravariant f => (a -> b) -> f b -> f a

Конструктор типа, который является функтором, но не Applicative:

У меня нет хорошего примера. Да Const, но в идеале я бы хотел конкретный немоноид, и ни о чем не могу думать. Все типы в основном числовые, перечисления, продукты, суммы или функции, когда вы приступаете к этому. Вы можете увидеть ниже свиновод, и я не согласен с тем, Data.Voidявляется ли это Monoid;

instance Monoid Data.Void where
    mempty = undefined
    mappend _ _ = undefined
    mconcat _ = undefined

Поскольку _|_в Хаскеле это является юридической ценностью и фактически единственной юридической ценностью Data.Void, это соответствует правилам Моноида. Я не уверен, что unsafeCoerceс этим делать, потому что ваша программа больше не гарантирует, что не нарушит семантику Haskell, как только вы используете какую-либо unsafeфункцию.

Обратитесь к Haskell Wiki за статьей о нижних ( ссылка ) или небезопасных функциях ( ссылка ).

Интересно, возможно ли создать такой конструктор типов, используя более богатую систему типов, такую ​​как Agda или Haskell с различными расширениями.

Конструктор типа, который является Аппликативным, но не Монадой:

newtype T a = T {multidimensional array of a}

Вы можете сделать аппликатив из этого, например:

mkarray [(+10), (+100), id] <*> mkarray [1, 2]
  == mkarray [[11, 101, 1], [12, 102, 2]]

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

Конструктор типа, который является Монадой:

[]

О Стрелках:

Спрашивать, где находится Стрелка в этой иерархии, все равно, что спрашивать, что это за форма "красная". Обратите внимание на несоответствие:

Functor :: * -> *
Applicative :: * -> *
Monad :: * -> *

но,

Arrow :: * -> * -> *
Дитрих Эпп
источник
3
Хороший список! Я бы предложил использовать что-то более простое, например, Either aв качестве примера для последнего случая, так как это легче понять.
fuz
6
Если вы все еще ищете конструктор типов, который является Applicative, но не Monad, очень распространенным примером будет ZipList.
Джон Л
23
_|_Обитает в каждом типе *, но суть в Voidтом, что вам придется наклониться назад, чтобы создать его, или вы уничтожили его значение. Вот почему это не экземпляр Enum, Monoid и т. Д. Если он у вас уже есть, я с удовольствием позволю вам объединить их вместе (давая вам Semigroup) mempty, но я не даю инструментов для явного построения значения типа Voidв void, Вы должны зарядить пистолет, направить его на ногу и самостоятельно нажать на курок.
Эдвард КМЕТТ
2
Педантично, я думаю, что ваше представление о Cofunctor неверно. Двойник функтора - это функтор, потому что вы переворачиваете и вход, и выход и в итоге получаете одно и то же. Понятие, которое вы ищете, вероятно, «контравариантный функтор», который немного отличается.
Бен Милвуд
1
@AlexVong: «Устаревший» -> люди просто используют другой пакет. Говоря о «контравариантном функторе», а не о «двойственном функторе», извините за путаницу. В некоторых контекстах я видел, что «cofunctor» использовался для обозначения «контравариантных функторов», потому что функторы самодвойственны, но, похоже, просто сбивают с толку людей.
Дитрих Эпп
87

Мой стиль может быть ограничен моим телефоном, но здесь идет.

newtype Not x = Kill {kill :: x -> Void}

не может быть Функтором. Если бы это было, мы бы

kill (fmap (const ()) (Kill id)) () :: Void

и Луна будет сделана из зеленого сыра.

между тем

newtype Dead x = Oops {oops :: Void}

это функтор

instance Functor Dead where
  fmap f (Oops corpse) = Oops corpse

но не может быть аппликативным, иначе мы бы

oops (pure ()) :: Void

и Зеленый будет сделан из лунного сыра (что может произойти, но только позже вечером).

(Дополнительное примечание: Voidпоскольку Data.Voidэто пустой тип данных. Если вы попытаетесь использовать, undefinedчтобы доказать, что это моноид, я буду использовать, unsafeCoerceчтобы доказать, что это не так.)

радостно,

newtype Boo x = Boo {boo :: Bool}

является аппликативным во многих отношениях, например, как это было бы у Дейкстры,

instance Applicative Boo where
  pure _ = Boo True
  Boo b1 <*> Boo b2 = Boo (b1 == b2)

но это не может быть монадой. Чтобы понять, почему нет, обратите внимание, что возвращение должно быть постоянно Boo Trueили Boo False, и, следовательно, что

join . return == id

не может удержаться.

О да я чуть не забыл

newtype Thud x = The {only :: ()}

это монада Катайся сам.

Самолет, чтобы поймать ...

pigworker
источник
8
Пустота пуста! Во всяком случае, морально.
свиновод
9
Я полагаю, что Void - это тип с 0 конструкторами. Это не моноид, потому что нет mempty.
Rotsor
6
не определено? Как грубо! К сожалению, unsafeCoerce (unsafeCoerce () <*> undefined) не является (), поэтому в реальной жизни существуют наблюдения, которые нарушают законы.
свиновод
5
В обычной семантике, которая допускает ровно один неопределенный вид, вы совершенно правы. Конечно, есть и другие семантики. Пустота не ограничивается субмоноидом в общем фрагменте. И при этом это не моноид в семантике, которая различает способы неудачи. Когда у меня появится момент с более простым редактированием, чем по телефону, я поясню, что мой пример работает только в семантике, для которой точно не существует одного вида неопределенности.
свиновод
22
Много шума из_|_
Landei
71

Я полагаю, что другие ответы пропустили несколько простых и распространенных примеров:

Конструктор типа, который является Functor, но не Applicative. Простой пример - пара:

instance Functor ((,) r) where
    fmap f (x,y) = (x, f y)

Но нет способа определить его Applicativeэкземпляр без наложения дополнительных ограничений на r. В частности, нет способа, как определить pure :: a -> (r, a)для произвольного r.

Конструктор типа, который является Аппликативным, но не Монадой. Хорошо известным примером является ZipList . (Это newtypeобертка списков и предоставляет им другой Applicativeэкземпляр.)

fmapопределяется обычным способом. Но pureи <*>определяются как

pure x                    = ZipList (repeat x)
ZipList fs <*> ZipList xs = ZipList (zipWith id fs xs)

поэтому pureсоздает бесконечный список путем повторения заданного значения и <*>архивирует список функций со списком значений - применяет i-ю функцию к i- му элементу. (Стандарт <*>на []производит все возможные комбинации применения I ую функции J -му элемент.) Но нет разумного способа , как определить монады (см этого поста ).


Как стрелки вписываются в иерархию функтор / аппликатив / монад? Видите, идиомы не обращают внимания, стрелки дотошны, монады неразборчивы от Сэма Линдли, Филиппа Уодлера, Джереми Яллопа. MSFP 2008. (Они называют аппликативные функторы идиомами .) Аннотация:

Мы вновь рассмотрим связь между тремя понятиями вычислений: монады Могги, стрелки Хьюза и идиомы Макбрайда и Патерсона (также называемые аппликативными функторами). Покажем, что идиомы эквивалентны стрелкам, удовлетворяющим изоморфизму типа A ~> B = 1 ~> (A -> B), и что монады эквивалентны стрелкам, удовлетворяющим изоморфизму типа A ~> B = A -> (1 ~ > Б). Кроме того, идиомы встраиваются в стрелки, а стрелки - в монады.

Петр Пудлак
источник
1
Так ((,) r)что функтор не аппликативен; но это только потому, что вы не можете определить pureдля всех rсразу. Следовательно, это причудливость языковой лаконичности, попытки определить (бесконечный) набор аппликативных функторов с одним определением pureи <*>; в этом смысле, как представляется , не будет ничего математически глубоко об этом контрпример , так как для любого бетона r, ((,) r) может быть аппликативном функтор. Вопрос: Можете ли вы вспомнить функтор КОНКРЕТНЫЙ, который не является аппликативным?
Джордж
1
См. Stackoverflow.com/questions/44125484/… как сообщение с этим вопросом.
Джордж
21

Хороший пример для конструктора типа, который не является функтором Set: Вы не можете реализовать fmap :: (a -> b) -> f a -> f b, потому что без дополнительного ограничения Ord bвы не можете создать f b.

Landei
источник
16
На самом деле это хороший пример, поскольку математически нам бы очень хотелось сделать это функтором.
Александр С.
21
@AlexandreC. Я бы не согласился с этим, это не хороший пример. Математически такая структура данных формирует функтор. Тот факт, что мы не можем реализовать, fmapявляется просто вопросом языка / реализации. Кроме того, можно обернуть Setв монаду продолжения, которая делает из нее монаду со всеми ожидаемыми свойствами, см. Этот вопрос (хотя я не уверен, что это можно сделать эффективно).
Петр Пудлак
@PetrPudlak, как это языковой вопрос? Равенство bможет быть неразрешимым, в этом случае вы не можете определить fmap!
Turion
@ Турион Быть решаемым и определяемым - это две разные вещи. Например, можно правильно определить равенство в лямбда-терминах (программах), даже если это невозможно решить с помощью алгоритма. В любом случае, это был не случай этого примера. Здесь проблема в том, что мы не можем определить Functorэкземпляр с Ordограничением, но это может быть возможно при другом определении Functorили лучшей языковой поддержке. На самом деле с ConstraintKinds можно определить класс типа, который можно параметризовать следующим образом.
Петр Пудлак
Даже если мы сможем преодолеть ordограничение, тот факт, что a Setне может содержать повторяющиеся записи, означает, что это может изменить fmapконтекст. Это нарушает закон ассоциативности.
Джон Ф. Миллер
12

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

Когда конструкторы типов не могут иметь экземпляры классов типов?

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

  1. Невозможно реализовать сигнатуры типов необходимых методов из класса типов.
  2. Может реализовывать подписи типа, но не может соответствовать требуемым законам.

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

Конкретные примеры

  • Конструктор типа, который не может иметь экземпляр functor, потому что тип не может быть реализован:

    data F z a = F (a -> z)

Это контрафунктор, а не функтор, относительно параметра типа a, потому что он находится aв контравариантной позиции. Невозможно реализовать функцию с сигнатурой типа (a -> b) -> F z a -> F z b.

  • Конструктор типа, который не является законным функтором, даже если сигнатура типа fmapможет быть реализована:

    data Q a = Q(a -> Int, a)
    fmap :: (a -> b) -> Q a -> Q b
    fmap f (Q(g, x)) = Q(\_ -> g x, f x)  -- this fails the functor laws!

Любопытный аспект этого примера заключается в том, что мы можем реализовать fmapправильный тип, даже если он Fне может быть функтором, потому что он используется aв противоположной позиции. Таким образом, эта реализация, fmapпоказанная выше, вводит в заблуждение - даже если она имеет правильную сигнатуру типа (я считаю, что это единственно возможная реализация этой сигнатуры типа), законы функторов не выполняются. Например, fmap idid, потому что let (Q(f,_)) = fmap id (Q(read,"123")) in f "456"есть 123, но let (Q(f,_)) = id (Q(read,"123")) in f "456"есть 456.

На самом деле, Fэто всего лишь профессор, он не является ни функтором, ни контрафунктором.

  • Законный функтор, который не является аппликативным, потому что сигнатура типа pureне может быть реализована: возьмите монаду Writer (a, w)и удалите ограничение, которое wдолжно быть моноидом. Тогда невозможно построить значение типа (a, w)из a.

  • Функтор , который не аппликативен , так как тип подпись <*>не может быть реализована: data F a = Either (Int -> a) (String -> a).

  • Функтор, который не является законно-аппликативным, хотя могут быть реализованы методы класса типов:

    data P a = P ((a -> Int) -> Maybe a)

Конструктор типов Pявляется функтором, потому что он используется aтолько в ковариантных позициях.

instance Functor P where
   fmap :: (a -> b) -> P a -> P b
   fmap fab (P pa) = P (\q -> fmap fab $ pa (q . fab))

Единственная возможная реализация сигнатуры типа <*>- это функция, которая всегда возвращает Nothing:

 (<*>) :: P (a -> b) -> P a -> P b
 (P pfab) <*> (P pa) = \_ -> Nothing  -- fails the laws!

Но эта реализация не удовлетворяет закону тождества для аппликативных функторов.

  • Функтор, который Applicativeне является,Monad потому что сигнатура типа bindне может быть реализована.

Я не знаю таких примеров!

  • Функтор, который является, Applicativeно неMonad потому, что законы не могут быть выполнены, даже если подпись типа bindможет быть реализована.

Этот пример вызвал немало дискуссий, поэтому можно с уверенностью сказать, что доказать правильность этого примера непросто. Но несколько человек подтвердили это независимо разными способами. См. `Данные PoE a = Пусто | Пара монад? для дополнительного обсуждения.

 data B a = Maybe (a, a)
   deriving Functor

 instance Applicative B where
   pure x = Just (x, x)
   b1 <*> b2 = case (b1, b2) of
     (Just (x1, y1), Just (x2, y2)) -> Just((x1, x2), (y1, y2))
     _ -> Nothing

Несколько громоздко доказать, что законного Monadпримера нет. Причиной немонадного поведения является то, что не существует естественного способа реализации, bindкогда функция f :: a -> B bможет возвращать Nothingили Justдля других значений a.

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

 join :: Maybe (Maybe (a, a, a), Maybe (a, a, a), Maybe (a, a, a)) -> Maybe (a, a, a)
 join Nothing = Nothing
 join Just (Nothing, Just (x1,x2,x3), Just (y1,y2,y3)) = ???
 join Just (Just (x1,x2,x3), Nothing, Just (y1,y2,y3)) = ???
 -- etc.

В случаях, обозначенных как ???, кажется очевидным, что мы не можем производить Just (z1, z2, z3)разумным и симметричным способом из шести различных значений типа a. Конечно, мы могли бы выбрать какое-то произвольное подмножество этих шести значений, например, всегда брать первое непустое значение, Maybeно это не удовлетворяло бы законам монады. Возвращение Nothingтакже не будет соответствовать законам.

  • Древовидная структура данных, которая не является монадой, хотя и имеет ассоциативность, bindно не соответствует законам идентичности.

Обычная древовидная монада (или «дерево с ветвями в форме функтора») определяется как

 data Tr f a = Leaf a | Branch (f (Tr f a))

Это бесплатная монада над функтором f. Форма данных представляет собой дерево, где каждая точка ветвления является «функторной» из поддеревьев. Стандартное двоичное дерево будет получено с type f a = (a, a).

Если мы изменим эту структуру данных, сделав также листья в форме функтора f, мы получим то, что я называю «полумонадой» - она ​​имеет bindто, что удовлетворяет законам естественности и ассоциативности, но ее pureметод не соответствует одному из законов идентичности. «Полумонады - это полугруппы в категории эндофункторов, в чем проблема?» Это тип класса Bind.

Для простоты я определяю joinметод вместо bind:

 data Trs f a = Leaf (f a) | Branch (f (Trs f a))
 join :: Trs f (Trs f a) -> Trs f a
 join (Leaf ftrs) = Branch ftrs
 join (Branch ftrstrs) = Branch (fmap @f join ftrstrs)

Прививка веток стандартная, но прививка листьев нестандартная и дает а Branch. Это не проблема для закона ассоциативности, но нарушает один из законов идентичности.

Когда у полиномиальных типов есть монады?

Ни один из функторов Maybe (a, a)и Maybe (a, a, a)не может быть дан законный Monadэкземпляр, хотя они, очевидно Applicative.

Эти функторы не имеют никаких трюков - нет Voidили в bottomлюбом месте, не сложно лени / строгости, ни бесконечных структуры, а также какие - либо ограничения класса типа. ApplicativeЭкземпляр полностью стандартны. Функции returnи bindмогут быть реализованы для этих функторов, но не будут удовлетворять законам монады. Другими словами, эти функторы не являются монадами, потому что отсутствует определенная структура (но непросто понять, чего именно не хватает). Например, небольшое изменение в функторе может превратить его в монаду: data Maybe a = Nothing | Just aэто монада. Другой подобный функтор data P12 a = Either a (a, a)- также монада.

Конструкции для полиномиальных монад

В общем, вот некоторые конструкции, которые производят законные Monads из полиномиальных типов. Во всех этих конструкциях Mесть монада:

  1. type M a = Either c (w, a)где wлюбой моноид
  2. type M a = m (Either c (w, a))где mкакая-то монада и wесть какой-нибудь моноид
  3. type M a = (m1 a, m2 a)где m1и m2какие монады
  4. type M a = Either a (m a)где mкакая-то монада

Первая конструкция есть WriterT w (Either c), вторая конструкция есть WriterT w (EitherT c m). Третья конструкция является компонентным произведением монад: pure @Mопределяется как компонентное произведение pure @m1и pure @m2, и join @Mопределяется путем исключения данных о перекрестном произведении (например m1 (m1 a, m2 a), отображается m1 (m1 a)путем исключения второй части кортежа):

 join :: (m1 (m1 a, m2 a), m2 (m1 a, m2 a)) -> (m1 a, m2 a)
 join (m1x, m2x) = (join @m1 (fmap fst m1x), join @m2 (fmap snd m2x))

Четвертая конструкция определяется как

 data M m a = Either a (m a)
 instance Monad m => Monad M m where
    pure x = Left x
    join :: Either (M m a) (m (M m a)) -> M m a
    join (Left mma) = mma
    join (Right me) = Right $ join @m $ fmap @m squash me where
      squash :: M m a -> m a
      squash (Left x) = pure @m x
      squash (Right ma) = ma

Я проверил, что все четыре конструкции производят законные монады.

Я предполагаю, что нет никаких других конструкций для полиномиальных монад. Например, функтор Maybe (Either (a, a) (a, a, a, a))не получается ни через одну из этих конструкций и поэтому не является монадическим. Тем не менее, Either (a, a) (a, a, a)это монадическая потому она изоморфна произведению трех монад a, aи Maybe a. Кроме того, Either (a,a) (a,a,a,a)является монадическим, потому что оно изоморфно произведению aи Either a (a, a, a).

Четыре конструкции, показанные выше, позволят нам получить любую сумму любого количества продуктов любого числа a, например, Either (Either (a, a) (a, a, a, a)) (a, a, a, a, a))и так далее. Все такие конструкторы типов будут иметь (хотя бы один) Monadэкземпляр.

Конечно, еще предстоит выяснить, какие варианты использования могут существовать для таких монад. Другая проблема заключается в том, что Monadэкземпляры, полученные с помощью конструкций 1-4, как правило, не являются уникальными. Например, конструктору типа type F a = Either a (a, a)можно дать Monadэкземпляр двумя способами: конструкцией 4 с использованием монады (a, a)и конструкцией 3 с использованием изоморфизма типов Either a (a, a) = (a, Maybe a). Опять же, поиск вариантов использования для этих реализаций не сразу очевиден.

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

winitzki
источник
Я думаю B , это монада. Можете ли вы дать контрпример к этой привязке Pair x y >>= f = case (f x, f y) of (Pair x' _,Pair _ y') -> Pair x' y' ; _ -> Empty?
Фрэнки
@Franky Ассоциативность терпит неудачу с этим определением, когда вы выбираете fтакое, которое f xесть, Emptyно f yесть Pair, и на следующем шаге оба являются Pair. Я вручную проверил, что законы не действуют ни для этой реализации, ни для какой-либо другой реализации. Но это большая работа, чтобы сделать это. Хотелось бы, чтобы был более простой способ понять это!
winitzki
1
@Turion Этот аргумент неприменим, Maybeпотому Maybeчто не содержит разных значений, о которых aнужно беспокоиться.
Даниэль Вагнер
1
@ Турион Я доказал это парой страниц вычислений; Аргумент о «естественном пути» - это просто эвристическое объяснение. MonadЭкземпляр состоит из функций , returnи bindчто законы , удовлетворяют. Есть две реализации returnи 25 реализаций, bindкоторые соответствуют требуемым типам. Прямым расчетом можно показать, что ни одна из реализаций не удовлетворяет законам. Чтобы сократить количество требуемой работы, я использовал joinвместо этого bindи сначала использовал законы об идентичности. Но это было немало работы.
winitzki
1
@duplode Нет, я не думаю, что Traversableнужно. m (Either a (m a))преобразуется с помощью pure @mв m (Either (m a) (m a)). Тогда тривиально Either (m a) (m a) -> m a, и мы можем использовать join @m. Это была реализация, для которой я проверил законы.
winitzki