my full Huffman leaves SO answer.md

https://stackoverflow.com/questions/49136510/list-all-leaves-of-huffman-tree/49137936#49137936

On the "fundamentals" level, in Scheme we write functions to either construct and return a value, or for their side-effects – meaning, when they do something while we ignore their returned value.

What can a function do? A list can be altered in-place with set-car!, and grown ⁄ shrunk with set-cdr!, as an example. append does neither. It constructs new value, new list, from its arguments. But then we have to use this new value somehow, have to return it from our function. Just writing (append a b) does nothing, if it's not (in) the last expression in a function.

Your code is written in imperative style, and even that with the order of operations jumbled up. You meant

(define (huffman-leaves tree)
  (let ((listenr1 '()))
    (define (iterator currentbranch)
      (let ((left (left-branch currentbranch))
            (right (right-branch currentbranch)))
        (if (leaf? left)
            (append! listenr1 (list (symbols left) (weight left)))  ; here!
            (iterator left))        ; _not_ here
        (if (leaf? right)
            (append! listenr1 (list (symbols right) (weight right)))  ; here!
            (iterator right))))        ; _not_ here
    (iterator tree)   ; side-effect: grow the list incrementally
    listenr1))        ; now return the constructed list

using the non-existent (append! a b) which would alter the a list in-place to have b as its new last value, appended into it.

You could code it as a macro, or just write (set! a (append a (list b))) instead.

This is of course extremely inefficient as it introduces quadratic behavior, each appending operation having to retrace the growing list from its start each time anew.

One way to ameliorate this is to also maintain the last cons cell "pointer" while set-cdr!ing it, so that each such append! operation is O(1) (as can be seen e.g. here or here).

Arguably the easiest fix, though, is to just build the list in reverse order with (set! a (cons b a)), and return (reverse listenr1) in the end. And as Sylwester notes in the comments, the need to reverse vanishes if we also swap the processing of the branches, going right before going left, so,

(define (huffman-leaves tree)
  (let ((listenr1 '()))
    (define (iterator currentbranch)
      (let ((left (left-branch currentbranch))
            (right (right-branch currentbranch)))
        (if (leaf? right)
            (set! listenr1 (cons (list (symbols right) (weight right)) listenr1))  ; here!
            (iterator right))        ; _not_ here
        (if (leaf? left)
            (set! listenr1 (cons (list (symbols left) (weight left)) listenr1))  ; here!
            (iterator left))))        ; _not_ here
    (iterator tree)   ; side-effect: grow the list incrementally
    listenr1))        ; now return the list constructed right-to-left... no need to reverse it!

The use of set! is usually frowned upon but since here it is used to alter the well encapsulated entity, the fringe list listenr1, the whole thing is still functional on the outside.

---

To code it in the fully functional way, either nested recursion or [tag:continuation-passing] style can be used. The first is

(define (huffman-leaves-nested-rec tree)
    (define (iterator tree next)
      (if (leaf? tree)
          (cons (list (symbols tree) (weight tree))
                next)
          (let ((left (left-branch tree))
                (right (right-branch tree)))
            (iterator left
               (iterator right next)))))
    (iterator tree '()))

which though recursive is quite efficient, with the recursion's depth never exceeding the tree's depth, building the resulting list by a series of efficient cons calls bottom-up; and the second,

(define (huffman-leaves-cps tree)
    (define (iterator tree next)
      (if (leaf? tree)
          (next (lambda (z)
                  (cons (list (symbols tree) (weight tree))
                        z)))
          (let ((left (left-branch tree))
                (right (right-branch tree)))
            (iterator left (lambda (x)                  ; collect the result from left
               (iterator right (lambda (y)                ; and from right; then
                   (next (lambda (z) (x (y z)))))))))))     ; combine and use them
    (iterator tree (lambda (x) (x '()))))

which traverses the tree in order, gradually building up a function that, when finally applied to an empty list, will create the resulting list by a series of efficient cons calls bottom-up. It could've been coded simpler, as

(define (huffman-leaves-cps-appending tree)
    (define (iterator tree next)
      (if (leaf? tree)
          (next (list (list (symbols tree) (weight tree))))
          (let ((left (left-branch tree))
                (right (right-branch tree)))
            (iterator left (lambda (x)
               (iterator right (lambda (y)
                   (next (append x y)))))))))
    (iterator tree (lambda (x) x)))

but this would re-introduce the problematic append.