Scheme collecting similar items in a list and find

问题:

This question already has an answer here:

• Count occurrence of element in a list in Scheme? 4 answers

I want to make a function that occurs how many times an element occurs in a list. For example in the list: '(a b c b b c c a) I want it to return a nested list with: '((a 2) (b 3) (c 3))

I know the function will look sort of like this:

(define collect-similar
 (lambda (elm ls)
  (cond
   [(null? ls) '()]
   [(equal? elm (car ls))]

I know that I need to continue checking through the list until it arrives back at the base case of the null list and I can check the rest of the list by using cadr. But I'm not too sure on how to get the value and how to make it return the nested list.

The next function I'm trying to write finds the most common element in the list. For example running the function on the list '(a a a a a b c) will simply return a. I know I can make use of the collect-similar function and find which number is the highest.

回答1:

This has been asked before, just adapt one of @ChrisJester-Young's bagify implementations. For example:

(define (collect-similar lst) ; a slightly modified `bagify`
  (hash->list
   (foldl (lambda (key ht)               
            (hash-update ht key add1 0))
          '#hash()
          lst)))

(collect-similar '(a b c b b c c a))
=> '((a . 2) (b . 3) (c . 3))

With collect-similar in place, it's simple to find the most common element:

(define (most-common lst)
  (let loop ((alst (collect-similar lst)) ; use previous procedure
             (maxv '(#f . -inf.0)))
    (cond ((null? alst) (car maxv))
          ((> (cdar alst) (cdr maxv))
           (loop (cdr alst) (car alst)))
          (else
           (loop (cdr alst) maxv)))))

(most-common '(a a a a a b c))
=> 'a