skaller wrote:

>Do you provide lists directly in the term calculus?
>Or are they just constructed from products and sums?
>  
>
Short answer: yes, lists are provided in the term calculus.

Long answer: Maple has no linked lists (ie lists based on nil and 
cons).  It has "automatically flattened n-tuples" - they are called 
"expression sequences".  When you see
(a list)               [a,b,c]
(a set)               {a,b,c}
(a function call) f(a,b,c)

all 3 contain the expression sequence a,b,c.  Two additional points:
1) expression sequences (and their contents) are uniquified [ie stored 
only once]
2) they are stored in contiguous memory, so that they are more 
array-like than list-like

While you may want your term language to support lists, supporting 
'flattened' n-tuples can be much simpler from a polymorphism point of 
view. The idea here is that a tagged datatype is just a pair tag + 
expression sequence, and you can defined all your polymorphic operators 
to "map into" the datatype by mapping onto the expression sequence.  
Experience shows that this is mightily convenient.  And most likely 
difficult as all #$%#$% to ``type''.

On the other hand, I was able to reflect this high degree of 
polymorphism in parts of my toy interpreter, where I could 'factor' a 
lot of my code quite nicely.  If only that 'tags' of an algebraic 
datatype were also first-class functions in Ocaml [as they are in 
Haskell], I would make my code considerably more elegant.

Jacques C.