Почему pure требуется только для Applicative, а не для Functor?

Прочитав этот Wikibook об основах Haskell и теории категорий, я узнал о функторах:

Функтор - это, по сути, преобразование между категориями, поэтому для категорий C и D функтор F: C -> D

отображает любой объект A из C в F (A) из D.

отображает морфизмы f: A -> B в C в F (f): F (A) -> F (B) в D.

... звучит неплохо. Позже будет представлен пример:

У нас тоже есть образец:

instance Functor Maybe where
  fmap f (Just x) = Just (f x)
  fmap _ Nothing  = Nothing

Вот ключевая часть: конструктор типа Maybe принимает любой тип T в новый тип, Maybe T. Кроме того, fmap, ограниченный типами Maybe, принимает функцию a -> b в функцию Maybe a -> Maybe b. Но это все! Мы определили две части: что-то, что переводит объекты в Hask в объекты другой категории (типы Maybe и функции, определенные для типов Maybe), и что-то, что переводит морфизмы в Hask в морфизмы в этой категории. Итак, может быть, это функтор.

Я понимаю, что определение fmap является ключевым. Я не понимаю, как «конструктор типа Maybe» предоставляет первую часть. Я бы скорее ожидал чего-то вроде pure.

Если я правильно понял, Maybe скорее отображает C в D. (Таким образом, являясь морфизмом на уровне категории, который может быть требованием для функтора)

Думаю, вы могли бы перефразировать мой вопрос так: есть ли функтор, в котором нет очевидной реализации pure?


haskell functor category-theory
person ruben.moor    schedule 30.10.2015    source источник
comment
Спасибо за все полезные ответы. Я выбрал самый подробный, чтобы быть правильным.   -  person ruben.moor    schedule 30.10.2015
comment
Один простой Functor, который не допускает pure, - это data Void a. Экземпляр выглядит как instance Functor Void where { fmap f x = case x of {} }. (Я не даю этого ответа, потому что не думаю, что этот пример особенно поучительный, хотя он отвечает на единственный вопрос, который вы действительно задаете телу.)   -  person Daniel Wagner    schedule 30.10.2015
comment
@DanielWagner Я думаю, что до изоморфизма единственного Functor, который не допускает pure: если у вас есть любое значение v в Functor, вы можете определить pure x = x <$ v. И я думаю, что каждый выбор для pure тоже имеет такую ​​форму. Конечно, это обычно не является чем-то особенным.   -  person Ørjan Johansen    schedule 31.10.2015
comment
переносит объекты в Hask к объектам в другой категории (типам Maybe и функциям, определенным в типах Maybe) Я думаю, вы путаете кодомен и изображение. Кодомен здесь такой же, как и домен, это Hask, поэтому мы говорим об эндофункторе. изображение Hask в разделе Maybe является подмножеством кодомена - всех типов Maybe. Вы можете легко убедить себя, что Maybe не выводит вас из Hask, потому что вы можете применять Maybe несколько раз - Maybe (Mabe a) и т. Д. - внутреннее Maybe все еще находится в области Maybe.   -  person Bartosz Milewski    schedule 31.10.2015
comment
@BartoszMilewski Вы правы, это было мое замешательство. И это поясняется приведенными ниже ответами. Должен ли я исправить свой вопрос (мне это не кажется необходимым)?   -  person ruben.moor    schedule 02.11.2015
comment
@ ØrjanJohansen Я не согласен с этим утверждением, существует множество функторов, которые не допускают pure. Вот пара примеров: instance Functor ((,) a) имеет fmap f (a, b) = (a, f b), но как бы вы реализовали pure? pure x = (error "shit", x). Если вам удалось реализовать pure, вы могли бы получить magic = fst . pure () magic :: a, что является своего рода доказательством того, что такой pure по своей сути будет включать _|_. (Я понимаю, что Monoid a => (,) a допускает pure, но (,) a нет. Другой пример - instance Functor (Map k), а еще один - instance Functor (Const m).   -  person semicolon    schedule 28.09.2016
comment
@semicolon Я думаю, вам нужно выбрать один a: Я не делаю никаких заявлений о конструкторах полиморфных типов. Если a имеет значение без оснований, то очевидно, что у вас pure тоже без оснований. А если a не имеет значения, то он изоморфен Void. Но теперь я вижу, что лень усложняет дело, поскольку (error "shit", x) не является самой нижней частью Haskell. Я думаю, что для такого рода вопросов типично игнорировать все основания (иначе вы могли бы просто сказать pure x = undefined и покончить с этим), и тогда я думаю, что мое утверждение все еще верно для любого мономорфного примера.   -  person Ørjan Johansen    schedule 30.09.2016
comment
@ ØrjanJohansen Круто, конечно, это может быть верно для любого мономорфного примера. Жаль, что это не имеет значения, потому что огромное количество функторов не определено мономорфным образом, и этот вопрос говорит о том, почему pure не входит в Functor, чего НЕ ДОЛЖНО быть. И даже мономорфные примеры не обязательно имеют наилучшее значение по умолчанию. Например, списки pure 5 :: ZipList Int и pure 5 :: [Int] очень сильно различаются, но оба имеют решающее значение для соответствующих Applicative экземпляров.   -  person semicolon    schedule 30.09.2016
comment
@Bartosz Разумно ли говорить о типах в Maybe как о их собственной категории (конечно, подкатегории Hask)? Если это так, то цитата совершенно правильная. Я всегда так смотрел на функторы Haskell, а не как на эндофункторы. Конечно, их можно рассматривать как эндофункторы, но поскольку конструктор типов всегда создает новые типы, большинство эндофункторов в Hask не могут быть выражены как функторы Haskell.   -  person Ben    schedule 04.12.2016

Ответы (4)


arrow_upward
15
arrow_downward

Я думаю, вы путаетесь между типами и значениями. Вот определение функтора:

Пусть C и D будут категориями . Функтор F от C до D - это отображение, которое:

  • связывает с каждым объектом X ∈ C объект F (X) ∈ D.

  • сопоставляет каждому морфизму f: X → Y ∈ C морфизм F (f): F (X) → F (Y) ∈ D такой, что выполняются следующие условия:

    • F(id : X → X) = id : F(X) → F(X) for every object X ∈ C.
    • F (g ∘ f) = F (g) ∘ F (f) для всех морфизмов f: X → Y и g: Y → Z .

Категория состоит из объектов и морфизмов между объектами.

Весь код в Haskell является частью Hask , категория Haskell. В Hask:

  1. Типы - это объекты.
  2. Функции - это морфизмы между типами.

Следовательно, все Functor экземпляры в Haskell являются функторами от Hask к Hask (т.е. они являются эндофункторами).

Строго говоря, для всех экземпляров Functor в Haskell:

  1. C = Hask.
  2. D = Hask.

Теперь каждый функтор F - это отображение, которое сопоставляет каждому объекту X ∈ C объект F (X) ∈ D.

  1. Обратите внимание, что X и F (X) являются объектами C и D соответственно.
  2. Поскольку и C, и D являются Hask, оба X и F (X) являются типами, а не значениями.
  3. Таким образом, F: Type → Type или в Haskell f : * -> *.

Действительно, именно так класс типов Functor определяется в Haskell:

class Functor (f : * -> *) where
    fmap :: (x -> y) -> (f x -> f y)

Здесь fmap - вторая часть функтора. Это функция от значений к значениям. Однако сам Functor является конструктором типа (т. Е. Отображением типов в типы). По этой причине Maybe является функтором, а [] - функтором, но Maybe Int и [Int] не являются функторами.

Обратите внимание, что pure не образует первую часть определения функтора, потому что это отображение экземпляра X на экземпляр F (X) (т. Е. Это функция из значения к значениям). Однако нам нужно отображение X в F (X) (т. Е. Отображение типов в типы).

person Aadit M Shah    schedule 30.10.2015

arrow_upward
4
arrow_downward

Если я правильно понял, Maybe скорее отображает C на D. (Таким образом, являясь морфизмом на уровне категории, который может быть требованием для функтора)

Не совсем так, поскольку C и D существуют категории, а не типы Haskell. Functor (то есть экземпляр класса типа, в отличие от функтора в целом) - это отображение из категории Hask (категория типов и функций Haskell) в Hask < / strong> сам; то есть C и D оба являются Hask в этом случае. В главе Wikibook это упоминается в разделе Функторы в Hask. В вашем примере конструктор типа Maybe обеспечивает первую часть сопоставления, переводя некоторый тип a (объект в Hask) в тип Maybe a (другой объект в Hask). .

Думаю, вы могли бы перефразировать мой вопрос так: есть ли Functor, в котором нет очевидной реализации pure?

Одним из примеров является пара Functor, (,) a. fmap легко написать - \f (x, y) -> (x, f y), но для pure и (<*>) требуется ограничение Monoid на a, поскольку в противном случае не было бы никакого способа справиться с лишними a значениями. Дополнительное обсуждение и другие примеры см. В разделе Хорошие примеры Not a Functor / Functor / Applicative / Monad?

person duplode    schedule 30.10.2015

arrow_upward
3
arrow_downward

Я бы сказал, что экземпляр Applicative становится натяжкой для Either (что было бы прекрасно, если бы просто иметь экземпляр для Bifunctor, но, с другой стороны, использовать его как монаду удобно), и было бы (ИМХО) не подходит для чего-то вроде:

data ABC a = A a | B a | C a

Где все A, B, C "одинаково хороши". Поскольку нет очевидного выбора, что следует использовать для pure, его не следует предоставлять вообще. Однако наличие fmap - это нормально.

person Bartek Banachewicz    schedule 30.10.2015
comment
Имеет смысл ... произвол в связи с реализацией pure откладывается до тех пор, пока кто-то не реализует Applicative (и на этом этапе необходимо сделать выбор). - person ruben.moor; 30.10.2015
comment
@ ruben.moor Когда вы решили, как вы хотите реализовать <*> в своем Applicative, pure больше не является произвольным: он ограничен законами о применении. Реализация полностью произвольного pure как части Functor, где вам действительно не нужно было бы думать о том, как pure взаимодействует с чем-либо еще, может упростить случайное написание pure, которое не работает для Applicative (или Monad). - person Ben; 04.12.2016

arrow_upward
2
arrow_downward

Категория Hask имеет типы как объекты и функции как стрелки, поэтому отображение объектов, предоставляемое экземпляром Functor, должно сопоставлять типы с типами.

fmap отображает стрелки, то есть отображает функции a -> b в функции f a -> f b для функтора f. Конструктор типа Functor - это отображение для объектов, то есть между типами.

Например, конструктор типа Maybe отображает тип t на тип Maybe t, например. С String по Maybe String.

Напротив, pure сопоставляет значения некоторого базового типа со значением соответствующего аппликативного типа, например. «abc» и (Just «abc») оба значения String и Maybe String соответственно.

person Lee    schedule 30.10.2015
comment
Согласны ли вы, что в статье Викибука морфизм категорий путается с чистым, где говорится: отображает любой объект A из C в F (A) в D? - person ruben.moor; 30.10.2015
comment
Статья в викиучебнике верна. f в Functor f отображает объекты в категории Hask на объекты в категории Hask. Обратите внимание, что Haskell Functor является строго эндофунктором - его домен и кодомен должны быть Hask. Затем функция fmap отображает морфизм в Hask (функции типа a -> b) на морфизмы в Hask, в частности, на морфизм f a -> f b. В статье функтору присвоен тип Hask ~> Hask. Но обратите внимание, что эта стрелка не является стрелкой функции - стрелка функции переводит типы в типы, а не категории в категории. - person user2407038; 30.10.2015
comment
@ user2407038 действительно, теперь я понял. - person ruben.moor; 30.10.2015