Defining an operator to access a multi-dimensional array

Question

I got the idea of defining an operator that takes a (possibly) multidimensional list, and a list of indices, and returns the element. My proto attempt was:

(!!!) xs [i]            = xs !! i
(!!!) xs (cI : restI)   = (xs !! cI) !!! restI

In retrospect, this obviously has a lot of problems. I couldn't figure out a type signature first off, then I realized that in line 2, the return type of (xs !! cI) will constantly change, and may not always even be a list (on the last "iteration")

I realized that to access a multi-dimensional array using the standard subscript operator, you can simply chain it like:

[[1,2,3],[4,5,6],[7,8,9]] !! 1 !! 1 = 5

And realized that that looks a lot like a fold, so I tried:

(!!!) xxs inds = foldl (!!) xxs inds
or simply (!!!) = foldl (!!) 

But I get the same error as my first attempt; that I'm trying to construct an infinite type.

Is this type of function even possible (through a hack or otherwise)? I'm starting to think that its type is just too up in the air to work.

Just as an example, I was aiming for the following:

[[1,2,3],[4,5,6],[7,8,9]] !!! [1,1] = 5

Answer 1

As long as you are not bound to using a list to store your indices, you can do this without much effort. The indices must be passed as a datatype which encodes how many indices there are in the type. The canonical length indexed list type looks something like this:

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 

Then your function is

(!!!) a Nil = a 
(!!!) a (i :> is) = (a !! i) !!! is 

You'll notice this doesn't compile. This is because the types of a in the first and second lines are different. The type of a must depend on the type of the indices, and you must tell the compiler exactly how they depend on it. The dependence is quite straightforward; when there are n indices, there must be a list of n dimensions:

type family Dimension (n :: Nat) (v :: * -> *) (x :: *) :: * where 
  Dimension     Z v x = x 
  Dimension (S n) v x = v (Dimension n v x)

Then the type of the above is quite simply

(!!!) :: Dimension n [] a -> Vector n Int -> a

I don't know how familiar you are with the more advanced features of the Haskell type system, but the above requires type families and data kinds.