Subject: Re: intersection From: Erik Naggum <erik@naggum.no> Date: 28 Jan 2004 20:57:47 +0000 Newsgroups: comp.lang.lisp Message-ID: <3284312267277380KL2065E@naggum.no> * Tuang | Both of these replies (thank you, BTW) seem to be saying that the | result of performing an intersection on lists containing duplicate | members is undefined, at least with respect to the number of | duplicates that may show up in the result. That's a much stronger | statement than the "may have duplicates" line in the spec. Please, this requires attention to detail. It is not «undefined» just because what you want to have defined is not defined. This is like literary analysis in that you can choose one of two possible modi operandi in your approach to a text: (A) to regard the text as the true source of its meaning and to spend your energy on understanding what the author meant, or (B) to regard yourself as the true source of meaning in your personal universe and to spend your energy on proving that what you mean is in the text. There is no limit to what you can find support for in a text if you set your mind to it. The challenge is therefore not to find support for what you believe, but to explain why you believe it in the face of relevant counter-evidence. | With that much description of an implementation dependency that could | have been covered with "the first input to nintersection is destroyed", | I didn't think "may have duplicates" would imply "the number of members | in the result is so undefined that even within the same implementation | the length of X i'sect Y isn't guaranteed to be the same as the length | of Y i'sect X. You draw some pretty annoyingly misguided conclusions from the evidence before you, and it is actually hard for me to muster all the energy to respond to the clear impression that you have already made up your mind about something that you do not have sufficient information to make up your mind about. I just don't have the energy to fight someone who insists that his misguided beliefs must be correct and therefore the rest of the world is wrong, but the more you insist, the more the rest of the world needs to be shown that you are misguided. The obvious implementation of INTERSECTION is the trivial (defun intersection (list-1 list-2-not) (loop for elt in list-1 if (member elt list-2) collect elt)) which happens to produce exactly the results you observe. With the exception of the key and test arguments, which I have omitted for the sake of clarity, but which cry out for optimization, I would be very surprised if anyone has implemented this differently. (Barring, of course, LOOP allergies.) | Of course, Lisp makes it easy for me to define it any way I like and | implement it in about half a dozen lines of code, so it doesn't matter | in that respect. I was thinking, though, that I was going to learn | how I *ought* to define it, mistakenly thinking that all of the Lisp | builtins, except where explicitly noted, had evolved to very rigidly | defined algorithms years ago. They generally have. Just because you don't find them intuitively evident does not mean that they have not evolved thusly. -- Erik Naggum | Oslo, Norway 2004-028 Act from reason, and failure makes you rethink and study harder. Act from faith, and failure makes you blame someone and push harder.