Racket count occurrences using `map`

Question

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.

Answer 1

If ... x ... is an open formula, i.e. an expression which references an unbound variable x, wrapping it in a lambda form makes it a function in x, like so:

(lambda (x) ... x ... )

where x becomes bound by that lambda form; a parameter to this so called lambda function, which is to say, an anonymous function introduced by a lambda form.

So, the solution for your troubles is quite simple: recognize that

    (length
        (filter (lambda (x)               
                     (symbol=? x (first los1)))
                los2))

should actually be

    (length
        (filter (lambda (x)               
                     (symbol=? x y))
                los2))

where y refers to each of the elements of los1 in turn, not just the first one; and that it is then an open formula in y – that is to say, y is unbound, free, there. So we must capture it, and make it bound, by ... yes, enclosing this expression in a lambda form, thereby making it a function in y! Like so:

  (lambda (y)
    (length
        (filter (lambda (x)               
                     (symbol=? x y))
                los2)))

And this is what gets mapped over los1.

With this simple tweak, your code becomes a correct, working function definition.

Answer 2

Does this fit your requirements and restrictions?

(define (count-occurrences lst1 lst2)
  (map (lambda (e1)
         (count (lambda (e2) (eq? e1 e2))
                lst2))
       lst1))

Answer 3

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.