Racket count occurrences using `map`

user_9015835 0
Viewed 1671

Write a Racket function count-occurrences that consumes two lists of symbols and produces a list of natural numbers measuring how many times items in the first list occur in the second list. For example:

(count-occurrences (list 'a 'b 'a 'q) (list 'r 'a 'b 'e 'b 'g))

=> (list 1 2 1 0)

I've been struggling with this question - how do I use map to do it, since for this question it's specified we can't use recursion.

My original idea was to do the following:

(define (count-occurrences los1 los2) 
  (map
   (length (filter (lambda (x) (symbol=? x (first los1))) los2))
   los1))

but using length here can only get us the number 'a occurred, instead of going into recursion. and for abstract functions there can only be one argument for the inside function, so I'm totally lost.

racket map-function scheme
3 Answers

A good way to keep track of keys and values is with a hash-table. While it is possible to write count-occurrences using map and passing a lambda, being explicit may make it easier to see what is going on.

;;; list list -> list
;;; 
(define (count-occurrences keys values)

  ;; Create data structure
  (define ht (make-hash))

  ;; Initialize data structure with keys
  ;; Set the value of each key to zero
  ;; Since we have not started counting
  (for ([k keys])
    (hash-set! ht k 0))

  ;; Iterate over values and
  ;; Increment hash table if
  ;; When value is a key
  (for ([v values])
    (if (hash-has-key? ht v)
      (hash-set! ht v (+ (hash-ref ht v) 1))
      null))

  ;; Iterate over keys and
  ;; Create list of values 
  (for/list ([k keys])
    (hash-ref ht k)))

Since recursion is prohibited, explicitly looping may make for more maintainable/readable code than an implicit loop. Besides, the variations of for are worth knowing. Hash tables have the advantage that duplicate keys read the same value and there is no need to track the same key twice.

One of the engineering advantages of using for rather than map is that it is easier to reason about the running time. The running time for this code is 2m + n where m is keys and n is values. Solutions using map will typically be m * n. There's nothing inherently wrong with that. But it is worth recognizing.

user_21019090
Related