get pairs out of a huffman tree

Question

I'm trying to write a procedure Huffman-leaves; the procedure returns a list of pairs from a created huffman tree. Example on how it runs

  (huffman-leaves sample-tree) 
   ->((A . 8) (C . 5) (B . 1) (D . 1))

What I've comed up with but got writers block...

(define (huffman-leaves tree)
  (define (huffman-get-pairs current-branch pairs)
     (if (or (null? tree) (null? current-branch))
         pairs
         (let ((next-branch
                (get-branch (car current-branch) current-branch)))
           (not (member? next-branch pairs)
                (if (leaf? next-branch)
                    (cons (append  pairs next-branch)
                          (display pairs)
                          (huffman-get-pairs (cadr current-branch) pairs))
                    (huffman-get-pairs next-branch pairs))))))
  (huffman-get-pairs tree '()))

  (member? item 'list) #if item in list return #t else #false

I know that I'm doing something wrong but I can't see it. How can I stop a search in a huffman-tree in scheme? Any tip that I should be doing different?

Answer 1

I recommend:

1. Write a data definition for Huffman Tree

2. Make example input huffman trees, encoded according to your data definition from step 1, and expected outputs (lists of leaves, in this case).

3. Follow the design recipe to build a basic template for the huffman-leaves function.

4. Fill in the ... in your template according to the examples you built from step 2.

5. Translate your examples from step 2. into tests, and test your code from step 4.

Sorry if the above seems vague, but it is the best advice I can give with the level of detail (or lack thereof) you have supplied in this question thus far. If you can provide answers for the steps above, and say explicitly which step you are blocked on, then we can help you get over your writers block in a more systematic way.

---

If you prefer real code, here is one direction you could go in to make a very generic solution for your problem:

;; make-visitor : (X -> Y) (X -> [Listof X]) (Y [Listof Z] -> Z) -> Z
;; Very generic descend+map+recombine routine
;; (note X, Y, Z are implicitly universally quantified above).
(define (make-visitor transform children combine)
  (lambda (x)
    (let rec ((x x)) ;; rec : X -> Z
      (combine (transform x)
               (map rec (children x))))))

;; ... the hard bit is coming up with the appropriate lambda
;; expressions for `transform`, `children`, and `combine` above.

(define leaves
  (make-visitor (lambda (x) ...)
                (lambda (x) ...)
                (lambda (y zs) ...)))

I don't actually recommend trying to jump directly to a solution of this form; you will be better off if you try to follow the design recipe and make a direct solution to your problem. But once you have done that, it can be an educational exercise to see if you can retrofit your own solution onto the generic routine above.