[Tutor] Experiments with generators, part deux [flattened lists, Scheme, and Python]

Danny Yoo dyoo@hkn.eecs.berkeley.edu
Mon, 4 Feb 2002 21:36:49 -0800 (PST)


[Warning: the following is experimental code that only works with Python
2.2.  This code below is meant to be completely Useless.  However, it's
also not guaranteed to be quickly understandable.  Skip this message if
you don't know about Scheme.]










Hi Everyone,

I've been having some fun recently trying to bend my head around the
concept of continuations in Scheme, using the Scheme book "Teach Yourself
Scheme in Fixnum Days":

http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme-Z-H-15.html#%25_sec_13.3

One of the examples that the author uses to present continuations is the
following problem: given two deeply nested lists, can we write an
efficient method to easily see if they have the same elements --- that is,
how can we tell if the two lists have the same "fringe"?  For example,
we'd say that "[1, [2, [3]]]" and "[[[1]], [[2], 3]]" would have the same
fringe, but "[1, [2, [3]]]" and "[[[1]], [[], 3]]" would not.

One simple way to do this fringe-check is to flatten both lists, and then
just do a single list comparison:

###
>>> def flatten(L):
...     if type(L) != types.ListType: return [L]
...     if len(L) == 0: return []
...     return flatten(L[0]) + flatten(L[1:])
... 
>>> flatten([1, [2, [3]]])
[1, 2, 3]
>>> flatten([1, [2, [3]]]) == flatten([[[1]], [[2], 3]])
1
>>> flatten([1, [2, [3]]]) == flatten([[[1]], [[], 3]])
0
###

However, one disadvantage of this is that we end up making duplicate
copies of our lists in memory.  For huge lists, flatten()ing can be
prohibitively expensive.  What can we do?


One solution that avoids the explicit list flattening is to write a
"generator" that automagically presents a flattened view of a list.  For
those who like sticking their hands in door jams, here's the code in
Scheme:

;;;
(define tree->generator
  (lambda (tree)
    (let ((caller '*))
      (letrec
	  ((generate-leaves
	    (lambda ()
              (let loop ((tree tree))
                (cond ((null? tree) 'skip)
                      ((pair? tree)
                       (loop (car tree))
                       (loop (cdr tree)))
                      (else
		       (call/cc
			(lambda (rest-of-tree)
                          (set! generate-leaves
				(lambda ()
				  (rest-of-tree 'resume)))
                          (caller tree))))))
              (caller '()))))
        (lambda ()
          (call/cc
	   (lambda (k)
             (set! caller k)
             (generate-leaves))))))))
;;;


There's a lot of tricky lexical scoping issues involved here, and I
thought this just looked both paradoxically beautiful yet hideous.  (I did
rewrite tree->generator to tease out some of the complexity into separate
functions, with some success.  If anyone's interested, email me.)



In any case, let's see how this works:

###
> (define g (tree->generator '((1) 2 (3 (4 ((5)))))))
> (g)
1
> (g)
2
> (g)
3
> (g)
4
> (g)
5
> (g)
()
###

So even if the code is complicated, it's still pretty useful!  It allows
us to look at any nested list as if it were flattened, so that we can
write a fringe function almost casually.



For fun, I wrote an equivalent generator in Python:

###
from __future__ import generators

def tree_generator(tree):
    if tree == []:
        raise StopIteration
    if isinstance(tree, list):
        for branch in tree:
            for element in tree_generator(branch):
                yield element
    else:
        yield(tree)
###

I don't think this is so bad, but I admit it's still a little tricky.  
But it works!  Here's the generator in action:

###
>>> g = tree_generator([[1], 2, [3, [4, [[5]]]]])
>>> g.next()
1
>>> g.next()
2
>>> g.next()
3
>>> g.next()
4
>>> g.next()
5
>>> g.next()
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
StopIteration
###


Generators are a lot of fun to play with, and they do appear to allow us
to do things that would be difficult to do otherwise.  At the same time,
I'm also somewhat relieved that we don't have continuations in Python, as
these things are just evil!  *grin*


Anyway, I hope this was interesting!