Scheme Programming Language :: Is there anything that lists can't do but pairs can?


	Is there anything that lists can't do but pairs can? hi Is there anything that lists can't do but pairs can? I can't seem to figure out why use pairs at all. It's anooying having to figure out the degenerate cases of pairs. lists seem more general, one extra null symbol won't kill anybody. Newbie response warning... On Wed, 04 Apr 2007 20:51:36 -0700, dillogimp wrote: > Is there anything that lists can't do but pairs can? Dunno. Building binary trees with pairs seems a lot neater than with lists that have dangling nulls at every internal node. Maybe that's a good enough reason? > I can't seem to figure out why use pairs at all. It's anooying having to > figure out the degenerate cases of pairs. lists seem more general, one > extra null symbol won't kill anybody. Pairs are a more atomic building block than lists. That seems to be a good enough reason to me. There would also seem to be a fairly significant space efficiency advantage for some sorts of data structures. Is it really such a hardship? My first real scheme program is still under a thousand lines, and that certainly isn't one of the issues causing me grief (yet). (verbosity of vector and struct element update operations, on the other hand...) Cheers, -- Andrew On Apr 4, 11:51 pm, dillog@gmail.com wrote: > hi > Is there anything that lists can't do but pairs can? > I can't seem to figure out why use pairs at all. > It's anooying having to figure out the degenerate cases of pairs. > lists seem more general, one extra null symbol won't kill anybody. I would argue the main value of distinct support for pairs in code is that you can indicate implicitly that something is a singleton. So if you see '(user . bob) in some code, you know the system is not designed to support >1 user. Singletons are so common in programming that having the construct of "pair" available makes for cleaner code. There are of course other reasons that admittedly could be dismissed as "missing the point", all having to do with the fact that they're "closer to the metal" On Apr 4, 9:51 pm, dillog@gmail.com wrote: > hi > Is there anything that lists can't do but pairs can? > I can't seem to figure out why use pairs at all. > It's anooying having to figure out the degenerate cases of pairs. > lists seem more general, one extra null symbol won't kill anybody. How would you construct a list without pairs? A node struct with "car" and "cdr" members? Brad On 4 Apr 2007 20:51:36 -0700, dillog@gmail.com wrote: >Is there anything that lists can't do but pairs can? Since it's possible to implement pairs using lists (and vice versa), no. >I can't seem to figure out why use pairs at all. Because they are more "fundamental" (in a sort of axiomatic sense) than lists. Implementing lists using pairs requires no extra baggage beyond an atomic object to represent the empty list. Implementing pairs using list requires a lot more in the way of rules and conventions. (Note that a pair does _not_ have the same behavior as a list with two elements.) >It's anooying having to figure out the degenerate cases of pairs. I don't understand this. There are no degenerate cases. If you've implemented generalized support for pairs, then both proper and improper lists (and anything else you can build out of pairs) comes for free. Perhaps you're thinking of the shorthand notation for lists, e.g.: (a b c) which is, of course, shorthand for (a . (b . (c . ()))) If you accept the notion that the former is shorthand, and that the latter represents the "genuine" structure of a list, you shouldn't have any trouble. Steve Schafer Fenestra Technologies Corp. http://www.fenestra.com/ In article <1175745096.358808.93@n59g2000hsh.googlegroups.com>, dillog@gmail.com wrote: > hi > Is there anything that lists can't do but pairs can? > I can't seem to figure out why use pairs at all. > It's anooying having to figure out the degenerate cases of pairs. > lists seem more general, one extra null symbol won't kill anybody. Pairs are isomorphic to two-element lists, so obviously anything you can do with one can be done with the other. The difference is efficiency: a pair requires only one data structure with two slots in it, while a two-element list requires two data structures, each with two slots. And accessing the second element of the 2-list requires an extra indirection. So you're doubling the memory use and slowing down half the data accesses, yet getting no benefit from doing so. -- Barry Margolin, bar@alum.mit.edu Arlington, MA * PLEASE post questions in newsgroups, not directly to me * * PLEASE don't copy me on replies, I'll read them in the group *