The problem is very simple - as long as a list is homogenous or it is a finite either-of algebraic data type, you could infer the type of a function on these -

The problem is very simple - as long as a list is homogenous or it is a finite either-of algebraic data type, you could infer the type of a function on these - it could be a another homogenous list or a value if some other type. As long as a list could contain anything then it could be mapped to another list of anything (a list of symbols, numbers, etc.) Or a value. Basically, we could say a pointer or a list of pointers, which by definition could point to any kind of a type-tagged value. Types a-la (* -> *) -> [*] -> [*] are't very useful, but this is what we have in Lisps. Moreover, as long as there is no difference between a pointer to a list and pointer to a value (these are just bindings of symbols to type-tagged values) we could have procedures of type * -> * -> * Lisp stands for LISt Processing after all, for performing so-called symbolic manipulations (like our minds do) and this is a pretty good "type" for a procedure doing a symbolic transformation. So, all the values have type-tags. Add NIL and T, structural types such as arrays or structs, and you will get a crude type hierarchy of a Lisp. Our lists aren't sets (homogenous) so all the typing based on Set theory is of no use.