Уникальны ли экземпляры Functor?

Мне было интересно, в какой степени экземпляры Functor в Haskell определяются (однозначно) по функторным законам.

Так как ghc может выводить экземпляры Functor для, по крайней мере, для "запускаемых мельниц" типов данных, кажется, что они должны быть уникальными, по крайней мере, в самых разных случаях.

Для удобства, законы определения и функтора Functor:

class Functor f where
  fmap :: (a -> b) -> f a -> f b

fmap id = id
fmap (g . h) = (fmap g) . (fmap h)

Вопросы:

Можно ли определить определение map, исходя из предположения, что это экземпляр Functor для data List a = Nil | Cons a (List a)? Если да, то какие предположения должны быть сделаны для этого?
Существуют ли какие-либо типы данных Haskell, которые имеют более одного экземпляра Functor, которые удовлетворяют законам функтора?
Когда ghc выводит экземпляр Functor, а когда он не может?
Все ли это зависит от того, как мы определяем равенство? Законы Functor выражаются в терминах равенства значений, но мы не требуем, чтобы Functors имели экземпляры Eq. Итак, есть ли здесь выбор?

Что касается равенства, то, безусловно, существует понятие того, что я называю "конструкторским равенством", что позволяет нам рассуждать о том, что [a,a,a] "равно" [a,a,a] для любого значения a любого типа, даже если a не имеет (==), определенного для него. Все другие (полезные) понятия равенства, вероятно, более грубые, чем это отношение эквивалентности. Но я подозреваю, что равенство в законах Functor является скорее отношением "рассуждения о равенстве" и может быть специфичным для приложения. Любые мысли об этом?

Ответ 1

Смотрите Брент Йорги Typeclassopedia:

В отличие от некоторых других классов типов, с которыми мы столкнемся, данный тип имеет не более одного допустимого экземпляра Functor. Это можно доказать с помощью свободной теоремы для типа fmap. Фактически, GHC может автоматически получать экземпляры Functor для многих типов данных.

Ответ 2

"Когда может GHC получить экземпляр функтора, а когда он не может?"

Когда у нас есть преднамеренные круговые структуры данных. Система типов не позволяет нам выразить наше намерение принудительной округлости. Итак, ghc может получить экземпляр, похожий на тот, который мы хотим, но не тот.

Структуры круговых данных вероятно, единственный случай, когда Functor должен быть реализован по-другому. Но опять же, у него будет такая же семантика.

data HalfEdge a = HalfEdge { label :: a , companion :: HalfEdge a }

instance Functor HalfEdge where
    fmap f (HalfEdge a (HalfEdge b _)) = fix $ HalfEdge (f a) . HalfEdge (f b)

EDIT:

HalfEdges - это структуры (известные в компьютерной графике, 3D-сетки...), которые представляют собой неориентированные края в графе, где вы можете иметь ссылку на любой конец. Обычно они хранят больше ссылок на соседние HalfEdges, узлы и лица.

newEdge :: a -> a -> HalfEdge a
newEdge a b = fix $ HalfEdge a . HalfEdge b

Семантически, нет fix $ HalfEdge 0 . HalfEdge 1 . HalfEdge 2, потому что ребра всегда состоят из ровно двух половинных ребер.

ИЗМЕНИТЬ 2:

В сообществе haskell для этой структуры данных известно цитата "Связывание узла" . Речь идет о структурах данных, которые семантически бесконечны, потому что они цикличны. Они потребляют только ограниченную память. Пример: данный ones = 1:ones, мы будем иметь эти семантически эквивалентные реализации twos:

twos = fmap (+1) ones
twos = fix ((+1)(head ones) :)

Если мы пересекаем (первые n элементов) twos и все еще имеем ссылку на начало этого списка, эти реализации отличаются скоростью (оценивайте 1 + 1 каждый раз только один раз) и потребление памяти (O (n ) vs O (1)).