remove items appearing in both lists

Given 2 lists Olist and Clist. I want to remove items that appears in
both list. How best to do this?

Say,

(setq Olist (list "a" "b" "c" "d" "e"))
(setq Clist (list "ee" "a" "d" "c" "bb"))

i want the result to be like

(setq Olist (list "b" "e"))
(setq Clist (list "ee" "bb"))

order doesn't matter.

i think i can go thru each element and build OlistNew, and removing
Clist to build a ClistNew. But the checking existance and building
item by item would be difficult or very inefficient i think but am not
sure about lisp here.

should i turn them both into hash table first for easy checking
existance?

Thanks.

Xah
∑ http://xahlee.org/

☄

Posted to too many groups by mistake. Sorry. Fixed follow up to just
lisp and emacs.

On Jul 20, 7:14Â*am, "xah...@gmail.com" <xah...@gmail.com> wrote:
> Given 2 lists Olist and Clist. I want to remove items that appears in
> both list. How best to do this?
>
> Say,
>
> (setq Olist (list "a" "b" "c" "d" "e"))
> (setq Clist (list "ee" "a" "d" "c" "bb"))
>
> i want the result to be like
>
> (setq Olist (list "b" "e"))
> (setq Clist (list "ee" "bb"))
>
> order doesn't matter.
>
> i think i can go thru each element and build OlistNew, and removing
> Clist to build a ClistNew. But the checking existance and building
> item by item would be difficult or very inefficient i think but am not
> sure about lisp here.
>
> should i turn them both into hash table first for easy checking
> existance?
>
> Thanks.
>
> Â* Xah
> ∑http://xahlee.org/
>
> ☄

On Jul 20, 3:16Â*pm, "xah...@gmail.com" <xah...@gmail.com> wrote:
> Posted to too many groups by mistake. Sorry.

That's going on a t-shirt :-)

> Fixed follow up to just
> lisp and emacs.
>
> On Jul 20, 7:14Â*am, "xah...@gmail.com" <xah...@gmail.com> wrote:
>
> > Given 2 lists Olist and Clist. I want to remove items that appears in
> > both list. How best to do this?
>
> > Say,
>
> > (setq Olist (list "a" "b" "c" "d" "e"))
> > (setq Clist (list "ee" "a" "d" "c" "bb"))
>
> > i want the result to be like
>
> > (setq Olist (list "b" "e"))
> > (setq Clist (list "ee" "bb"))
>
> > order doesn't matter.
>
> > i think i can go thru each element and build OlistNew, and removing
> > Clist to build a ClistNew. But the checking existance and building
> > item by item would be difficult or very inefficient i think but am not
> > sure about lisp here.
>
> > should i turn them both into hash table first for easy checking
> > existance?
>
> > Thanks.
>
> > Â* Xah
> > ∑http://xahlee.org/
>
> > ☄
>
>

xahlee@gmail.com wrote:

> Given 2 lists Olist and Clist. I want to remove items that appears in
> both list. How best to do this?
>
> Say,
>
> (setq Olist (list "a" "b" "c" "d" "e"))
> (setq Clist (list "ee" "a" "d" "c" "bb"))
>
> i want the result to be like
>
> (setq Olist (list "b" "e"))
> (setq Clist (list "ee" "bb"))
>
> order doesn't matter.

In F#, convert the lists to sets and use set theoretic operations:

let Olist, Clist = set Olist, set Clist
let union = Olist + Clist
let Olist, Clist = Olist - union, Clist - union

--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com/products/?u

Rainer Joswig and Kent Pitman suggested the Common Lisp solution:

(psetq Olist (set-difference Olist Clist :test #'string=)
Clist (set-difference Clist Olist :test #'string=))

Thanks to Rainer Joswig and Kent Pitman.

Jon Harrop wrote:

> In F#, convert the lists to sets and use set theoretic operations:
>
> let Olist, Clist = set Olist, set Clist
> let union = Olist + Clist
> let Olist, Clist = Olist - union, Clist - union

O, great. In Mathematica.

olist = {"a", "b", "c", "d", "e"};
clist = {"ee", "a", "d", "c", "bb"};

olist = Complement[olist, clist]
clist = Complement[clist, olist]

btw, if i'm curious and want to have a peek of docs of Caml or F# now
and then, is there a easy to use website?

--------------------------------------
David Kastrup offered a pure elisp solution:

David wrote:

«
(setq Olist (sort Olist 'string<) Clist (sort Clist 'string<))
(let (outolist outclist)
(while (and Olist Clist)
(cond ((string= (car Olist) (car Clist))
(pop Olist) (pop Clist))
((string< (car Olist) (car Clist))
(push (pop Olist) outolist))
(t (push (pop Clist) (outclist)))))
(setq Olist (nconc (nreverse outolist) Olist)
Clist (nconc (nreverse outclist) Clist)))

Untested, of course. But something like that should work.
»

Will there be a day when emacs lisp incorporate many of CL's highlevel
list manipulation functions? I think there's controversy... especially
adding CL's more complex features, but i think just adding highlevel
functions is very beneficial.

Xah
∑ http://xahlee.org/

☄

On Jul 22, 4:29 am, Jon Harrop <j...@ffconsultancy.com> wrote:
> xah...@gmail.com wrote:
> > Given 2 lists Olist and Clist. I want to remove items that appears in
> > both list. How best to do this?
>
> > Say,
>
> > (setq Olist (list "a" "b" "c" "d" "e"))
> > (setq Clist (list "ee" "a" "d" "c" "bb"))
>
> > i want the result to be like
>
> > (setq Olist (list "b" "e"))
> > (setq Clist (list "ee" "bb"))
>
> > order doesn't matter.
>
> In F#, convert the lists to sets and use set theoretic operations:
>
> let Olist, Clist = set Olist, set Clist
> let union = Olist + Clist
> let Olist, Clist = Olist - union, Clist - union
>
> --
> Dr Jon D Harrop, Flying Frog Consultancyhttp://www.ffconsultancy.com/products/?u

On 2008-07-20, xahlee@gmail.com <xahlee@gmail.com> wrote:
> Given 2 lists Olist and Clist. I want to remove items that appears in
> both list. How best to do this?
>
> Say,
>
> (setq Olist (list "a" "b" "c" "d" "e"))
> (setq Clist (list "ee" "a" "d" "c" "bb"))
>
> i want the result to be like
>
> (setq Olist (list "b" "e"))
> (setq Clist (list "ee" "bb"))

Since you're assigning to variables, wouldn't this be off-topic in
comp.lang.functional?

> order doesn't matter.

;; items common to both sets

(intersection '("a" "b" "c") '("b" "c" "d") :test #'equal)

-> ("b" "c")

;; items in the left set which are not in the right set

(set-difference '("a" "b" "c") '("b" "c" "d") :test #'equal)

-> ("a")

You want to remove (via set-difference) from each original list the
intersection of those two lists:

På Wed, 23 Jul 2008 08:49:03 +0200, skrev David Kastrup <dak@gnu.org>:

>
> The Common Lisp solution that you are clamoring for most certainly
> _isn't_ O(n lg n) but rather O(n^2). The same likely holds for the
> other "elegant" solutions based on a set abstraction. You can at best
> have O(n^2) behavior without making use of an order relation, because
> then you are reduced to comparing everything with everything.
>
> If we are not talking about similarly sized sets, the "elegant"
> solutions are O(m n), and the one using sorting is O(n lg n + m lg m).
>

Not entirely true.
You could store one set in a hash table without making assumptions about
order.
Then you have k * n complexity. I believe SBCL does this for large lists.
K here is a high number so for small lists the approach above is still
better.

As for order. Well if they are in order it is a merge or order n.
There is no reason you couldn't keep the set in order. (And sort it at
compile time if the elements are known in advance.)
Thus you can do better than that.

--------------
John Thingstad

On Jul 22, 10:33*pm, "xah...@gmail.com" <xah...@gmail.com> wrote:
> O, great. In Mathematica.
>
> olist = {"a", "b", "c", "d", "e"};
> clist = {"ee", "a", "d", "c", "bb"};
>
> olist = Complement[olist, clist]
> clist = Complement[clist, olist]

Sorry, my F# code was wrong. It should have been:

let olist = set ["a"; "b"; "c"; "d"; "e"]
let clist = set ["ee"; "a"; "d"; "c"; "bb"]
let olist, clist = olist - clist, clist - olist

> btw, if i'm curious and want to have a peek of docs of Caml or F# now
> and then, is there a easy to use website?

There is a site running OCamlJava somewhere but it is not the real
OCaml implementation (e.g. no tail calls).

Easiest to "apt-get install ocaml" under Linux or install Visual
Studio Shell and the F# distribution under Windows.

Cheers,
Jon Harrop.

"John Thingstad" <jpthing@online.no> writes:

> På Wed, 23 Jul 2008 08:49:03 +0200, skrev David Kastrup <dak@gnu.org>:
>
>>
>> The Common Lisp solution that you are clamoring for most certainly
>> _isn't_ O(n lg n) but rather O(n^2). The same likely holds for the
>> other "elegant" solutions based on a set abstraction. You can at best
>> have O(n^2) behavior without making use of an order relation, because
>> then you are reduced to comparing everything with everything.
>>
>> If we are not talking about similarly sized sets, the "elegant"
>> solutions are O(m n), and the one using sorting is O(n lg n + m lg m).
>>
>
> Not entirely true.
> You could store one set in a hash table without making assumptions
> about order.

Hash codes _provide_ an order relation.

> As for order. Well if they are in order it is a merge or order n.
> There is no reason you couldn't keep the set in order.

_Keeping_ in order is usually more expensive than bothering about order
only when it is needed.

> (And sort it at compile time if the elements are known in advance.)
> Thus you can do better than that.

You _are_ aware that the code I posted starts by a sort on both lists,
and returns an ordered list?

So if your data is in order, the code is trivial to change in order to
make use of that. Just throw out the initial calls to sort.

--
David Kastrup

On Jul 23, 7:49*am, David Kastrup <d...@gnu.org> wrote:
> Uh, it might be worth to add that only the last, explicit solution is
> guaranteed to be O(n lg n), efficient.
>
> The Common Lisp solution that you are clamoring for most certainly
> _isn't_ O(n lg n) but rather O(n^2). *The same likely holds for the
> other "elegant" solutions based on a set abstraction...

Both the OCaml and the F# are already asymptotically efficient (at
least as good as O(n log n)) because very efficient set
implementations are provided in their standard libraries. In
Mathematica 6, sets are also efficient.

Cheers,
Jon.