Page 1 of 1

count occurences in a list

Posted: Thu Aug 30, 2012 3:51 am
by zcohen
Hi everybody,
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:

Code: Select all

> (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?

Thanks guys

Re: count occurences in a list

Posted: Thu Aug 30, 2012 11:18 am
by saulgoode
Start with an empty dictionary (an alist), and then traverse your input (using recursion); if you encounter an item that is not in your dictionary, add it with a count of "1". If the item you encounter is already in the dictionary, increment its count.

When you reach the end of your input, your dictionary will be the result you want.