tags:

views:

1096

answers:

8

I need something like this, a collection of elements which contains no duplicates of any element. Does Common Lisp, specifically SBCL, have any thing like this?

+1  A: 

Not that I'm aware of, but you can use hash tables for something quite similar.

Chris Jester-Young
A: 

Lisp hashtables are CLOS based. Specs here.

dsm
Umm... CL's standard hash tables _are_ instances of the CLOS class HASH-TABLE, which you can define methods for without worries. Furthermore, the article you link to talks about a kind of object system that isn't like CLOS at all. In CLOS, methods belong to generic functions, not objects.
Matthias Benkard
My bad.... I'm editing the response
dsm
Common Lisp hashtables are wrapped in CLOS. I don't know in what sense they're "CLOS based". CLTL1 had hashtables but no CLOS, for example.
Ken
+5  A: 

For a quick solution, just use hash tables, as has been mentioned before.

However, if you prefer a more principled approach, you can take a look at FSet, which is “a functional set-theoretic collections library”. Among others, it contains classes and operations for sets and bags.

(EDIT:) The cleanest way would probably be to define your set-oriented operations as generic functions. A set of generic functions is basically equivalent to a Java interface, after all. You can simply implement methods on the standard HASH-TABLE class as a first prototype and allow other implementations as well.

Matthias Benkard
+2  A: 

You could use lists, though they can prove to be inefficient for representing large sets. This is done using ADJOIN or PUSHNEW to add a new element to a list, and DELETE or REMOVE to do the opposite.

(let ((set (list)))
  (pushnew 11 set)
  (pushnew 42 set)
  (pushnew 11 set) 
  (print set) ; set={42,11}
  (setq set (delete 42 set))
  (print set)) ; set={11}

One thing to watch out for is all that these operators use EQL by default to test for potential duplicates in the set (much as Java uses the equals method). That's OK for sets holding numbers or characters, but for sets of other objects, a `deeper' equality test such as EQUAL should be specified as a :TEST keyword parameter, e.g. for a set of strings :-

(let ((set (list)))
  (pushnew "foo" set :test #'equal)
  (pushnew "bar" set :test #'equal)
  (pushnew "foo" set :test #'equal) ; EQUAL decides that "foo"="foo"
  (print set)) ; set={"bar","foo"}

Lisp's counterparts to some of Java's Set operations are:

Tamelite
This is a recommended approach to start with then optimise later should profiling suggest it is needed.
wentbackward
+3  A: 

Look at cl-containers. There is a set-container class.

Jacek Szymański
+3  A: 

Yes, it has sets. See this section on "Sets" from Practical Common Lisp.

Basically, you can create a set with pushnew and adjoin, query it with member, member-if and member-if-not, and combine it with other sets with functions like intersection, union, set-difference, set-exclusive-or and subsetp.

Matt Curtis
except that it doesn't scale above a few dozen of elements...
Attila Lendvai
+1  A: 

Easily solvable using a hash table.

(let ((h (make-hash-table :test 'equalp))) ; if you're storing symbols
  (loop for i from 0 upto 20
        do (setf (gethash i h) (format nil "Value ~A" i)))
  (loop for i from 10 upto 30
        do (setf (gethash i h) (format nil "~A eulaV" i)))
  (loop for k being the hash-keys of h using (hash-value v)
        do (format t "~A => ~A~%" k v)))

outputs

0 => Value 0
1 => Value 1
...
9 => Value 9
10 => 10 eulaV
11 => 11 eulaV
...
29 => 29 eulaV
30 => 30 eulaV
Mikael Jansson
A: 

Personally, I would just implement a function which takes a list and return a unique set. I've drafted something together which works for me:

(defun make-set (list-in &optional (list-out '()))
  (if (endp list-in)
      (nreverse list-out)
      (make-set
        (cdr list-in)
        (adjoin (car list-in) list-out :test 'equal))))

Basically, the adjoin function prepends an item to a list non-destructively if and only if the item is not already present in the list, accepting an optional test function (one of the Common Lisp "equal" functions). You can also use pushnew to do so destructively, but I find the tail-recursive implementation to be far more elegant. So, Lisp does export several basic functions that allow you to use a list as a set; no built-in datatype is needed because you can just use different functions for prepending things to a list.

My data source for all of this (not the function, but the info) has been a combination of the Common Lisp HyperSpec and Common Lisp the Language (2nd Edition).

zvoase