Search code examples
vectortuplesidrisdependent-typemap-function

Idris - map function on custom dependent data type fails

I am relatively new to idris and dependent-types and I encountered the following problem - I created a custom data type similar to vectors:

infixr 1 :::

data TupleVect : Nat -> Nat -> Type -> Type where
    Empty : TupleVect Z Z a
    (:::) : (Vect o a, Vect p a) ->
            TupleVect n m a ->
            TupleVect (n+o) (m+p) a

exampleTupleVect : TupleVect 5 4 Int
exampleTupleVect = ([1,2], [1]) ::: ([3,4],[2,3]) ::: ([5], [4]) ::: Empty

It is inductively constructed by adding tuples of vectors and indexed by the sum of the vector lengths in each tuple position.

I tried to implement a map function for my data type:

tupleVectMap : ((Vect k a, Vect l a) -> (Vect k b, Vect l b)) ->
               TupleVect n m a -> TupleVect n m b
tupleVectMap f Empty = Empty
tupleVectMap f (x ::: xs) = let fail = f x
                            in ?rest_of_definition

This yields the following type error: 

   |
20 | tupleVectMap f (x ::: xs) = let fail = f x
   |                             ~~~~~~~~~~~~~~ ...
When checking right hand side of tupleVectMap with expected type
        TupleVect (n + o) (m + p) b

Type mismatch between
        (Vect o a, Vect p a)
and
        (Vect k a, Vect l a)

It seems that the typechecker can't unify the lengths of the vectors in the extracted tuple x and the required lengths in the argument of f. However I don't understand why that is since k and l are just the type names indicating that f doesn't change the length of the given vectors.

I am even more perplexed since the following typechecks:

tupleVectMap' : TupleVect n m a -> TupleVect n m b
tupleVectMap' Empty = Empty
tupleVectMap' (x ::: xs) =
    let nonfail = f x
    in ?rest_of_definition
      where
        f : ((Vect k a, Vect l a) -> (Vect k b, Vect l b))

Here f has the exact same type signature. The only difference being that f is defined locally.

Solution

  • If you :set showimplicits in the refl you'll see the difference between the two functions.

    In tupleVectMap is

    f : (Data.Vect.Vect k a, Data.Vect.Vect l a) ->
    (Data.Vect.Vect k b, Data.Vect.Vect l b)
x : (Data.Vect.Vect o a, Data.Vect.Vect p a)

    Because k and o (l and p) are not necessary equal, x cannot be applied to f. Basically, if you call tupleVectMap, you already determined that f only accepts Vects of length k.

    While in tupleVectMap' it is

    f : {k : Prelude.Nat.Nat} -> {l : Prelude.Nat.Nat} ->
    (Data.Vect.Vect k a, Data.Vect.Vect l a) ->
    (Data.Vect.Vect k b, Data.Vect.Vect l b)
x : (Data.Vect.Vect o a, Data.Vect.Vect p a)

    Here f takes two implicit arguments to set the length of the Vects whenever it gets called. So f x {k=o} {l=p} works (though you don't have to specify the implicit arguments).

    It will work as well if you define your function type as 

    tupleVectMap : ({k, l : Nat} -> (Vect k a, Vect l a) -> (Vect k b, Vect l b)) ->
               TupleVect n m a -> TupleVect n m b