On Thu, Nov 11, 2010 at 12:25:02PM -0500, John Cowan wrote: > Yi DAI scripsit: > > > Why do we have both list and dotted-list, given that the former is just a > > special case (terminated by nil) of the latter? Can we simply live with the > > latter? > > Conceptually, lists are the basic functional programming data structure: > sequential with O(n) access and shareable (in Lisp/Scheme, also mutable). > For historical reasons, lists are not primitive in Scheme but are > implemented using pairs, and this fact is exposed to Scheme programmers.
This way of thinking about it may be helpful: Lists are *a* basic functional programming structure. N-tuples, for different N, are another. The most striking redundancy is that Scheme has both pairs and length 2 vectors. These are distinct objects that fill the same conceptual role. Conceptually, a list is type-homogeneous, and lists of different length (whose members have the same type) are of the same type. N-tuples may be type-heterogeneous, and n-tuples of different length are of different types, no matter what type their members. It is not necessary to implement lists on top of n-tuples, but it is possible to do so, and Scheme does. Conceptually, the operation that takes a head and a tail list and returns a new list is different than the operation that takes two objects and returns a pair (i.e. a 2-tuple) of them. But given Scheme's implementation of lists, these operations are both spelled "cons". (Because of the pair/vector redundancy, the second operation is also implemented by "vector".) Since Scheme is dynamically typed, the conceptual type constraints I described are either unobvious or unenforced. I'd say they are unobvious. They're still there, constraining the use of operations like map and fold and so on. If you map some function that accepts either ints or bools as arguments over your list, then the list can be regarded as homogeneously having a union type, int-or-bool. In statically-typed functional languages, you'd have to express that explicitly, by boxing the elements inside an Either-type. -- Jim Pryor prof...@jimpryor.net _______________________________________________ Chicken-users mailing list Chicken-users@nongnu.org http://lists.nongnu.org/mailman/listinfo/chicken-users
