Bağımlı büyüklükteki dizileri n boyutlarına genellemek için?

Question

Şu an bununla oynuyordum ama bu işi yapmak için GHC'yi ikna edemedim.

newtype Arr1 (w :: Nat) a = Arr1 (Int -> a) 
newtype Arr2 (w :: Nat) (h :: Nat) a = Arr2 (Int -> a) 

ix2 :: forall w h a. (KnownNat w) => Arr2 w h a -> Int -> Int -> a 
ix2 (Arr2 f) x y = f (y * w + x) 
    where w = fromInteger $ natVal (Proxy :: Proxy w) 

sub2 :: forall w h a. (KnownNat w) => Arr2 w h a -> Int -> Arr1 w a 
sub2 (Arr2 f) y = Arr1 $ \x -> f (y * w + x) 
    where w = fromInteger $ natVal (Proxy :: Proxy w) 

mkArr2V :: forall w h a. (V.Unbox a, KnownNat w, KnownNat h) => V.Vector a -> Arr2 w h a 
mkArr2V v = Arr2 $ (v V.!) 

-- and so on ... errorchecking neglected 

Ama şimdiki GHC versiyonları bize çok daha expressibility vermek:

Temel olarak bağımlı boy Haskell/ghc güncel sürümlerinde diziler oluşturmak için oldukça kolaydır. Temelde bunun için tek bir türünü oluşturmak için mümkün olmalıdır: Bu GHCi çalışır

newtype Mat (s :: [Nat]) a = Mat (Int -> a) 

-- create array backed by vector 
mkMatV :: forall s a. V.Vector a -> Mat s a 
mkMatV v = Mat $ (v V.!) 

:

>>> let m = mkMatV (V.fromList [1,2,3,4]) :: Mat [2,2] Double 
>>> :t m 
m :: Mat '[2, 2] Double 

Ama diziler içine indeksleme gerçekleştirmek için nasıl emin değilim bu noktaya kadar

. Basit bir çözüm, nd ve 1d endeksleme için iki farklı fonksiyon kullanmak olacaktır. Not bu yazmaz.

-- slice from nd array 
(!) :: forall s ss a. (KnownNat s) => Mat (s ': ss) a -> Int -> Mat ss a 
(!) (Mat f) o = Mat $ \i -> f (o*s+i) 
    where s = fromInteger $ natVal (Proxy :: Proxy (sum ss)) 

-- index into 1d array 
(#) :: forall s ss a. (KnownNat s) => Mat (s ': '[]) a -> Int -> a 
(#) (Mat f) o = Mat $ \i -> f o 

böyle muhtemelen kullanılabilir: Z, Y, x, için endeksler vermek için gerekli olan Değil

>>> :t m ! 0 
Mat [2] Double 
>>> m ! 0 # 0 
1 

. Tercih edilen çözümüm, dizinin boyutuna bağlı olarak dönüş türünü değiştiren tek bir endeksleme işlevi sağlar. Benim bildiğim kadarıyla bu tür sınıfları kullanarak bir şekilde elde edilebilir, ancak bunu henüz anlamadım. Endeksler "doğal" x, y, z sırasına göre verilebilirse bonus puanları.

tl; dr: Yukarıda tanımlanan şekilde n boyutlu dizileri indeksleyen bir işlev istiyorum.

Answer 1

Bu gerçekten tip sınıfları ile yapılabilir. Bazı elemelerindeki:

{-# LANGUAGE 
    UndecidableInstances, MultiParamTypeClasses, TypeFamilies, 
    ScopedTypeVariables, FunctionalDependencies, TypeOperators, 
    DataKinds, FlexibleInstances #-} 

import qualified Data.Vector as V 

import GHC.TypeLits 
import Data.Proxy 

newtype NVec (shape :: [Nat]) a = NVec {_data :: V.Vector a} 

başka bir şey önce, bir n-boyutlu vektör toplam yassı boyutunu anlatmak gerekir. Endeksleme için adımları hesaplamak için kullanacağız. Tip seviyesi listesinde tekrarlamak için bir sınıf kullanıyoruz.

class FlatSize (sh :: [Nat]) where 
    flatSize :: Proxy sh -> Int 

instance FlatSize '[] where 
    flatSize _ = 1 

instance (KnownNat s, FlatSize ss) => FlatSize (s ': ss) where 
    flatSize _ = fromIntegral (natVal (Proxy :: Proxy s)) * flatSize (Proxy :: Proxy ss)  

Ayrıca dizin oluşturma için bir tür sınıfı kullanıyoruz. Tek boyutlu durum için (basitçe alttaki vektöre indekslediğimiz) ve daha yüksek boyutlu durum için farklı boyutlar sağlıyoruz (yeni bir NVec'u indirgenmiş boyutla döndürüyoruz). Her iki durumda da aynı sınıfı kullanıyoruz. daha yüksek boyutlu bir vektör içine

infixl 5 !            
class Index (sh :: [Nat]) (a :: *) (b :: *) | sh a -> b where 
    (!) :: NVec sh a -> Int -> b 

instance Index '[s] a a where 
    (NVec v) ! i = v V.! i   

instance (Index (s2 ': ss) a b, FlatSize (s2 ': ss), res ~ NVec (s2 ': ss) a) 
    => Index (s1 ': s2 ': ss) a res where 
    (NVec v) ! i = NVec (V.slice (i * stride) stride v) 
    where stride = flatSize (Proxy :: Proxy (s2 ': ss)) 

dizin hemen elde edilen vektör, düz boyutu ve ofset uygun olan bir dilim alıyor.

Bazı testler: ekstra olarak

fromList :: forall a sh. FlatSize sh => [a] -> NVec sh a 
fromList as | length as == flatSize (Proxy :: Proxy sh) = NVec (V.fromList as) 
fromList _ = error "fromList: initializer list has wrong size" 

v3 :: NVec [2, 2, 2] Int 
v3 = fromList [ 
    2, 4, 
    5, 6, 

    10, 20, 
    30, 0 ] 

v2 :: NVec [2, 2] Int 
v2 = v3 ! 0 

vElem :: Int 
vElem = v3 ! 0 ! 1 ! 1 -- 6 

---

, bu çok daha uygun olduğu için ben de bir singletons çözüm sunmak edelim. Daha fazla kodu (tek bir işlev için daha az özel tipler) yeniden kullanmamıza ve daha doğrudan, işlevsel bir tarzda yazmamıza izin verir.

{-# LANGUAGE 
    UndecidableInstances, MultiParamTypeClasses, TypeFamilies, 
    ScopedTypeVariables, FunctionalDependencies, TypeOperators, 
    DataKinds, FlexibleInstances, StandaloneDeriving, DeriveFoldable, 
    GADTs, FlexibleContexts #-} 

import qualified Data.Vector as V 
import qualified Data.Foldable as F 
import GHC.TypeLits 
import Data.Singletons.Preludeimport 
import Data.Singletons.TypeLits 

newtype NVec (shape :: [Nat]) a = NVec {_data :: V.Vector a} 

flatSize çok daha basit hale gelir: Biz sadece değer seviyesine sh düşürmek ve her zamanki gibi üzerinde çalışacağı:

flatSize :: Sing (sh :: [Nat]) -> Int 
flatSize = fromIntegral . product . fromSing 

Biz bir tür aile ve dizin oluşturma için bir işlevini kullanın. Önceki çözümde boyutlar üzerinde gönderilecek örnekleri kullandık; Burada biz desen eşleştirme ile aynı şeyi:

type family Index (shape :: [Nat]) (a :: *) where 
    Index (s ': '[])  a = a 
    Index (s1 ': s2 ': ss) a = NVec (s2 ': ss) a 

infixl 5 ! 
(!) :: forall a sh. SingI sh => NVec sh a -> Int -> Index sh a 
(!) (NVec v) i = case (sing :: Sing sh) of 
    SCons _ SNil  -> v V.! i 
    SCons _ ss@SCons{} -> NVec (V.slice (i * stride) stride v) where 
    stride = flatSize ss 

Biz de güvenli endeksleme ve başlatmak için Nat singletons kullanabilirsiniz (. i e statik sınırları ve boyutları kontrol ile.). Başlatma için statik büyüklükte bir liste tipi tanımlarız (Vec). Güvenli fonksiyonlar için

safeIx :: 
    forall a s sh i. (SingI (s ': sh), (i + 1) <= s) => 
    NVec (s ': sh) a -> Sing i -> Index (s ': sh) a 
safeIx v si = v ! (fromIntegral $ fromSing si)      

data Vec n a where 
    VNil :: Vec 0 a 
    (:>) :: a -> Vec (n - 1) a -> Vec n a 
infixr 5 :> 
deriving instance F.Foldable (Vec n) 

fromVec :: forall a sh. SingI sh => Vec (Foldr (:*$) 1 sh) a -> NVec sh a 
fromVec = fromList . F.toList 

Bazı örnekler:

-- Other than 8 elements in the Vec would be a type error 
v3 :: NVec [2, 2, 2] Int 
v3 = fromVec 
    (2 :> 4 :> 
     5 :> 6 :> 

     10 :> 20 :> 
     30 :> 0 :> VNil) 

vElem :: Int 
vElem = v3 
    `safeIx` (sing :: Sing 0) 
    `safeIx` (sing :: Sing 1) 
    `safeIx` (sing :: Sing 1) -- 6