Если вы хотите извлечь элемент из структуры данных, вы должны указать его индекс. Но смыслиндекс зависит от самой структуры данных.

class Indexed f where
    type Ix f
    (!) :: f a -> Ix f -> Maybe a  -- indices can be out of bounds

Например...

Элементы в списке имеют числовые позиции.

data Nat = Z | S Nat
instance Indexed [] where
    type Ix [] = Nat
    [] ! _ = Nothing
    (x:_) ! Z = Just x
    (_:xs) ! (S n) = xs ! n

Элементы в двоичном дереве идентифицируются последовательностью направлений.

data Tree a = Leaf | Node (Tree a) a (Tree a)
data TreeIx = Stop | GoL TreeIx | GoR TreeIx  -- equivalently [Bool]
instance Indexed Tree where
    type Ix Tree = TreeIx
    Leaf ! _ = Nothing
    Node l x r ! Stop = Just x
    Node l x r ! GoL i = l ! i
    Node l x r ! GoR j = r ! j

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

data Rose a = Rose a [Rose a]  -- I don't even like rosé
data RoseIx = Top | Down Nat RoseIx  -- equivalently [Nat]
instance Indexed Rose where
    type Ix Rose = RoseIx
    Rose x ts ! Top = Just x
    Rose x ts ! Down i j = ts ! i >>= (! j)

Кажется, что индекс типа продукта - это сумма (указывающая, на какое плечо продукта смотреть), индекс элемента - это тип единицы, а индекс вложенного типа - это продукт (указывающий, куда посмотри во вложенном типе). Кажется, что единственные суммы, которые никак не связаны спроизводное, Индекс суммы также является суммой - он сообщает, какую часть суммы пользователь надеется найти, и если это ожидание нарушается, у вас остается горсткаNothing.

На самом деле я добился определенного успеха в реализации! обычно для функторов, определенных как неподвижная точка бифунктора полинома. Я не буду вдаваться в подробности, ноFix f можно сделать примеромIndexed когдаf является примеромIndexed2...

class Indexed2 f where
    type IxA f
    type IxB f
    ixA :: f a b -> IxA f -> Maybe a
    ixB :: f a b -> IxB f -> Maybe b

... и оказывается, что вы можете определить экземплярIndexed2 для каждого из бифункторов строительных блоков.

Но что на самом деле происходит? Каковы основные отношения между функтором и его индексом? Как это связано с производной функтора? Нужно ли пониматьтеория контейнеров (что я действительно не знаю), чтобы ответить на этот вопрос?