索引到容器中：數學基礎

當您想從數據結構中提取元素時，必須給出索引。但索引的含義取決於數據結構本身。索引到容器中：數學基礎

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)

似乎產品類型的指數是一個總和（告訴你看該產品的臂），元素的索引爲單位類型，和嵌套類型的索引爲一個產品（告訴你在嵌套類型中的位置）。總計似乎是唯一不以某種方式鏈接到derivative。總和的索引也是一個總和 - 它告訴你用戶希望找到的總和的哪一部分，如果違反了這個期望，你只剩下一小部分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實例的雙聯積木。

但是究竟發生了什麼？仿函數和它的索引之間的底層關係是什麼？它如何與函數的導數相關？是否需要了解theory of containers（我沒有，真的）來回答這個問題？

來源

2016-04-16 Benjamin Hodgson

我真的不認爲列表是通過數字索引（這'Nothing'是比較難看）。對我來說'xs'列表是由'Fin（length xs）'或類似[this]（http://lpaste.net/160209）索引的。然後，索引只是相應容器中的位置。對於列表'Shape ='和'Position = Fin'，即你完全得到'Fin（length xs）'，因爲列表的形狀是它的長度。 – user3237465

看起來類似的索引是構造函數集合中的一個索引，接着是表示該構造函數的產品索引。這可以很自然地用例如generics-sop。

首先，您需要一個數據類型來將可能的索引表示爲產品的單個元素。這可以是指向a, 類型的元素或指向g b類型的索引的索引 - 這需要指向g的索引和指向b中的類型a的元素的索引。這個編碼有以下類型：

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實現）的總和總和超過構造元素的類型（構造器的選擇，所選擇的通用表示）：

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

你可以寫各種指數智能構造函數：

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)

注意，如在列表情況下，不能構造指向[]構造函數的（非底部）索引 - 對於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]

來源

2016-04-17 03:54:12 user2407038

索引到容器中：數學基礎

回答

相關問題