How to Implement a counter for every number inside a list with Scheme ?

Question

Okay I want to count the number of times each [number] has appeared inside a list using Scheme.

How can I do that ? I also would like to store the counter of the given number and re-construct a new list.

For example I have the following list ((1 2)(2 5)(5 7)(7 8)(6 8)(4 6)(3 4)(1 3)(4 8))

I was thinking first flatten the list, and then set a counter for each number (don't know how to do it). And then reconstruct a new list corresponding to the original number. (this can be tricky ? I need to store a temporary variable ?)

Say from this example the number 1 appeared twice, number 2 appeared twice, number 3 twice etc... so I would like to recreate a new list to something like this:

(1 2) (2 2) (3 2) (4 3) (5 2) (7 2) (6 2) (8 3)

any idea how I can achieve this ?

Update:

I was thinking to implement an increment counter helper something like this ?

 (define inc-counter 
    (let ((counter 0)) 
      (lambda () (set! counter (+ counter 1)))))

Answer 1

Use an accumulator parameter to flatten which keeps an association list of how many times each has appeared. That way you'll have all the data you need each time around the loop.

For example, you might write factorial like this:

(define (factorial num accum)
  (if (= num 0) accum (factorial (- num 1) (* accum num)))

And call it with (factorial 10 1). At the end, the value of the accumulator is the result of the function. In your example, you'd write a little helper function that would call flatten and keep track of the number of times each number has appeared.

Answer 2

Perhaps not the most efficient solution, but I think you could achieve this by partitioning the list by its first element until there are no more elements in the list. The list of in-elements would then be all of the numbers in the list that were the same as the first number. This process could be repeated on the list of out-elements until there were no more elements in the list.

Answer 3

You could use a hashtable mapping the number to its number of occurrences. Create it with (make-hash).

Answer 4

A good answer mostly depends on your implementation (modulo R6RS). In the case of PLT scheme, here's a quick definition that does that. It avoids flattening the list -- you only need to scan each item, so there's no point in constructing a new copy when scanning a tree is so simple. Also, this function sorts the resulting list (since it will be all scrambled on its way out of the hash table). Even if you're using some completely different implementation, it should be easy to translate:

(define (counts x)
  (define t (make-hash))
  (define (scan x)
    (if (list? x)
      (for-each scan x)
      (hash-set! t x (add1 (hash-ref t x 0)))))
  (scan x)
  (sort (hash-map t list) < #:key car))

(Note, BTW, that if this is any kind of HW question, then this code is much too practical to be useful as an answer...)