Любая функция с тем же полиморфным типом, что и fmap, должна быть равна fmap?

Question

Я читаю второе издание по программированию на Хаскеле, и я наткнулся на это предложение:

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

Это мне не кажется правильным. Я вижу, что существует только одно действительное определение fmap для каждого Functor типа, но, конечно, я могу определить любое количество функций с типом (a -> b) -> f a -> f b, которые не эквивалентны друг другу

Почему это так? Или это просто ошибка автора?

Answer 1

Вы неправильно поняли то, что говорил автор.

... любая функция с того же полиморфного типа, что и fmap ...

Это означает, что любая функция с подписью

Functor f => (a -> b) -> f a -> f b

должна быть эквивалентна fmap.(Если, конечно, вы не разрешите нижние значения.)

Это утверждение верно;это можно увидеть довольно легко, если вы попытаетесь определить такую ​​функцию: поскольку вы ничего не знаете о f, за исключением того, что это функтор, единственный способ получить значение, отличное от 101 f b, - это fmapping поверх f aодин.

Немного менее очевидным является логическое следствие в цитате:

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

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

Я согласен с тем, что слово «следовательно» немного неверно сформулировано, но в принципе цитата верна.

Answer 2

Я думаю, что цитата относится к этому сценарию. Предположим, мы определяем параметризованный тип:

data F a = .... -- whatever

, для которого мы можем написать не одну, а две fmap реализации

fmap1 :: (a -> b) -> F a -> F b
fmap2 :: (a -> b) -> F a -> F b

удовлетворяющих законам функтора

fmap1 id = id
fmap1 (f . g) = fmap1 f . fmap1 g
fmap2 id = id
fmap2 (f . g) = fmap2 f . fmap2 g

При этих предположениях мы имеем, что fmap1 = fmap2.

Это теоретическое следствие «свободной теоремы», связанной с полиморфным типом fmap (см. Комментарий под Лемма 1 ). Прагматично, это гарантирует, что экземпляр, который мы получаем из deriving Functor, является единственно возможным.

Answer 3

Это ошибка. Вот несколько примеров функций того же типа, что и fmap для списков, которые не fmap:

\f -> const []
\f -> concatMap (replicate 2 . f)
\f -> map (f . head) . chunksOf 2
\f -> map f . reverse

Есть еще много. В общем, учитывая функцию ixf от длин списков до списков чисел, не превышающих эту длину (то есть действительных индексов в списке), мы можем построить

maybeIt'sFmapLol :: (Int -> [Int]) -> (a -> b) -> [a] -> [b]
maybeIt'sFmapLol ixf elemf xs = [map elemf xs !! ix | ix <- ixf (length xs)]

Используйте подходящие ленивые варианты Int для обработки бесконечных списков. Аналогичная схема функции может быть составлена ​​для других контейнероподобных функторов.