SICP - exercise 2.69 - generate a huffman tree from a set of ordered leaves 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?
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.