Есть ли еще один возможный экземпляр-функтор данного типа [duplicate]

«Когда может GHC получить экземпляр functor, а когда он не может быть?»

Когда у нас есть преднамеренные структуры круговых данных. Система типов не позволяет нам выразить наше намерение принудительной округлости. Таким образом, 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, Nodes и Faces.

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) против O (1)).