WillNess · March 16, 2018 16:47 · Mar 16, 2018 · Mar 16, 2018 · Mar 7, 2018
diff --git a/my full Huffman leaves SO answer.md b/my full Huffman leaves SO answer.md
@@ -9,6 +9,8 @@ What can a function *do*? A list can be altered in-place with `set-car!`,  and g
 
 Your code is written in imperative style, and even that with the order of operations jumbled up. You meant
 
+<!-- language-all: scheme -->
+
     (define (huffman-leaves tree)
       (let ((listenr1 '()))
         (define (iterator currentbranch)

diff --git a/my full Huffman leaves SO answer.md b/my full Huffman leaves SO answer.md
@@ -32,7 +32,22 @@ This is of course extremely inefficient as it introduces quadratic behavior, eac
 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](https://stackoverflow.com/a/13256555/849891) or [here](https://stackoverflow.com/a/14965347/849891)).
 
 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](https://stackoverflow.com/users/1565698/sylwester) notes [in the comments](https://stackoverflow.com/questions/49136510/problems-with-scheme-iteration-not-appending-to-list/49137936#comment85281897_49137936),
-the need to reverse vanishes if we also swap the processing of the branches, going right before going left.
+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.
 

diff --git a/my full Huffman leaves SO answer.md b/my full Huffman leaves SO answer.md
@@ -0,0 +1,84 @@
+
+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 &ndash; 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 &frasl; 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](https://stackoverflow.com/a/13256555/849891) or [here](https://stackoverflow.com/a/14965347/849891)).
+
+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](https://stackoverflow.com/users/1565698/sylwester) notes [in the comments](https://stackoverflow.com/questions/49136510/problems-with-scheme-iteration-not-appending-to-list/49137936#comment85281897_49137936),
+the need to reverse vanishes if we also swap the processing of the branches, going right before going left.
+
+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`.
+