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

18

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

  

Приведите пример типа вида * - & gt; *, которые не могут быть     Functor (без использования undefined).

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

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

Спасибо!

Источник оригинального упражнения здесь, раздел 3: Ссылка

    
задан JS. 20.04.2013 в 10:44
источник
  • Как насчет (-> int)? –  Ramon Snir 20.04.2013 в 10:57
  • @RamonSnir ((->) Int) на самом деле отлично, вам нужно что-то вроде данных K a = K (a -> Int). –  Mikhail Glushenkov 20.04.2013 в 10:59
  • @MikhailGlushenkov, это почти наверняка то, что означает Рамон, так же, как (+ 1) = \ a -> a + 1. –  huon 20.04.2013 в 11:02
  • @MikhailGlushenkov as @dbaupp отметил, (-> int) <> ((->) int). –  Ramon Snir 20.04.2013 в 11:10
  • См. также Хорошие примеры не functor / functor / Applicative / Monad ?. –  Petr Pudlák 20.04.2013 в 17:14

2 ответа

22

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

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 фактически представляет функторы covariant ( 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.     

ответ дан Mikhail Glushenkov 20.04.2013 в 11:01
  • +1 для CoFunctors. –  Ramon Snir 20.04.2013 в 11:18
  • Спасибо, поэтому, если я правильно понимаю, проблема в том, что для определения fmap для K имеем (a -> b) -> K (a -> Int) -> K (a -> b), что определяется путем попытки создать функцию типа a -> Int и функцию типа a -> b, которая не работает, потому что тип a должен быть привязан к Int? –  JS. 20.04.2013 в 11:20
  • @JS У вас есть функция типа a -> b и функция типа a -> Int, и вы должны создать функцию типа b -> Int. Но вы не можете составить входные данные для получения желаемого результата. –  Mikhail Glushenkov 20.04.2013 в 11:31
  • Нет необходимости определять контравариантный класс, используйте один из Hackage! –  leftaroundabout 20.04.2013 в 11:50
  • @ mikhail-glushenkov ах да, я вижу это сейчас, еще раз спасибо. –  JS. 20.04.2013 в 14:53
6

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

Учитывая (-> 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) .

    
ответ дан Ramon Snir 20.04.2013 в 11:07
  • Доказательство просто: мы имеем две теоремы, для которых требуются доказательства для a. У нас есть только доказательство для b. Никаких новых доказательств не может быть получено (поскольку ни одна из теорем не применима) => для Int не может быть получено никаких доказательств. –  Ramon Snir 20.04.2013 в 11:09