Using closures to lazily yield a tree's leaves in Scheme

Question

The tree is a linear list or non-linear list, such as:

'(1 2 3 4)
'((1 2) 3 4)
'((1 (2)) 3 (4))

All the trees above will yield leaves in order: 1 -> 2 -> 3 ->4. I know how to deal with a linear tree:

(define (treeg tree)
  (lambda ()
    (if (null? tree)
      '()
      (let ((e (car tree)))
        (set! tree (cdr tree))
        e))))

So, you can use like this:

(define gtr (treeg '(1 2 3 4)))
;now you can get a leaf per `gtr` call.

But when facing non-linear tree, the following code failed:

(define (treeg tree)
  (lambda ()
    (if (null? tree)
      '()
      (let ((e (car tree)))
        (set! tree (cdr tree))
        (if (pair? e)
          ((treeg e)) ;here just yield first leaf.
          e)))))

I know there is a call/cc solution, but is there a solution using closures?

You may find my answer to [call-with-current-continuation - state saving concept](http://stackoverflow.com/q/24183566/1281433) helpful. It begins with a non-call/cc version and builds a lazy iterator over a list. — Joshua Taylor, Aug 23 '14 at 05:40
[How to implement Python-style generator in Scheme (Racket or ChezScheme)?](http://stackoverflow.com/q/25269308/1281433) might be of interest, too. — Joshua Taylor, Aug 23 '14 at 05:41
@Joshua Taylor Thanks. but your example is about a linar list, I still find it difficult to apply to non-linar list. And the question in the second comment is Mine, I know it too. — xiang, Aug 23 '14 at 06:13
Oh, I didn't notice that it was your question. I still think the link is useful, since other readers of the question may find it helpful. Stack Overflow is about helping *everyone*, after all, not just the original asker. — Joshua Taylor, Aug 23 '14 at 13:06
The modification to adapt the CPS style list traversal to a CPS tree traversal isn't hard. I've added an answer. Regarding "but your example is about a linar list": yes, I recognized that, and that's why I said that you may find it useful, but not that it's a duplicate. — Joshua Taylor, Aug 23 '14 at 13:22

uselpa · Accepted Answer · 2014-08-23T15:42:34.653

Yes it is possible. When your first element is a pair, just push back both its car and its cdr to the front of the tree and recur, ignoring empty sublists on your way:

(define (treeg tree)
  (define (next)
    (if (null? tree)
        '()
        (if (pair? tree)
            (let ((e (car tree)))
              (cond
                ((null? e) (set! tree (cdr tree))
                           (next))
                ((pair? e) (set! tree (list* (car e) (cdr e) (cdr tree)))
                           (next))
                (else      (set! tree (cdr tree))
                           e)))
            (begin0
              tree
              (set! tree null)))))
  next)

Testing:

(for/list ((i (in-producer (treeg '(1 2 3 4)) '()))) i)
=> '(1 2 3 4)
(for/list ((i (in-producer (treeg '((1 (2)) 3 (4))) '()))) i)
=> '(1 2 3 4)

To illustrate the process, here's how tree evolves in the second example:

called with ((1 (2)) 3 (4))
called with (1 ((2)) 3 (4))
yield 1
called with (((2)) 3 (4))
called with ((2) () 3 (4))
called with (2 () () 3 (4))
yield 2
called with (() () 3 (4))
called with (() 3 (4))
called with (3 (4))
yield 3
called with ((4))
called with (4 ())
yield 4
called with (())
called with ()

EDIT re: the discussions in the comments section, here's the generator version, for comparison, which is way more elegant (to me, at least):

(define (treeg tree)
  (generator ()
    (define (rec tree)
      (unless (null? tree)
        (if (pair? tree)
            (let ((e (car tree)))
              (cond
                ((pair? e) (rec (car e))
                           (rec (cdr e)))
                (else      (yield e)))
              (rec (cdr tree)))
            (yield tree))))
    (rec tree)
    (yield null)))

I see [this answer](http://stackoverflow.com/a/3802417/3909433). The author emphasized "I wouldn't use yield at all in Lisp/Scheme" and led me to this question. Currently seems he is right. — xiang, Aug 23 '14 at 08:28
@xiang You can do everything in any turing-complete language, even in assembler. So generators are not a necessary construct, and can always be emulated with other language constructs. So why are they so often used in Python? Because 1) they allow for elegant code 2) they are cheap (i.e. their implementation is fast in Python). Why are they not used more often in Scheme? Because a universal implementation has to use continuations, and those seem to be difficult to implement efficiently. In Common Lisp, you'd even have to implement continuations first. — uselpa, Aug 23 '14 at 09:02
@xiang It's a little bit like saying "I would never use `append` in Lisp". In Python, `append` is O(1) so you use it all the time. In Lisp, you `cons`, and `reverse` if necessary. Is `append` bad? No way, it's actually the better solution in many cases. Still you want to avoid it in Lisp for performance reasons. So it boils down to "what is a common idiom in language x", and those idioms are chosen for many reasons, notably performance. — uselpa, Aug 23 '14 at 10:05
I quite like using generator. it's elegant and convenient to express ideas. Actually I am trying to write a simple python style generator(it just yields value, can't send value to it) using r6rs. — xiang, Aug 23 '14 at 10:32

score 0 · Answer 2 · edited May 23 '17 at 11:57

Here's a modification of the first part of my answer to call-with-current-continuation - state saving concept. It shows how to define a continuation passing tree-mapping procedure, and then to define an iterator creating procedure around it.

(define (kmaptree fn tree k)
  (if (pair? tree)                           ; If the tree is a pair (a . b)
      (kmaptree fn                           ; then first map over the subtree
                (car tree)                   ; a, but with a continuation that 
                (lambda (left)               ; will recieve the result, and then
                  (kmaptree fn               ; map over the subtree b.  When
                            (cdr tree)       ; the result of that is received
                            (lambda (right)  ; call the original k with the pair
                              (k (cons left right)))))) ; of the results.
      (fn tree k)))                          ; Else, just call fn with the leaf.

(define (identity x) x)                      ; Just an identity function, `values`
                                             ; would work fine, too.
(define (iterator tree)
  ;; Returns an iterator over the tree.
  (define (next k)
    ;; Next is helper function that, at first, maps a function 
    ;; over the tree.  That function, though, keeps updating
    ;; next to be a function that continues the mapping, and 
    ;; calls k with each leaf it encounters.
    (kmaptree (lambda (leaf more-next)
                (set! next more-next)  ; update next
                (k leaf))              ; call k with the leaf
              tree
              (lambda (results)
                (k 'done))))
  ;; The iterator is just a function that calls next.
  (lambda ()
    (next identity)))                  ; or (next values)

(define get (iterator '((1 . 2) (3 . 4) 5 . 6)))

> (get)
1
> (get)
2
> (get)
3
> (get)
4
> (get)
5
> (get)
6
> (get)
done
> (get)
done

Wow, CPS is really wrap my head around. I feel it's even harder than call/cc. I shall have a good sleep and drink a cup of milk and continue to try to understand its mechanism tomorrow. — xiang, Aug 23 '14 at 13:54
Continuation passing style isn't really a *different* thing from what call/cc gives you. After all, call/cc is short for call-with-current-*continuation*. The difference is that doing it explicitly makes things a bit clearer (in my opinion, anyway). I started to find call/cc more understandable once I spent a bit of time working with CPS. — Joshua Taylor, Aug 23 '14 at 14:58
@uselpa Good point about `values`! I think that `values` might be a little bit esoteric for less experiences users, so I'm going to leave it with `identity` for the moment, to keep things a little more transparent. I'll add a comment to the code, though. — Joshua Taylor, Aug 23 '14 at 15:01
@uselpa Touché! This answer, as written now, doesn't make use of any particularly uncommon functionality (just pair?, cons, car, cdr, lambda, define, set!, and a nested definition), all of which Scheme programmers will encounter relatively early. This answer highlights CPS, which is somewhat esoteric (most programmers probably don't use continuations all that much, except in UI programming), but doesn't require any particular unusual features to implement. `values`, while not esoteric, is probably something that fewer Scheme programmers will have used than the rest of what's here. — Joshua Taylor, Aug 23 '14 at 15:55

Using closures to lazily yield a tree's leaves in Scheme

2 Answers2