Calculation of the nontrivial type of Idris for indexing tensors

Question

I fiddled with a simple tensor library in which I defined the following type.

data Tensor : Vect n Nat -> Type -> Type where
  Scalar : a -> Tensor [] a
  Dimension : Vect n (Tensor d a) -> Tensor (n :: d) a

A type vector parameter describes tensor "dimensions" or "shape". I am currently trying to define a function for indexing safely Tensor. I planned to do this with help Fin, but I had a problem. Since it Tensorhas an unknown order, I may need any number of indexes, each of which requires a different upper bound. This means that indexes Vectwill not be enough, because each index will have a different type. This made me look at the use of tuples (called "pairs" in Idris?). I wrote the following function to calculate the required type.

TensorIndex : Vect n Nat -> Type
TensorIndex []      = ()
TensorIndex (d::[]) = Fin d
TensorIndex (d::ds) = (Fin d, TensorIndex ds)

This function worked as I expected, calculating the corresponding index type from the dimension vector.

> TensorIndex [4,4,3] -- (Fin 4, Fin 4, Fin 3)
> TensorIndex [2] -- Fin 2
> TensorIndex [] -- ()

index...

index : {d : Vect n Nat} -> TensorIndex d -> Tensor d a -> a
index () (Scalar x) = x
index (a,as) (Dimension xs) = index as $ index a xs
index a (Dimension xs) with (index a xs) | Tensor x = x

... ( , ).

Type mismatch between
         (A, B) (Type of (a,as))
and
         TensorIndex (n :: d) (Expected type)

, , TensorIndex , , , data; " ". ? TensorIndex , , ? , - index?

Answer 1

, () TensorIndex,

TensorIndex : Vect n Nat -> Type
TensorIndex []      = ()
TensorIndex (d::ds) = (Fin d, TensorIndex ds)

index : {ds : Vect n Nat} -> TensorIndex ds -> Tensor ds a -> a
index {ds = []} () (Scalar x) = x
index {ds = _ :: ds} (i, is) (Dimension xs) = index is (index i xs)

TensorIndex, ds = [_] ds = _::_::_ TensorIndex:

TensorIndex : Vect n Nat -> Type
TensorIndex []      = ()
TensorIndex (d::[]) = Fin d
TensorIndex (d::ds) = (Fin d, TensorIndex ds)

index : {ds : Vect n Nat} -> TensorIndex ds -> Tensor ds a -> a
index {ds = []} () (Scalar x) = x
index {ds = _ :: []} i (Dimension xs) with (index i xs) | (Scalar x) = x
index {ds = _ :: _ :: _} (i, is) (Dimension xs) = index is (index i xs)

, , - , index TensorIndex, TensorIndex ds .

Answer 2

, Tensor , Index .

, Vect n Nat, , . , , , : , .

module Tensor

import Data.Fin
import Data.Vect

tensor : Vect n Nat -> Type -> Type
tensor []        a = a
tensor (m :: ms) a = Vect m (tensor ms a)

data Index : Vect n Nat -> Type where
  Here : Index []
  At   : Fin m -> Index ms -> Index (m :: ms)

index : Index ms -> tensor ms a -> a
index Here     a = a
index (At k i) v = index i $ index k v