Re: Multiset (or bag) library

ShaunJ skrev:
Is there a common multiset [1] (or bag) implementation? There is of
course many possibly representations of a multiset. I can use
whichever is most common. However, the most immediately useful
representation to me would be { 1, 2, 2, 3 } represented by '(1 1 2
3). In particular, I'm looking for a lmultiset<= procedure similar to
SRFI-1's lset<= procedure:

(lset<= = '(1 2 2 3) '(1 2 3))
#t

(lmultiset<= = '(1 2 2 3) '(1 2 3))
#f

The lists will always be sorted. If there's no standard
implementation, is there a scheme one-liner that works?

If you are using PLT Scheme, you can make use of Galore.


> (require (planet "bag.ss" ("soegaard" "galore.plt" 3 6))
(lib "67.ss" "srfi"))


> (define b1 (make-ordered number-compare 2 1 3 2))

> (define b2 (make-ordered number-compare 1 3 2 4 5 5))

> (elements b1)
(1 2 3)

> (to-alist b1)
((1 . 1) (2 . 2) (3 . 1))

> (to-alist b2)
((1 . 1) (2 . 1) (3 . 1) (4 . 1) (5 . 2))

> (elements (union b1 b2))
(1 2 3 4 5)

> (to-alist (difference b1 b2))
((2 . 1))

See the documentation:

http://planet.plt-scheme.org/package-source/soegaard/galore.plt/3/6/doc.txt

--
Jens Axel Søgaard
.

Relevant Pages