Пример типа с видом * → *, который не может быть экземпляром Functor

Я очень новичок Haskell, поэтому извиняюсь, если ответ очевиден, но я работаю через Typeclassopedia, чтобы лучше понять категории. При выполнении упражнений для раздела "Функторы" я столкнулся с этой проблемой:

Приведите пример типа вида * → *, который нельзя сделать экземпляром   Functor (без использования undefined).

Моя первая мысль заключалась в том, чтобы определить какое-то бесконечно рекурсивное определение fmap, но не было бы, по сути, таким же, как если бы в определении было undefined?

Если кто-то может объяснить ответ, мы будем очень благодарны.

Спасибо!

Источник оригинального упражнения здесь, раздел 3: http://www.haskell.org/haskellwiki/Typeclassopedia#Introduction

Ответы

Ответ 1

Простым примером является

data K a = K (a -> Int)

Здесь, о котором говорит ghci, мы пытаемся автоматически получить экземпляр Functor для K:

Prelude> :set -XDeriveFunctor
Prelude> data K a = K (a -> Int)
Prelude> :k K
K :: * -> *
Prelude> data K a = K (a -> Int) deriving Functor

<interactive>:14:34:
    Can't make a derived instance of `Functor K':
      Constructor `K' must not use the type variable in a function argument
    In the data type declaration for `K'

Проблема состоит в том, что стандартный класс Functor фактически представляет ковариантные функторы (fmap поднимает свой аргумент до f a -> f b), но вы не можете создать a -> b и a -> Int, чтобы получить функцию тип b -> Int (см. ответ Рамона). Тем не менее, можно определить класс типа для контравариантных функторов:

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

и сделайте K его экземпляр:

instance Contravariant K where
    contramap f (K g) = K (g . f)

Подробнее о ковариации/контравариантности в Haskell см. здесь.

Изменить: Здесь также хороший комментарий по этому вопросу от Криса Смита на Reddit.

Ответ 2

Расширить мой (короткий) комментарий и ответить на вопрос Михаила:

Учитывая (-> Int), вы ожидаете, что fmap будет выглядеть следующим образом:

(a -> Int) -> (a -> b) -> (b -> Int)

или

(a -> Int) -> (a -> b) -> b -> Int

Нетрудно доказать, что из трех аргументов (a -> Int), (a -> b), b нет возможного пути достижения Int (без undefined), поэтому из (a -> Int), (a -> b) невозможно достичь (b -> Int). Вывод: экземпляр Functor существует для (-> Int).