Car*_*ate 4 haskell multidimensional-array
我有了定义一个运算符的想法,该运算符采用(可能)多维列表和索引列表,并返回该元素.我的原型尝试是:
(!!!) xs [i] = xs !! i
(!!!) xs (cI : restI) = (xs !! cI) !!! restI
回想起来,这显然有很多问题.我首先想不出类型签名,然后我意识到在第2行,(xs !! cI)的返回类型将不断变化,并且可能并不总是一个列表(在最后一次"迭代"中)
我意识到要使用标准的下标运算符访问多维数组,您可以简单地将其链接为:
[[1,2,3],[4,5,6],[7,8,9]] !! 1 !! 1 = 5
并意识到这看起来很像折叠,所以我试过:
(!!!) xxs inds = foldl (!!) xxs inds
or simply (!!!) = foldl (!!)
但是我得到的错误与我的第一次尝试相同; 我正在尝试构建一个无限类型.
这种类型的功能是否可行(通过黑客或其他方式)？我开始认为它的类型太空中了.
举个例子,我的目标是:
[[1,2,3],[4,5,6],[7,8,9]] !!! [1,1] = 5
只要您不必使用列表来存储索引,就可以毫不费力地执行此操作.索引必须作为数据类型传递,该数据类型对类型中有多少索引进行编码.规范长度索引列表类型如下所示:
data Nat = Z | S Nat
infixr 5 :>
data Vector (n :: Nat) a where
Nil :: Vector Z a
(:>) :: a -> Vector n a -> Vector (S n) a
然后你的功能是
(!!!) a Nil = a
(!!!) a (i :> is) = (a !! i) !!! is
你会注意到这不会编译.这是因为a第一行和第二行中的类型不同.类型a必须取决于索引的类型,并且必须告诉编译器它们如何依赖它.依赖性非常简单; 当有n个索引时,必须有n个维度的列表:
type family Dimension (n :: Nat) (v :: * -> *) (x :: *) :: * where
Dimension Z v x = x
Dimension (S n) v x = v (Dimension n v x)
那么上面的类型很简单
(!!!) :: Dimension n [] a -> Vector n Int -> a
我不知道你对Haskell类型系统的更高级功能有多熟悉,但上面需要类型族和数据类型.