I tried to make this change over a year ago, now I'll try again.
The attached 2 patches tries to simplify and cleanup domain
IndexedList and List.
First patch, it moves almost all functions from IndexedList to
List. Because these functions are not related with index at all.
Second patch, it removes many usage of Lisp function call by
SPAD function call. This will not harm performance, because
in domain List we can do inline optimization (we can't inline
in IndexedList). There is also a benefit that these function
call will be type checked.
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
diff --git a/src/algebra/list.spad b/src/algebra/list.spad
index c6f2dc6e..6e07bffb 100644
--- a/src/algebra/list.spad
+++ b/src/algebra/list.spad
@@ -68,62 +68,56 @@ List(S : Type) : Exports == Implementation where
cycleMax ==> 1000 -- value used in checking for cycles
Qfirst ==> QCAR$Lisp
Qrest ==> QCDR$Lisp
- Qempty? ==> NULL$Lisp
- Qempty ==> NIL$Lisp
- Qeq ==> EQ$Lisp
- Qcons ==> CONS$Lisp
- Qset_first ==> qset_first$Lisp
- Qset_rest ==> qset_rest$Lisp
- Qreverse! ==> NREVERSE$Lisp
#x == LENGTH(x)$Lisp
- concat(s : S, x : %) == Qcons(s, x)
- eq?(x, y) == EQ(x, y)$Lisp
+ cons(s, x) == CONS(s, x)$Lisp
+ concat(s : S, x : %) == cons(s, x)
+ eq?(x, y) == EQ(x, y)$Lisp
first x == SPADfirst(x)$Lisp
- elt(x,"first") == SPADfirst(x)$Lisp
- empty() == Qempty
- empty? x == Qempty?(x)
+ elt(x, "first") == first x
+ empty() == NIL$Lisp
+ empty? x == NULL(x)$Lisp
rest x == CDR(x)$Lisp
- elt(x,"rest") == CDR(x)$Lisp
+ elt(x, "rest") == rest x
+ qsetfirst!(x, s) == qset_first(x, s)$Lisp
setfirst!(x, s) ==
- Qempty?(x) => error "Cannot update an empty list"
- Qset_first(x, s)
- qsetfirst!(x, s) == Qset_first(x, s)
+ empty? x => error "Cannot update an empty list"
+ qsetfirst!(x, s)
setelt!(x, "first", s) ==
- Qempty?(x) => error "Cannot update an empty list"
- Qset_first(x, s)
+ empty? x => error "Cannot update an empty list"
+ qsetfirst!(x, s)
+ qsetrest!(x, y) == qset_rest(x, y)$Lisp
setrest!(x, y) ==
- Qempty?(x) => error "Cannot update an empty list"
- Qset_rest(x, y)
- qsetrest!(x, y) == Qset_rest(x, y)
+ empty? x => error "Cannot update an empty list"
+ qsetrest!(x, y)
setelt!(x, "rest", y) ==
- Qempty?(x) => error "Cannot update an empty list"
- Qset_rest(x, y)
+ empty? x => error "Cannot update an empty list"
+ qsetrest!(x, y)
construct l == l pretend %
parts s == s pretend List S
- reverse! x == Qreverse!(x)
+ reverse! x == NREVERSE(x)$Lisp
reverse x == REVERSE(x)$Lisp
minIndex x == LISTMININDEX
maxIndex x == # x
rest(x, n) ==
for i in 1..n repeat
- if Qempty?(x) then error "index out of range"
+ if empty? x then error "index out of range"
x := Qrest x
x
copy x ==
- y : % := Qempty
- for i in 0.. while not Qempty?(x) repeat
- if Qeq(i,cycleMax) and cyclic? x then error "cyclic list"
- y := Qcons(Qfirst x, y)
+ y : % := empty()
+ for i in 0.. while not empty? x repeat
+ if i = cycleMax and cyclic? x then error "cyclic list"
+ y := cons(Qfirst x, y)
x := Qrest x
- Qreverse!(y)
+ reverse!(y)
leaves x ==
- empty? x => Qempty
- for i in 0.. while not Qempty? x repeat
- Qeq(i, cycleMax) and cyclic? x => error "cyclic list"
+ empty? x => empty()
+ for i in 0.. while not empty? x repeat
+ i = cycleMax and cyclic? x => error "cyclic list"
leaf? x => return [value x]
x := Qrest x
@@ -131,46 +125,46 @@ List(S : Type) : Exports == Implementation where
coerce(x) : OutputForm ==
-- displays cycle with overbar over the cycle
- y := (Qempty)@List(OutputForm)
+ y := empty()@List(OutputForm)
s := cycleEntry x
- while not(Qeq(x, s)) repeat
+ while not(eq?(x, s)) repeat
y := concat((first x)::OutputForm, y)
x := rest x
- y := Qreverse! y
- Qempty?(s) => bracket y
+ y := reverse! y
+ empty? s => bracket y
-- cyclic case: z is cyclic part
z := list((first x)::OutputForm)
- while not(Qeq(s, rest x)) repeat
+ while not(eq?(s, rest x)) repeat
x := rest x
z := concat((first x)::OutputForm, z)
- bracket concat!(y, overbar commaSeparate Qreverse! z)
+ bracket concat!(y, overbar commaSeparate reverse! z)
if S has BasicType then
x = y ==
- Qeq(x, y) => true
- while not Qempty?(x) and not Qempty?(y) repeat
+ eq?(x, y) => true
+ while not empty? x and not empty? y repeat
Qfirst x ~=$S Qfirst y => return false
x := Qrest x
y := Qrest y
- Qempty?(x) and Qempty?(y)
+ empty? x and empty? y
member?(s, x) ==
- while not Qempty?(x) repeat
+ while not empty? x repeat
if s = Qfirst x then return true else x := Qrest x
false
if S has SetCategory then
latex(x : %) : String ==
s : String := "\left["
- while not Qempty?(x) repeat
+ while not empty? x repeat
s := concat(s, latex(Qfirst x)$S)$String
x := Qrest x
- if not Qempty?(x) then s := concat(s, ", ")$String
+ if not empty? x then s := concat(s, ", ")$String
concat(s, " \right]")$String
hashUpdate!(s : HashState, x : %) : HashState ==
- while not Qempty?(x) repeat
+ while not empty? x repeat
s := hashUpdate!(s, Qfirst x)
x := Qrest x
s
@@ -178,24 +172,24 @@ List(S : Type) : Exports == Implementation where
-- Lots of code from parts of AGGCAT, repeated here to
-- get faster compilation
concat!(x : %, y : %) ==
- Qempty?(x) => y
+ empty? x => y
z := x
- while not Qempty?(Qrest(z)) repeat
+ while not empty? Qrest(z) repeat
z := Qrest z
- Qset_rest(z, y)
+ qsetrest!(z, y)
x
-- Then a quicky:
if S has BasicType then
removeDuplicates! l ==
p := l
- while not Qempty?(p) repeat
+ while not empty? p repeat
pp := p
f : S := Qfirst p
p := Qrest p
pr : %
- while not Qempty?(pr := Qrest(pp)) repeat
- if (Qfirst pr)@S = f then Qset_rest(pp, Qrest pr)
+ while not empty?(pr := Qrest(pp)) repeat
+ if (Qfirst pr)@S = f then qsetrest!(pp, Qrest pr)
else pp := pr
l
@@ -205,28 +199,28 @@ List(S : Type) : Exports == Implementation where
sort!(f, l) == mergeSort(f, l, #l)
merge!(f, p, q) ==
- Qempty?(p) => q
- Qempty?(q) => p
- Qeq(p, q) => error "cannot merge a list into itself"
+ empty? p => q
+ empty? q => p
+ eq?(p, q) => error "cannot merge a list into itself"
if f(Qfirst p, Qfirst q)
then (r := t := p; p := Qrest p)
else (r := t := q; q := Qrest q)
- while not Qempty?(p) and not Qempty?(q) repeat
+ while not empty? p and not empty? q repeat
if f(Qfirst p, Qfirst q)
- then (Qset_rest(t, p); t := p; p := Qrest p)
- else (Qset_rest(t, q); t := q; q := Qrest q)
- Qset_rest(t, if Qempty?(p) then q else p)
+ then (qsetrest!(t, p); t := p; p := Qrest p)
+ else (qsetrest!(t, q); t := q; q := Qrest q)
+ qsetrest!(t, if empty? p then q else p)
r
split!(p, n) ==
n < 1 => error "index out of range"
p := rest(p, (n - 1)::NonNegativeInteger)
q : % := Qrest p
- Qset_rest(p, Qempty)
+ qsetrest!(p, empty())
q
mergeSort(f, p, n) ==
- if n = 2 and f(first rest p, first p) then p := Qreverse! p
+ if n = 2 and f(first rest p, first p) then p := reverse! p
n < 3 => p
l := (n quo 2)::NonNegativeInteger
q := split!(p, l)
@@ -234,8 +228,6 @@ List(S : Type) : Exports == Implementation where
q := mergeSort(f, q, n - l)
merge!(f, p, q)
-
- cons(s, l) == concat(s, l)
append(l : %, t : %) == concat(l, t)
tails(x : %) : List(%) ==
[rest(x, i) for i in 0..(#x - 1)]
@@ -248,7 +240,7 @@ List(S : Type) : Exports == Implementation where
-- convinced that `xval' is a S. Duhhh! MCD.
--for xval in x repeat
-- OMwrite(dev, xval, false)
- while not empty?(x) repeat
+ while not empty? x repeat
OMwrite(dev, first x, false)
x := rest x
OMputEndApp(dev)
diff --git a/src/algebra/list.spad b/src/algebra/list.spad
index e2c77e07..c6f2dc6e 100644
--- a/src/algebra/list.spad
+++ b/src/algebra/list.spad
@@ -2,205 +2,19 @@
++ Author: Michael Monagan
++ Date Created: Sep 1987
++ Basic Operations:
-++ \#, concat, concat!, construct, copy, elt, empty,
-++ empty?, eq?, first, member?, merge!, mergeSort, minIndex,
-++ parts, removeDuplicates!, rest, reverse, reverse!,
-++ setelt, setfirst!, setrest!, sort!, split!
++ Related Constructors: List
++ Also See:
++ AMS Classification:
++ Keywords: list, aggregate, index
++ Description:
-++ \spadtype{IndexedList} is a basic implementation of
-++ \spadtype{ListAggregate}, often using functions in the underlying
-++ LISP system. The second parameter to the constructor (\spad{mn})
-++ is the beginning index of the list. That is, if \spad{l} is a
-++ list, then \spad{elt(l, mn)} is the first value. This constructor
-++ is probably best viewed as the implementation of singly-linked
-++ lists that are addressable by index rather than as a mere wrapper
-++ for LISP lists.
-IndexedList(S : Type, mn : Integer) : Exports == Implementation where
- cycleMax ==> 1000 -- value used in checking for cycles
-
--- The following seems to be a bit out of date, but is kept in case
--- a knowledgeable person wants to update it:
--- The following LISP dependencies are divided into two groups
--- Those that are required
--- CONS, EQ, NIL, NULL, QCAR, QCDR, RPLACA, RPLACD
--- Those that are included for efficiency only
--- NEQ, LIST, CAR, CDR, NCONC2, NREVERSE, LENGTH
--- Also REVERSE, since it's called in Polynomial Ring
-
- Qfirst ==> QCAR$Lisp
- Qrest ==> QCDR$Lisp
- Qempty? ==> NULL$Lisp
- Qempty ==> NIL$Lisp
- Qeq ==> EQ$Lisp
- Qcons ==> CONS$Lisp
- Qset_first ==> qset_first$Lisp
- Qset_rest ==> qset_rest$Lisp
- Qreverse! ==> NREVERSE$Lisp
-
- Exports ==> ListAggregate S
- Implementation ==>
- add
- #x == LENGTH(x)$Lisp
- concat(s : S, x : %) == Qcons(s, x)
- eq?(x, y) == EQ(x, y)$Lisp
- first x == SPADfirst(x)$Lisp
- elt(x,"first") == SPADfirst(x)$Lisp
- empty() == Qempty
- empty? x == Qempty?(x)
- rest x == CDR(x)$Lisp
- elt(x,"rest") == CDR(x)$Lisp
- setfirst!(x, s) ==
- Qempty?(x) => error "Cannot update an empty list"
- Qset_first(x, s)
- qsetfirst!(x, s) == Qset_first(x, s)
- setelt!(x, "first", s) ==
- Qempty?(x) => error "Cannot update an empty list"
- Qset_first(x, s)
- setrest!(x, y) ==
- Qempty?(x) => error "Cannot update an empty list"
- Qset_rest(x, y)
- qsetrest!(x, y) == Qset_rest(x, y)
- setelt!(x, "rest", y) ==
- Qempty?(x) => error "Cannot update an empty list"
- Qset_rest(x, y)
- construct l == l pretend %
- parts s == s pretend List S
- reverse! x == Qreverse!(x)
- reverse x == REVERSE(x)$Lisp
- minIndex x == mn
-
- rest(x, n) ==
- for i in 1..n repeat
- if Qempty?(x) then error "index out of range"
- x := Qrest x
- x
-
- copy x ==
- y : % := Qempty
- for i in 0.. while not Qempty?(x) repeat
- if Qeq(i,cycleMax) and cyclic? x then error "cyclic list"
- y := Qcons(Qfirst x, y)
- x := Qrest x
- Qreverse!(y)
-
- leaves x ==
- empty? x => Qempty
- for i in 0.. while not Qempty? x repeat
- Qeq(i, cycleMax) and cyclic? x => error "cyclic list"
- leaf? x => return [value x]
- x := Qrest x
-
- if S has CoercibleTo(OutputForm) then
-
- coerce(x) : OutputForm ==
- -- displays cycle with overbar over the cycle
- y := (Qempty)@List(OutputForm)
- s := cycleEntry x
- while not(Qeq(x, s)) repeat
- y := concat((first x)::OutputForm, y)
- x := rest x
- y := Qreverse! y
- Qempty?(s) => bracket y
- -- cyclic case: z is cyclic part
- z := list((first x)::OutputForm)
- while not(Qeq(s, rest x)) repeat
- x := rest x
- z := concat((first x)::OutputForm, z)
- bracket concat!(y, overbar commaSeparate Qreverse! z)
-
- if S has BasicType then
-
- x = y ==
- Qeq(x, y) => true
- while not Qempty?(x) and not Qempty?(y) repeat
- Qfirst x ~=$S Qfirst y => return false
- x := Qrest x
- y := Qrest y
- Qempty?(x) and Qempty?(y)
-
- member?(s, x) ==
- while not Qempty?(x) repeat
- if s = Qfirst x then return true else x := Qrest x
- false
-
- if S has SetCategory then
- latex(x : %) : String ==
- s : String := "\left["
- while not Qempty?(x) repeat
- s := concat(s, latex(Qfirst x)$S)$String
- x := Qrest x
- if not Qempty?(x) then s := concat(s, ", ")$String
- concat(s, " \right]")$String
-
- hashUpdate!(s : HashState, x : %) : HashState ==
- while not Qempty?(x) repeat
- s := hashUpdate!(s, Qfirst x)
- x := Qrest x
- s
-
- -- Lots of code from parts of AGGCAT, repeated here to
- -- get faster compilation
- concat!(x : %, y : %) ==
- Qempty?(x) => y
- z := x
- while not Qempty?(Qrest(z)) repeat
- z := Qrest z
- Qset_rest(z, y)
- x
-
- -- Then a quicky:
- if S has BasicType then
- removeDuplicates! l ==
- p := l
- while not Qempty?(p) repeat
- pp := p
- f : S := Qfirst p
- p := Qrest p
- pr : %
- while not Qempty?(pr := Qrest(pp)) repeat
- if (Qfirst pr)@S = f then Qset_rest(pp, Qrest pr)
- else pp := pr
- l
-
- -- then sorting
- mergeSort : ((S, S) -> Boolean, %, Integer) -> %
-
- sort!(f, l) == mergeSort(f, l, #l)
-
- merge!(f, p, q) ==
- Qempty?(p) => q
- Qempty?(q) => p
- Qeq(p, q) => error "cannot merge a list into itself"
- if f(Qfirst p, Qfirst q)
- then (r := t := p; p := Qrest p)
- else (r := t := q; q := Qrest q)
- while not Qempty?(p) and not Qempty?(q) repeat
- if f(Qfirst p, Qfirst q)
- then (Qset_rest(t, p); t := p; p := Qrest p)
- else (Qset_rest(t, q); t := q; q := Qrest q)
- Qset_rest(t, if Qempty?(p) then q else p)
- r
-
- split!(p, n) ==
- n < 1 => error "index out of range"
- p := rest(p, (n - 1)::NonNegativeInteger)
- q : % := Qrest p
- Qset_rest(p, Qempty)
- q
-
- mergeSort(f, p, n) ==
- if n = 2 and f(first rest p, first p) then p := Qreverse! p
- n < 3 => p
- l := (n quo 2)::NonNegativeInteger
- q := split!(p, l)
- p := mergeSort(f, p, l)
- q := mergeSort(f, q, n - l)
- merge!(f, p, q)
-
+++ \spadtype{IndexedList} is an implementation of
+++ \spadtype{ListAggregate}, the beginning index of the list
+++ is the second parameter to the constructor (\spad{mn}).
+++ That is, if \spad{l} is a
+++ list, then \spad{elt(l, mn)} is the first value.
+IndexedList(S : Type, mn : Integer) : ListAggregate S == List S add
+ minIndex x == mn
+ maxIndex x == mn + # x - 1
)abbrev domain LIST List
++ Author: Michael Monagan
@@ -219,7 +33,7 @@ IndexedList(S : Type, mn : Integer) : Exports == Implementation where
++ \spadtype{List} implements singly-linked lists that are
++ addressable by indices; the index of the first element
++ is 1. In addition to the operations provided by
-++ \spadtype{IndexedList}, this constructor provides some
+++ \spadtype{ListAggregate}, this constructor provides some
++ LISP-like functions such as \spadfun{cons} and \spadfun{append}.
List(S : Type) : Exports == Implementation where
LISTMININDEX ==> 1 -- this is the minimum list index
@@ -250,8 +64,177 @@ List(S : Type) : Exports == Implementation where
++ The order of elements in the resulting list is unspecified.
if S has OpenMath then OpenMath
- Implementation ==>
- IndexedList(S, LISTMININDEX) add
+ Implementation ==> add
+ cycleMax ==> 1000 -- value used in checking for cycles
+ Qfirst ==> QCAR$Lisp
+ Qrest ==> QCDR$Lisp
+ Qempty? ==> NULL$Lisp
+ Qempty ==> NIL$Lisp
+ Qeq ==> EQ$Lisp
+ Qcons ==> CONS$Lisp
+ Qset_first ==> qset_first$Lisp
+ Qset_rest ==> qset_rest$Lisp
+ Qreverse! ==> NREVERSE$Lisp
+
+ #x == LENGTH(x)$Lisp
+ concat(s : S, x : %) == Qcons(s, x)
+ eq?(x, y) == EQ(x, y)$Lisp
+ first x == SPADfirst(x)$Lisp
+ elt(x,"first") == SPADfirst(x)$Lisp
+ empty() == Qempty
+ empty? x == Qempty?(x)
+ rest x == CDR(x)$Lisp
+ elt(x,"rest") == CDR(x)$Lisp
+ setfirst!(x, s) ==
+ Qempty?(x) => error "Cannot update an empty list"
+ Qset_first(x, s)
+ qsetfirst!(x, s) == Qset_first(x, s)
+ setelt!(x, "first", s) ==
+ Qempty?(x) => error "Cannot update an empty list"
+ Qset_first(x, s)
+ setrest!(x, y) ==
+ Qempty?(x) => error "Cannot update an empty list"
+ Qset_rest(x, y)
+ qsetrest!(x, y) == Qset_rest(x, y)
+ setelt!(x, "rest", y) ==
+ Qempty?(x) => error "Cannot update an empty list"
+ Qset_rest(x, y)
+ construct l == l pretend %
+ parts s == s pretend List S
+ reverse! x == Qreverse!(x)
+ reverse x == REVERSE(x)$Lisp
+ minIndex x == LISTMININDEX
+ maxIndex x == # x
+
+ rest(x, n) ==
+ for i in 1..n repeat
+ if Qempty?(x) then error "index out of range"
+ x := Qrest x
+ x
+
+ copy x ==
+ y : % := Qempty
+ for i in 0.. while not Qempty?(x) repeat
+ if Qeq(i,cycleMax) and cyclic? x then error "cyclic list"
+ y := Qcons(Qfirst x, y)
+ x := Qrest x
+ Qreverse!(y)
+
+ leaves x ==
+ empty? x => Qempty
+ for i in 0.. while not Qempty? x repeat
+ Qeq(i, cycleMax) and cyclic? x => error "cyclic list"
+ leaf? x => return [value x]
+ x := Qrest x
+
+ if S has CoercibleTo(OutputForm) then
+
+ coerce(x) : OutputForm ==
+ -- displays cycle with overbar over the cycle
+ y := (Qempty)@List(OutputForm)
+ s := cycleEntry x
+ while not(Qeq(x, s)) repeat
+ y := concat((first x)::OutputForm, y)
+ x := rest x
+ y := Qreverse! y
+ Qempty?(s) => bracket y
+ -- cyclic case: z is cyclic part
+ z := list((first x)::OutputForm)
+ while not(Qeq(s, rest x)) repeat
+ x := rest x
+ z := concat((first x)::OutputForm, z)
+ bracket concat!(y, overbar commaSeparate Qreverse! z)
+
+ if S has BasicType then
+
+ x = y ==
+ Qeq(x, y) => true
+ while not Qempty?(x) and not Qempty?(y) repeat
+ Qfirst x ~=$S Qfirst y => return false
+ x := Qrest x
+ y := Qrest y
+ Qempty?(x) and Qempty?(y)
+
+ member?(s, x) ==
+ while not Qempty?(x) repeat
+ if s = Qfirst x then return true else x := Qrest x
+ false
+
+ if S has SetCategory then
+ latex(x : %) : String ==
+ s : String := "\left["
+ while not Qempty?(x) repeat
+ s := concat(s, latex(Qfirst x)$S)$String
+ x := Qrest x
+ if not Qempty?(x) then s := concat(s, ", ")$String
+ concat(s, " \right]")$String
+
+ hashUpdate!(s : HashState, x : %) : HashState ==
+ while not Qempty?(x) repeat
+ s := hashUpdate!(s, Qfirst x)
+ x := Qrest x
+ s
+
+ -- Lots of code from parts of AGGCAT, repeated here to
+ -- get faster compilation
+ concat!(x : %, y : %) ==
+ Qempty?(x) => y
+ z := x
+ while not Qempty?(Qrest(z)) repeat
+ z := Qrest z
+ Qset_rest(z, y)
+ x
+
+ -- Then a quicky:
+ if S has BasicType then
+ removeDuplicates! l ==
+ p := l
+ while not Qempty?(p) repeat
+ pp := p
+ f : S := Qfirst p
+ p := Qrest p
+ pr : %
+ while not Qempty?(pr := Qrest(pp)) repeat
+ if (Qfirst pr)@S = f then Qset_rest(pp, Qrest pr)
+ else pp := pr
+ l
+
+ -- then sorting
+ mergeSort : ((S, S) -> Boolean, %, Integer) -> %
+
+ sort!(f, l) == mergeSort(f, l, #l)
+
+ merge!(f, p, q) ==
+ Qempty?(p) => q
+ Qempty?(q) => p
+ Qeq(p, q) => error "cannot merge a list into itself"
+ if f(Qfirst p, Qfirst q)
+ then (r := t := p; p := Qrest p)
+ else (r := t := q; q := Qrest q)
+ while not Qempty?(p) and not Qempty?(q) repeat
+ if f(Qfirst p, Qfirst q)
+ then (Qset_rest(t, p); t := p; p := Qrest p)
+ else (Qset_rest(t, q); t := q; q := Qrest q)
+ Qset_rest(t, if Qempty?(p) then q else p)
+ r
+
+ split!(p, n) ==
+ n < 1 => error "index out of range"
+ p := rest(p, (n - 1)::NonNegativeInteger)
+ q : % := Qrest p
+ Qset_rest(p, Qempty)
+ q
+
+ mergeSort(f, p, n) ==
+ if n = 2 and f(first rest p, first p) then p := Qreverse! p
+ n < 3 => p
+ l := (n quo 2)::NonNegativeInteger
+ q := split!(p, l)
+ p := mergeSort(f, p, l)
+ q := mergeSort(f, q, n - l)
+ merge!(f, p, q)
+
+
cons(s, l) == concat(s, l)
append(l : %, t : %) == concat(l, t)
tails(x : %) : List(%) ==
