Add a character to a frequency list

问题:

I have a project about huffman coding, and I am stuck, I don't understand why my code is not working.

This is the exercise:

Write a function add1 which, given a character, adds 1 to its frequency in a frequency list. If the character is not yet in the list of frequencies, it is added.

(add1 "e" '(("l" 1) ("e" 2) ("x" 1)))       →          (("l" 1) ("e" 3) ("x" 1)) 
(add1 "e" '(("a" 4) ("b" 3)))               →          (("a" 4) ("b" 3) ("e" 1)) 

What I wrote:

(define add1
  (lambda (c l) 
    (if (null? l)
        '()
        (if (member? c l)
            (if (equal? c (caar l))
                (+ 1 (cadar l))
                (add1 c (cdr l)))
            (append l '((c 1)))))
        ))

The result:

(list (list "l" 1) (list "e" 2) (list "x" 1) (list 'c 1))

回答1:

It's a bad idea to call add1 the procedure, that clashes with a built-in procedure of the same name. Try this instead:

(define add-one
  (lambda (c l)
    (cond ((null? l)
           (list (list c 1)))
          ((equal? (caar l) c)
           (cons (list c (+ 1 (cadar l))) (cdr l)))
          (else
           (cons (car l) (add-one c (cdr l)))))))

See how, if we reach an empty list, it's because the character wasn't found in the list, so we must add it at the end. The other two cases are self-explanatory: either the character is the current one, or the character is in the rest of the list. By writing the solution in this way, it's not necessary to use member?. It works as expected:

(add-one "e" '(("l" 1) ("e" 2) ("x" 1)))
=> (("l" 1) ("e" 3) ("x" 1)) 

(add-one "e" '(("a" 4) ("b" 3)))
=> (("a" 4) ("b" 3) ("e" 1))