Subject: Re: intersection
From: Erik Naggum <>
Date: 28 Jan 2004 20:57:47 +0000
Newsgroups: comp.lang.lisp
Message-ID: <>

* 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.