1

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))))) 

4 Answers 4

3

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...)

3
  • haha actually this question is some what related to the hw that I'm working on but its more complicated. I just want to use this in my step that's all.
    – Jonathan
    Nov 13, 2009 at 15:23
  • the problem is that there is no such function I can use with "For each" or even "every". those aren't pre-defined functions in the language I'm using to compile
    – Jonathan
    Nov 13, 2009 at 15:25
  • for-each, at least, should be part of every scheme implementation. Nov 13, 2009 at 15:43
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.

3
  • exactly how? new to scheme never heard of accumulator till now :(
    – Jonathan
    Nov 13, 2009 at 13:50
  • An accumalator is just an extra parameter that gathers results as you weave your way through the functions. For example, you might write a version of the 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 of the call chain, the value of the accumulator would be the result, so when n=0 we simply return that. Nov 13, 2009 at 14:21
  • Eli Barzilay's answer makes WAY more sense than mine, so I'd use that and completely ignore mine. Nov 13, 2009 at 14:36
0

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.

0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.