SICP - exercise 2.69 - generate a huffman tree from a set of ordered leaves

Question

From SICP

Exercise 2.69: The following procedure takes as its argument a list of symbol-frequency pairs (where no symbol appears in more than one pair) and generates a Huffman encoding tree according to the Huffman algorithm.

(define (generate-huffman-tree pairs)
  (successive-merge 
   (make-leaf-set pairs)))

Make-leaf-set is the procedure given above that transforms the list of pairs into an ordered set of leaves. Successive-merge is the procedure you must write, using make-code-tree to successively merge the smallest-weight elements of the set until there is only one element left, which is the desired Huffman tree. (This procedure is slightly tricky, but not really complicated. If you find yourself designing a complex procedure, then you are almost certainly doing something wrong. You can take significant advantage of the fact that we are using an ordered set representation.)

• make-code-tree creates a tree from two branches, make those branches as left and right branches respectively, combine all symbols of the branches as its own set of symbols, and finally add the weights of the branches as its own weight.
• adjoin-set inserts a tree to the set while remaining ordered based on the weight of the items.

Though I am confident my code is correct, I am extremely unsure of my solution. What's bothering me is the hint that it's tricky. It does gave correct results for all tests I did. I have thought of alternative ways of doing this, but the procedures I came up with were very complex. Also, I think this is very slow. Please review my code.

(define (successive-merge leaves)
(if     (= (length leaves) 1)
        (car leaves)
    (successive-merge (adjoin-set (make-code-tree (car leaves) (cadr leaves)) (cddr leaves)))))

How can I make this code better and faster? And are there better ways of doing this?

Answer 1

Instead of using (= (length leaves) 1) to measure the list, consider just using (null? (cdr leaves)) instead, that way it's a constant operation.

Otherwise, if you're not using destructive operations (to improve adjoin-set), this looks as good as it can get.

Also make sure to have the correct indentation (if that wasn't caused by pasting), e.g.:

(define (successive-merge leaves)
  (if (null? (cdr leaves))
      (car leaves)
      (successive-merge
       (adjoin-set
        (make-code-tree (car leaves)
                        (cadr leaves))
        (cddr leaves)))))

Also take a look at this post maybe, one of the posts regarding the same exercise.