Same being anything from eq to equal in this case.
Right now I'm, using (not (intersection a b)). How does that stack up
vs. (and (= (list-length a) (list-length b))
(subsetp a b)) ?
I favored the intersection one just because it's shorter to type.
These look functionally equivalent to me, but I'm wondering if
there's something I've overlooked. I know the intersection one will
make a few conses sometimes, but that's not a concern for me at the
moment.
Or, is there simply a prettier way to determine that two lists have
all the same elements? I haven't found any standard functions yet to do
it.
--
B.B. --I am not a goat! thegoat4 at airmail.net
Fire the stupid--Vote.
B.B. wrote:
> Same being anything from eq to equal in this case.
>
> Right now I'm, using (not (intersection a b)). How does that stack up
> vs. (and (= (list-length a) (list-length b))
> (subsetp a b)) ?
> I favored the intersection one just because it's shorter to type.
> These look functionally equivalent to me, but I'm wondering if
> there's something I've overlooked. I know the intersection one will
> make a few conses sometimes, but that's not a concern for me at the
> moment.
> Or, is there simply a prettier way to determine that two lists have
> all the same elements? I haven't found any standard functions yet to do
> it.
>
From a set-theoretic perspective you want:
(and (subsetp a b) (subsetp b a))
From: Matthew Danish
Subject: Re: Good way to determine if two lists have all the same elements?
Date:
Message-ID: <20040419180759.GI25328@mapcar.org>
On Sun, Apr 18, 2004 at 10:54:54PM -0500, B.B. wrote:
> Same being anything from eq to equal in this case.
>
> Right now I'm, using (not (intersection a b)). How does that stack up
> vs. (and (= (list-length a) (list-length b))
> (subsetp a b)) ?
If I'm not mistaken, using intersection is incorrect:
[1]> (not (intersection '(a b c) '(a b)))
NIL
[2]> (not (intersection '(a b c) '(a b c)))
NIL
[3]> (not (intersection '(a b c) '()))
T
What you want to use is set-exclusive-or:
[4]> (not (set-exclusive-or '(a b c) '(a b)))
NIL
[5]> (not (set-exclusive-or '(a b c) '(a b c)))
T
[6]> (not (set-exclusive-or '(a b c) '()))
NIL
--
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
In article <······················@mapcar.org>,
Matthew Danish <·······@andrew.cmu.edu> wrote:
>On Sun, Apr 18, 2004 at 10:54:54PM -0500, B.B. wrote:
>> Same being anything from eq to equal in this case.
>>
>> Right now I'm, using (not (intersection a b)). How does that stack up
>> vs. (and (= (list-length a) (list-length b))
>> (subsetp a b)) ?
>
>If I'm not mistaken, using intersection is incorrect:
>
>[1]> (not (intersection '(a b c) '(a b)))
>NIL
>[2]> (not (intersection '(a b c) '(a b c)))
>NIL
>[3]> (not (intersection '(a b c) '()))
>T
>
>What you want to use is set-exclusive-or:
>
>[4]> (not (set-exclusive-or '(a b c) '(a b)))
>NIL
>[5]> (not (set-exclusive-or '(a b c) '(a b c)))
>T
>[6]> (not (set-exclusive-or '(a b c) '()))
>NIL
Ah! You're right. My brain farted while typing my message. I had
meant to type set-difference, which gives the correct results.
[11]> (not (set-difference '(a b c) '(a b c)))
T
[12]> (not (set-difference '(a b c) '(a b)))
NIL
[13]> (not (set-difference '(a b c) nil))
But I do like set-exclusive-or. Thanks.
--
B.B. --I am not a goat! thegoat4 at airmail.net
Fire the stupid--Vote.
From: Matthew Danish
Subject: Re: Good way to determine if two lists have all the same elements?
Date:
Message-ID: <20040420064901.GJ25328@mapcar.org>
On Mon, Apr 19, 2004 at 03:21:09PM -0500, B.B. wrote:
> Ah! You're right. My brain farted while typing my message. I had
> meant to type set-difference, which gives the correct results.
>
> [11]> (not (set-difference '(a b c) '(a b c)))
> T
> [12]> (not (set-difference '(a b c) '(a b)))
> NIL
> [13]> (not (set-difference '(a b c) nil))
Or not,
[1]> (not (set-difference '() '(a b c)))
T
SET-DIFFERENCE is not commutative.
> But I do like set-exclusive-or. Thanks.
Actually, I thought of this after using BIT-XOR on bit-vector sets. You
may want to consider Steven's advice regarding lists as sets.
Bit-vectors as sets make sense when you have a simple bijection from
your elements to the natural numbers.
--
; Matthew Danish <·······@andrew.cmu.edu>
; OpenPGP public key: C24B6010 on keyring.debian.org
; Signed or encrypted mail welcome.
; "There is no dark side of the moon really; matter of fact, it's all dark."
In article <······················@mapcar.org>,
Matthew Danish <·······@andrew.cmu.edu> wrote:
>On Mon, Apr 19, 2004 at 03:21:09PM -0500, B.B. wrote:
>> Ah! You're right. My brain farted while typing my message. I had
>> meant to type set-difference, which gives the correct results.
>>
>> [11]> (not (set-difference '(a b c) '(a b c)))
>> T
>> [12]> (not (set-difference '(a b c) '(a b)))
>> NIL
>> [13]> (not (set-difference '(a b c) nil))
>
>Or not,
>
>[1]> (not (set-difference '() '(a b c)))
>T
>
>SET-DIFFERENCE is not commutative.
Oh. Fortunately, the way I'm using it, it never happened to expose
that problem. But I would like to use something that would be correct
in unforseen cases.
>> But I do like set-exclusive-or. Thanks.
>
>Actually, I thought of this after using BIT-XOR on bit-vector sets. You
>may want to consider Steven's advice regarding lists as sets.
>Bit-vectors as sets make sense when you have a simple bijection from
>your elements to the natural numbers.
I'm still learning, so right now I'm trying to get to know the more
common functions and standard types in Lisp. My project at the moment
is implementing Thompson's construction as described in "Compiler Design
in C" but in Lisp instead. I figure it's a good way to get the hang of
things.
For now I have implemented all the states as simple lists. First
element is a cons of the state number and accepting action, every list
element after that is an edge. And an edge is a list with the first
element the character to move on, and the second element the state to
transfer to. Confused the shit out of myself until I discovered
*print-circle*. (:
I'm nearly finished. Once I complete it I plan to go back and redo
all of it with different goals in mind. Stuff like compactness vs.
execution speed. At that time I'll probably try to work in an object
model and make use of hash tables and pay a little more attention to
memory usage. Maybe stick it in a package too. I'll have to play with
macros too.
--
B.B. --I am not a goat! thegoat4 at airmail.net
Fire the stupid--Vote.
From: ·········@random-state.net
Subject: Re: Good way to determine if two lists have all the same elements?
Date:
Message-ID: <c63oot$80rm1$1@midnight.cs.hut.fi>
B.B. <·················@airmail.net.com.org.gov.tw.ch.ru> wrote:
> memory usage. Maybe stick it in a package too. I'll have to play with
^^^^^^^
Not aimed at you the OP, but all the tutorial writers and would be
authors: TEACH PACKAGES AND SYMBOLS EARLY!
The way I see it, the packages should be thought after basic repl
interaction and stuff like defun, but definitely before macros.
Packages are simple things, and make file a lot easier, but eg.
Grahams book ANSI Common Lisp manages to leave them to chapter 14
("Advanced Topics" !), and even then makes a mess of it.
One reason that I for a long time failed to "get" packages was
that they were explained too late: I had already built mental
models about symbols and packages that had only the most tenuous
connection to reality.
Cheers,
-- Nikodemus
From: Steven M. Haflich
Subject: Re: Good way to determine if two lists have all the same elements?
Date:
Message-ID: <4084AC45.7020500@alum.mit.edu>
All these comments are correct (modulo the necessary corrections and retractions)
but remember that the CL set operations are likely to have O^2 behavior simply
because they are very general. A Cl `set' can simultaneously contain objects
such as an integer, a float, a circulr list, a hashtable, and a file-stream.
This capability has interesting generality, but is otherwise fairly useless in
practical terms.
If you have _large_ sets, and if you have any a priory knowledge about the kind
of elements that can be in your sets, you are probably better off writing a
different reprentation of a set that can rely on sorting or hashing to achieve
Ologn efficiency on operations like this. The standard CL set functions are
mostly useful for low-bandwidth applications or rapid prototyping.