idris - Dependent types: enforcing global properties in inductive types -

i have following inductive type myvec:

import data.vect  data myvec: {k: nat} -> vect k nat -> type   nil: myvec []   (::): {k, n: nat} -> {v: vect k nat} -> vect n nat -> myvec v -> myvec (n :: v)  -- example: val: myvec [3,2,3] val = [[2,1,2], [0,2], [1,1,0]] 

that is, type specifies lengths of vectors inside myvec.

the problem is, val have k = 3 (k number of vectors inside myvec), ctor :: not know fact. first build myvec k = 1, 2, , 3. makes impossible define constraints based on final shape of value.

for example, cannot constrain values strictly less k. accepting vects of fin (s k) instead of vects of nat rule out valid values, because last vectors (the first inserted ctor) "know" smaller value of k, , stricter contraint.

or, example, cannot enforce following constraint: the vector @ position cannot contain number i. because final position of vector in container not known ctor (it automatically known if final value of k known).

so question is, how can enforce such global properties?

there (at least) 2 ways it, both of may require tracking additional information in order check property.

enforcing properties in data definition

enforcing elements < k

i cannot constrain values strictly less k. accepting vects of fin (s k) instead of vects of nat rule out valid values...

you right changing definition of myvect have vect n (fin (s k)) in not correct.

however, not hard fix generalizing myvect polymorphic, follows.

data myvec: (a : type) -> {k: nat} -> vect k nat -> type   nil: {a : type} -> myvec []   (::): {a : type} -> {k, n: nat} -> {v: vect k nat} -> vect n -> myvec v -> myvec (n :: v)  val : myvec (fin 3) [3,2,3] val = [[2,1,2], [0,2], [1,1,0]] 

the key solution separating type of vector k in definition of myvec, , then, @ top level, using "global value of k constrain type of vector elements.

enforcing vector @ position i not contain i

i cannot enforce vector @ position cannot contain number because final position of vector in container not known constructor.

again, solution generalize data definition keep track of necessary information. in case, we'd keep track of current position in final value be. call index. generalize a passed current index. finally, @ top level, pass in predicate enforcing value not equal index.

data myvec': (a : nat -> type) -> (index : nat) -> {k: nat} -> vect k nat -> type   nil: {a : nat -> type} -> {index : nat} -> myvec' index []   (::): {a : nat -> type} -> {k, n, index: nat} -> {v: vect k nat} ->         vect n (a index) -> myvec' (s index) v -> myvec' index (n :: v)  val : myvec' (\n => (m : nat ** (n == m = false))) 0 [3,2,3] val = [[(2 ** refl),(1 ** refl),(2 ** refl)], [(0 ** refl),(2 ** refl)], [(1 ** refl),(1 ** refl),(0 ** refl)]] 

enforcing properties after fact

another, simpler way it, not enforce property in data definition, write predicate after fact.

enforcing elements < k

for example, can write predicate checks whether elements of vectors < k, , assert our value has property.

wf : (final_length : nat) -> {k : nat} -> {v : vect k nat} -> myvec v -> bool wf final_length [] = true wf final_length (v :: mv) = isnothing (find (\x => x >= final_length) v) && wf final_length mv  val : (mv : myvec [3,2,3] ** wf 3 mv = true) val = ([[2,1,2], [0,2], [1,1,0]] ** refl) 

enforcing vector @ position i not contain i

again, can express property checking it, , asserting value has property.

wf : (index : nat) -> {k : nat} -> {v : vect k nat} -> myvec v -> bool wf index [] = true wf index (v :: mv) = isnothing (find (\x => x == index) v) && wf (s index) mv  val : (mv : myvec [3,2,3] ** wf 0 mv = true) val = ([[2,1,2], [0,2], [1,1,0]] ** refl)