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

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

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

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

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

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

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

Конструктор типа, который не является 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 :: * -> * -> *

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

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

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

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

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

Конструктор типа, который является 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 ~ > Б). Кроме того, идиомы встраиваются в стрелки, а стрелки - в монады.

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

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

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

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

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 id≠ id, потому что 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экземпляр. Я не знаю, как доказать, что нет других конструкций для полиномиальных монад. Я не думаю, что какая-либо теория существует до сих пор, чтобы ответить на этот вопрос.