Сделайте тип данных * → * Это не функтор

Ответ 1

Давайте поговорим об отклонениях.

Вот основное понятие. Рассмотрим тип A -> B. Я хочу, чтобы вы представляли, что такой тип похож на "имеющий B", а также "за счет A". Фактически, если вы вернете свой A, вы сразу получите свой B. Таким образом, функции похожи на escrow.

Понятие "наличие" и "отказ" может распространяться на другие типы. Например, самый простой контейнер

newtype Box a = Box a

ведет себя так: если у вас есть "Box a, то вы также" имеете "A. Мы рассматриваем типы, которые имеют вид * -> * и" имеют" свой аргумент как (ковариантные) функторы, и мы можем создать их для Functor

instance Functor Box where fmap f (Box a) = Box (f a)

Что произойдет, если мы рассмотрим тип предикатов над типом, например

newtype Pred a = Pred (a -> Bool)

в этом случае, если мы "имеем" a Pred a, мы фактически "обязаны" a A. Это связано с тем, что A находится в левой части стрелки (->). Где fmap of Functor определяется передачей функции в контейнер и ее применением ко всем местам, где мы "имеем" наш внутренний тип, мы не можем сделать то же самое для Pred a, поскольку мы не выполняем "имеют" и A s.

Вместо этого мы сделаем это

class Contravariant f where
  contramap :: (a -> b) -> (f b -> f a)

Теперь, когда contramap похож на "перевернутый" fmap? Это позволит нам применить функцию к местам, где мы "владеем" B в Pred b, чтобы получить Pred a. Мы можем назвать contramap "бартер", потому что он кодирует идею о том, что если вы знаете, как получить B от A, тогда вы можете превратить долг B в долг A s.

Посмотрим, как это работает.

instance Contravariant Pred where
  contramap f (Pred p) = Pred (\a -> p (f a))

мы просто запускаем нашу торговлю, используя f, прежде чем передавать ее в функцию предиката. Замечательно!

Итак, теперь мы имеем ковариантные и контравариантные типы. Технически они известны как ковариантные и контравариантные "функторы". Я также немедленно заявлю, что почти всегда контравариантный функтор не является также ковариантным. Это, таким образом, отвечает на ваш вопрос: существует куча контравариантных функторов, которые не могут быть созданы для Functor. Pred является одним из них.

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

data Z a = Z -- phantom a!

instance Functor       Z where fmap      _ Z = Z
instance Contravariant Z where contramap _ Z = Z

Фактически вы можете доказать, что все, что есть как Contravariant, так и Functor, имеет параметр phantom.

isPhantom :: (Functor f, Contravariant f) => f a -> f b   -- coerce?!
isPhantom = contramap (const ()) . fmap (const ())        -- not really...

С другой стороны, что происходит с типом типа

-- from Data.Monoid
newtype Endo a = Endo (a -> a)

В Endo a мы оба обязаны и получаем A. Означает ли это, что мы свободны от долгов? Ну, нет, это просто означает, что Endo хочет быть ковариантным и контравариантным и не имеет параметра phantom. Результат: Endo является инвариантным и не может создавать экземпляры Functor и Contravariant.

Ответ 2

Тип t вида * -> * можно сделать экземпляром Functor тогда и только тогда, когда для него возможно реализовать законный экземпляр класса Functor. Это значит, что вам нужно реализовать класс Functor, а ваш fmap должен подчиняться законам Functor:

fmap id x == x
fmap f (fmap g x) == fmap (f . g) x

Итак, чтобы решить это, вы должны назвать какой-то тип вашего выбора и доказать, что для него нет законной реализации fmap.

Начните с не-примера, чтобы установить тон. (->) :: * -> * -> * - это конструктор типа функции, как показано в типах функций типа String -> Int :: *. В Haskell вы можете частично применять конструкторы типов, поэтому вы можете иметь такие типы, как (->) r :: * -> *. Этот тип Functor:

instance Functor ((->) r) where
    fmap f g = f . g

Интуитивно, экземпляр Functor здесь позволяет применить f :: a -> b к возвращаемому значению функции g :: r -> a "before" (так сказать), вы применяете g к некоторому x :: r. Например, если это функция, возвращающая длину аргумента:

length :: [a] -> Int

... то это функция, которая возвращает удвоенную длину аргумента:

twiceTheLength :: [a] -> Int
twiceTheLength = fmap (*2) length

Полезный факт: монада Reader - это просто newtype для (->):

newtype Reader r a = Reader { runReader :: r -> a }

instance Functor (Reader r) where
    fmap f (Reader g) = Reader (f . g)

instance Applicative (Reader r) where
    pure a = Reader (const a)
    Reader f <*> Reader a = Reader $ \r -> f r (a r)

instance Monad (Reader r) where
    return = pure
    Reader f >>= g = Reader $ \r -> runReader g (f r) r

Теперь, когда у нас есть этот не-пример, вот тип, который нельзя сделать в Functor:

type Redaer a r = Redaer { runRedaer :: r -> a } 

-- Not gonna work!
instance Functor (Redaer a) where
    fmap f (Redaer g) = ...

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