CODEWITHSUNDEEP
lispcommon-lispuniqueduplicates
zcohen
zcohen

Reputation: 317

LISP - count occurences of every value in a list

I apologize for the bad English..
I have a task to write a function called "make-bag" that counts occurences of every value in a list
and returns a list of dotted pairs like this: '((value1 . num-occurences1) (value2 . num-occurences2) ...) For example: 

 (make-bag '(d c a b b c a))
((d . 1) (c . 2) (a . 2) (b . 2))

(the list doesn't have to be sorted)

Our lecturer allows us to us functions MAPCAR and also FILTER (suppose it is implemented), but we are not allowed to use REMOVE-DUPLICATES and COUNT-IF. He also demands that we will use recursion.

Is there a way to count every value only once without removing duplicates? And if there is a way, can it be done by recursion?

Upvotes: 0

Views: 2548

Answers (2)

Svarog
Svarog

Reputation: 285

First of, I agree with Mr. Joswig - Stackoverflow isn't a place to ask for answers to homework. But, I will answer your question in a way that you may not be able to use it directly without some extra digging and being able to understand how hash-tables and lexical closures work. Which in it's turn will be a good exercise for your advancement.

Is there a way to count every value only once without removing duplicates? And if there is a way, can it be done by recursion?

Yes, it's straight forward with hash-tables, here are two examples:

;; no state stored
(defun make-bag (lst)
  (let ((hs (make-hash-table)))
    (labels ((%make-bag (lst)
               (if lst
                   (multiple-value-bind (val exists)
                       (gethash (car lst) hs)
                     (if exists
                         (setf (gethash (car lst) hs) (1+ val))
                         (setf (gethash (car lst) hs) 1))
                     (%make-bag (cdr lst)))
                   hs)))
      (%make-bag lst))))

Now, if you try evaluate this form twice, you will get the same answer each time:

(gethash 'a (make-bag '(a a a a b b b c c b a 1 2 2 1 3 3 4 5 55)))
> 5
> T

(gethash 'a (make-bag '(a a a a b b b c c b a 1 2 2 1 3 3 4 5 55)))
> 5
> T

And this is a second example:

;; state is stored....
(let ((hs (make-hash-table)))
  (defun make-bag (lst)
    (if lst
        (multiple-value-bind (val exists)
            (gethash (car lst) hs)
          (if exists
              (setf (gethash (car lst) hs) (1+ val))
              (setf (gethash (car lst) hs) 1))
          (make-bag (cdr lst)))
        hs)))

Now, if you try to evaluate this form twice, you will get answer doubled the second time:

(gethash 'x (make-bag '(x x x y y x z z z z x)))
> 5
> T

(gethash 'x (make-bag '(x x x y y x z z z z x)))
> 10
> T

Why did the answer doubled?

How to convert contents of a hash table to an assoc list?

Also note that recursive functions usually "eat" lists, and sometimes have an accumulator that accumulates the results of each step, which is returned at the end. Without hash-tables and ability of using remove-duplicates/count-if, logic gets a bit convoluted since you are forced to use basic functions.

Upvotes: 2

user797257
user797257

Reputation:

Well, here's the answer, but to make it a little bit more useful as a learning exercise, I'm going to leave some blanks, you'll have to fill.

Also note that using a hash table for this task would be more advantageous because the access time to an element stored in a hash table is fixed (and usually very small), while the access time to an element stored in a list has linear complexity, so would grow with longer lists.

(defun make-bag (list)
  (let (result)
    (labels ((%make-bag (list)
               (when list
                 (let ((key (assoc (car <??>) <??>)))
                   (if key (incf (cdr key))
                       (setq <??>
                             (cons (cons (car <??>) 1) <??>)))
                   (%make-bag (cdr <??>))))))
      (%make-bag list))
    result))

There may be variations of this function, but they would be roughly based on the same principle.

Upvotes: 1

Related Questions