count occurences in a list

You have problems, and we're glad to hear them. Explain the problem, what you have tried, and where you got stuck.
Feel free to share a little info on yourself and the course.
Forum rules
Please respect your teacher's guidelines. Homework is a learning tool. If we just post answers, we aren't actually helping. When you post questions, be sure to show what you have tried or what you don't understand.
Post Reply
zcohen
Posts: 6
Joined: Wed Jun 06, 2012 12:41 am

count occurences in a list

Post by zcohen » Thu Aug 30, 2012 3:51 am

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

saulgoode
Posts: 45
Joined: Tue Dec 14, 2010 1:39 am

Re: count occurences in a list

Post by saulgoode » Thu Aug 30, 2012 11:18 am

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.

Post Reply