Dear epigrammers...
I hope the attached code isn't considered too long for a mailing list.
Here's the train of thought: Define a Tuple type parameterised by the
list of types of its elements, define vectors of length n as
usual. Now if a tuple happens to be such that it contains only vectors
over the same type X, but of possibly different lengths, there should
be a tuple concat function.
I tried to define it, but epigram thinks there is a type error in my
last clause.
------------------------------------------------------------------------------
( X : * ! ( x : X ; xs : List X !
data !------------! where (--------------! ; !----------------------!
! List X : * ) ! nil : List X ) ! cons x xs : List X )
------------------------------------------------------------------------------
( XS : List * ! ( x : X ; t : Tuple XS !
data !-------------! where (---------------! ; !-----------------------!
! Tuple XS ! ! unit : ! ! tcons x t : !
! : * ) ! Tuple (nil) ) ! Tuple (cons X XS) )
------------------------------------------------------------------------------
data (----------! where (-------------! ; (--------------!
! Bool : * ) ! true : Bool ) ! false : Bool )
------------------------------------------------------------------------------
( n : Nat !
data (---------! where (------------! ; !-------------!
! Nat : * ) ! zero : Nat ) ! suc n : Nat )
------------------------------------------------------------------------------
( n : Nat ; X : * ! ( x : X ; xs : vec n X !
data !------------------! where (--------------! ; !-----------------------!
! vec n X : * ) ! vnil : ! ! vcons x xs : !
! vec zero X ) ! vec (suc n) X )
------------------------------------------------------------------------------
( ns : List Nat ; X : * !
let !------------------------!
! nvecs ns X : List * )
nvecs ns X <= rec ns
{ nvecs x X <= case x
{ nvecs nil X => nil
nvecs (cons x xs) X => cons (vec x X) (nvecs xs X)
}
}
------------------------------------------------------------------------------
( n : Nat ; m : Nat !
let !--------------------!
! plus n m : Nat )
plus n m <= rec n
{ plus x m <= case x
{ plus zero m => m
plus (suc n) m => suc (plus n m)
}
}
------------------------------------------------------------------------------
( u : vec n X ; v : vec m X !
let !-------------------------------!
! append u v : vec (plus n m) X )
append u v <= rec u
{ append x v <= case x
{ append vnil v => v
append (vcons x xs) v => vcons x (append xs v)
}
}
------------------------------------------------------------------------------
( f : X -> Y -> Y ; a : Y ; ns : List X !
let !-----------------------------------------!
! fold f a ns : Y )
fold f a ns <= rec ns
{ fold f a x <= case x
{ fold f a nil => a
fold f a (cons x xs) => f x (fold f a xs)
}
}
------------------------------------------------------------------------------
( ns : List Nat !
let !---------------!
! sum ns : Nat )
sum ns => fold plus zero ns
------------------------------------------------------------------------------
( ns : List Nat ; t : Tuple (nvecs ns X) !
let !-----------------------------------------!
! tconcat t : vec (sum ns) X )
tconcat t <= rec t
{ tconcat x <= case x
{ tconcat x <= case ns
{ tconcat unit => vnil
}
tconcat x' <= rec ns
{ tconcat x'' <= case x
{ tconcat (tcons x' t) [=>append x' (concat t)]
}
}
}
}
------------------------------------------------------------------------------
It's hard to follow non-interactively, due to the way epigram renames
variables. The 'x' in the line "{ tconcat x'' <= case x" was in fact
the list formerly known as 'ns'.
Furthermore when I reimport this into epigram en masse it gets
confused, now flagging type errors at the case statements. It looks
like it is generating variable names differently now. I just replaced
the whole body of tconcat with a shed, and now I have the following
mystifying information from horace:
: List Nat ; ' : * ; x : Tuple (nvecs ')
It seems to have renamed ns to empty string, and X to emptystring
primed.
Going back to the interactive approach (putting the type declaration
of tconcat back into sheds and re-elaborating fixes the variable name
problems), this time doing the case statements in the other order, I
get as far as:
tconcat t <= rec t
{ tconcat x <= case ns
{ tconcat x => vnil
tconcat x' <= case x'
{ tconcat (tcons x' t) [=>append x' (tconcat t)]
}
}
}
Horace helpfully tells me that the type of tconcat (tcons x' t)
is supposed to be:
vec (plus x (fold (lam n;m => plus n m) zero xs)) X
and that it already knows;
x': vec x X
t : Tuple (nvecs xs X)
it seems to me that it should be able to typecheck (append x' (tconcat
t)) as having precisley the required type, but it doesn't seem to.
Jules