[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: LAST CALL for SRFI-113, Sets and bags

This page is part of the web mail archives of SRFI 113 from before July 7th, 2015. The new archives for SRFI 113 contain all messages, not just those from before July 7th, 2015.



Unfortunately, the implementation is buggy and makes the last appearance
win.  That's easy to fix for alist->bag, but tricky for alist->bag!,
where we want the first appearance *in the alist* to win, beating both
later appearances and any existing entry.  Suggestions?

How about something like this (untested pseudocode) for alist->bag!:

(define (alist->bag! bag alist)
  (bag-delete-all! bag (map car alist))
  (for-each (lambda (pair)
                  (unless (bag-contains? bag (car pair))
                    (bag-increment! bag (car pair) (cdr pair))))
                alist))

If the other bag operations are efficient then this algorithm should be optimal asymptotically, if not up to constant factors.

Kevin Wortman