Пример конкретного типа функтора, который не может быть аппликативным?

Из функторов, которые не являются аппликативными:

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

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

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

Здесь pure невозможно определить для всех типов одновременно; однако для любого бетона типа T можно сделать ((,) T) аппликативом.

Вопрос. Существует ли пример конкретного функтора (т. е. без задействованных переменных типа), который является функтором, но не аппликативным?


haskell category-theory
person George    schedule 23.05.2017    source источник
comment
[Однако] для любого конкретного типа T можно сделать ((,) T) аппликативным — не совсем так. Вам по-прежнему нужно, чтобы T был моноидом, и не только из-за pure: вам также нужно реализовать (<*>) таким образом, чтобы два метода следовали аппликативным законам.   -  person duplode    schedule 23.05.2017
comment
Итак, все, что нужно для ответа на этот вопрос, — это найти немоноид T, и тогда ((,) T) будет конкретным функтором, который не может быть аппликативным?   -  person George    schedule 23.05.2017
comment
Ага, этого достаточно.   -  person duplode    schedule 23.05.2017
comment
В математике существует теорема о том, что любой набор, состоящий как минимум из 2 элементов, можно превратить в моноид. Таким образом, для любого конкретного типа T его в принципе можно сделать членом Monoid, а затем в принципе можно сделать Applicative. Что не так с этим рассуждением?   -  person George    schedule 23.05.2017
comment
Является ли Dead из этот ответ тем, что вы ищете? Дополнительных переменных типа нет...   -  person Alec    schedule 23.05.2017
comment
Этот ответ соответствует тому, о чем вы начали думать: stackoverflow.com/a/36440023/414413   -  person Cirdec    schedule 23.05.2017
comment
Простой пример неаппликативного функтора: (a -> Int) -> Maybe a. Тип, требуемый для ‹*›, не имеет реализации, удовлетворяющей законам тождества.   -  person winitzki    schedule 10.04.2018
comment
@winitzki: как (a -> Int) -> Maybe a является Functor (т.е. как вы определяете fmap)?   -  person Tom    schedule 16.01.2019
comment
@Tom deriving Functor должен делать это автоматически. Этот конструктор типа использует a в ковариантных позициях, так что это явно функтор. Экземпляр функтора можно построить механически. Если вы видите, как (a -> Int) -> Int и z -> Maybe a реализуют свои fmap, вы легко поймете, что здесь делать.   -  person winitzki    schedule 17.01.2019
comment
@winitzki: Ну, конечно, спасибо! Для тех, кому интересно, идея состоит в том, что при наличии функции f :: a -> b и функции b -> Int их можно скомпоновать, чтобы получить функцию a -> Int. Учитывая x :: (a -> Int) -> Maybe a, можно применить его к результату и получить Maybe a, который затем можно сопоставить, используя fmap Maybe, с Maybe b, то есть fmap f x = \g -> fmap f (x (g . f)).   -  person Tom    schedule 18.01.2019
comment
@winitzki: теперь вопрос в том, как можно доказать, что никакая <*> реализация для этого типа не может удовлетворять законам.   -  person Tom    schedule 18.01.2019
comment
@Tom Во-первых, вы получаете реализацию из типа. Проще рассмотреть zip : F a -> F b -> F (a,b), чем <*>. Теперь нам нужно реализовать zip : ((a -> Z) -> Maybe a)) -> ((b -> Z) -> Maybe b) -> ((a, b) -> Z) -> Maybe (a, b). Но функция с этой сигнатурой типа может возвращать только Nothing, потому что невозможно вычислить пару (a, b) (у нас не может быть значения типа a -> Z или b -> Z, у нас есть только (a, b) -> Z). Так что это единственная реализация. Однако метод zip, который всегда возвращает Nothing, будет нарушать законы тождества для аппликативных функторов.   -  person winitzki    schedule 19.01.2019
comment
Спасибо за объяснение, @winitzki!   -  person Tom    schedule 19.01.2019

Ответы (3)


arrow_upward
5
arrow_downward

У меня нет репутации 50, чтобы комментировать здесь, поэтому я попытаюсь сделать это как ответ:

однако для любого конкретного типа T можно сделать ((,) T) аппликативом.

...

В математике существует теорема о том, что любой набор, состоящий как минимум из 2 элементов, можно превратить в моноид. Таким образом, для любого конкретного типа T его в принципе можно сделать членом Monoid, а затем в принципе сделать аппликативным. Что не так с этим рассуждением?

Как насчет кортежа из необитаемого типа? (,) Void

Это Functor, верно?

Не могли бы вы вывести Applicative для него? Как будет реализован pure?

person rbasso    schedule 23.05.2017

arrow_upward
3
arrow_downward

Хороший пример есть в reactive-banana library.

Он имеет типы Event a, которые представляют собой одно одновременное событие во времени (мысль, импульс), и тип Behavior a, которые представляют собой значение, доступное в любой момент (например, испускание значения из последнего события).

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

введите здесь описание изображения

Событие, однако, является только функтором, потому что вы не можете комбинировать их. Учитывая два Event, вы не можете быть уверены, что они произойдут одновременно.

Событие

person arrowd    schedule 23.05.2017
comment
Push-Pull FRP дает экземпляр Monad для Event, который реализует динамическое переключение событий. Соответствующий экземпляр Applicative принимает декартово произведение двух событий. - person Benjamin Hodgson♦; 24.05.2017

arrow_upward
0
arrow_downward

[Однако] для любого конкретного типа T можно сделать ((,) T) аппликативным — не совсем так. Вам по-прежнему нужно, чтобы T был моноидом, и не только из-за чистоты: вам также нужно реализовать (<*>) таким образом, чтобы два метода следовали аппликативным законам.

[...]

В математике существует теорема о том, что любой набор, состоящий как минимум из 2 элементов, можно превратить в моноид. Таким образом, для любого конкретного типа T его в принципе можно сделать членом Monoid, а затем в принципе можно сделать Applicative. Что не так с этим рассуждением?

В принципе не обязательно переводиться в код. Учитывать:

newtype UserID = UserID Integer

Насколько я вижу, для UserID не существует значимого экземпляра Monoid. В принципе, можно использовать 0 и (+) в базовом Integer, но это будет равносильно утечке деталей реализации без уважительной причины (и которые, вероятно, в конечном итоге будут скрыты, сделав тип абстрактным). Если так, то (,) UserID будет прекрасным примером Functor, который не является Applicative.

person duplode    schedule 23.05.2017