コンテナへの索引付け：数学的基盤

Question

データ構造から要素を取り出す場合は、そのインデックスを与える必要があります。しかし、のインデックスの意味は、データ構造そのものに依存します。例えば

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 

は、各レベルでの森林から木を選択することで、一度にレベル1を辞任することを伴います。

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) 

製品の種類のインデックスは、要素のインデックスは、単位型であり、ネストされたタイプのインデックスがある（を見て製品のどの腕を告げる）和であると思われます製品（ネストされた型をどこから探すか）和はderivativeに何らかの形でリンクされていない唯一のものと思われます。合計のインデックスは合計でもあります。ユーザーが検索したいと思っている部分の合計を示しています。その期待値が違反されている場合は、Nothingが残っています。

実際には、多項式二分関数の固定小数点として定義されたファンクタに対して、一般的には!を実装することで成功しました。私は詳細には触れませんが、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 

のインスタンスであるときFix fはIndexedのインスタンスを行うことができます...そして、それはあなたがそれぞれのIndexed2のインスタンスを定義することができ判明しますbifunctorビルディングブロックの

しかし、実際に何が起こっていますか？ファンクタとそのインデックスとの間の根本的な関係は何ですか？ファンクタのデリバティブとはどのような関係がありますか？私はこの質問に答えるためにtheory of containers（実際にはそうではありません）を理解する必要がありますか？

Answer 1

型へのインデックスのように、そのコンストラクタを表す製品へのインデックスに従って、コンストラクタのセットへのインデックスです。これは非常に自然に実施することができる。 generics-sop。

最初に、製品の単一要素に可能なインデックスを表すデータ型が必要です。これはタイプa, のタイプの要素、またはgを指すインデックスとタイプaを指すインデックスbを指すインデックスg bの何かを指すインデックスを指すインデックスである可能性があります。

import Generics.SOP 

data ArgIx f x x' where 
    Here :: ArgIx f x x 
    There :: (Generic (g x')) => Ix g -> ArgIx f x x' -> ArgIx f x (g x') 

newtype Ix f = ... 

インデックス自体は、単に（n進合計NSによって実装さ）の和である和のコンストラクタ要素のタイプ（コンストラクタの選択、選択の一般的な表現上：これは、以下のタイプを用いて符号化されます）：例えばこと

listIx :: Natural -> Ix [] 
listIx 0 = MkIx $ S $ Z $ Z Here 
listIx k = MkIx $ S $ Z $ S $ Z $ There (listIx (k-1)) Here 

treeIx :: [Bool] -> Ix Tree 
treeIx [] = MkIx $ S $ Z $ S $ Z Here 
treeIx (b:bs) = 
    case b of 
    True -> MkIx $ S $ Z $ Z $ There (treeIx bs) Here 
    False -> MkIx $ S $ Z $ S $ S $ Z $ There (treeIx bs) Here 

roseIx :: [Natural] -> Ix Rose 
roseIx [] = MkIx $ Z $ Z Here 
roseIx (k:ks) = MkIx $ Z $ S $ Z $ There (listIx k) (There (roseIx ks) Here) 

注：

newtype Ix f = MkIx (forall x . NS (NS (ArgIx f x)) (Code (f x))) 

あなたは様々な指標のためのスマートなコンストラクタを書くことができますリストのケースでは、TreeとEmptyのように[]コンストラクタを指す（非ボトム）インデックスを作成することはできません。また、タイプがaでない値を含むコンストラクタや、タイプがaのものが含まれます。数値化をMkIxにすると、最初にIntを指すような構成の悪いものがありません。にあり、xがIntにインスタンス化されています。

指数関数の実装は種類が怖いであっても、非常に簡単です：

(!) :: (Generic (f x)) => f x -> Ix f -> Maybe x 
(!) arg (MkIx ix) = go (unSOP $ from arg) ix where 

    atIx :: a -> ArgIx f x a -> Maybe x 
    atIx a Here = Just a 
    atIx a (There ix0 ix1) = a ! ix0 >>= flip atIx ix1 

    go :: (All SListI xss) => NS (NP I) xss -> NS (NS (ArgIx f x)) xss -> Maybe x 
    go (Z a) (Z b) = hcollapse $ hzipWith (\(I x) -> K . atIx x) a b 
    go (S x) (S x') = go x x' 
    go Z{} S{} = Nothing 
    go S{} Z{} = Nothing 

go機能は、インデックスと種類によって使用される実際のコンストラクタで指さコンストラクタを比較します。コンストラクタが一致しない場合、インデックスはNothingを返します。インデックスが正確にHereを指している場合には簡単な実際のインデックス作成が行われ、一部のサブストラクチャの場合は両方のインデックス作成操作が次々に成功し、それは>>=によって処理されます。

そして簡単なテスト：私は本当にリストが数字でインデックス化されているとは思わない

>map (("hello" !) . listIx) [0..5] 
[Just 'h',Just 'e',Just 'l',Just 'l',Just 'o',Nothing]