I'm home sick today, so tortured myself <0.9 wink>.
Sam mentioned using coroutines to compare the fringes of two trees, and I
picked a simpler problem: given a nested list structure, generate the leaf
elements one at a time, in left-to-right order. A solution to Sam's problem
can be built on that, by getting a generator for each tree and comparing the
leaves a pair at a time until there's a difference.
Attached are solutions in Icon, Python and Scheme. I have the least
experience with Scheme, but browsing around didn't find a better Scheme
approach than this.
The Python solution is the least satisfactory, using an explicit stack to
simulate recursion by hand; if you didn't know the routine's purpose in
advance, you'd have a hard time guessing it.
The Icon solution is very short and simple, and I'd guess obvious to an
average Icon programmer. It uses the subset of Icon ("generators") that
doesn't require any C-stack trickery. However, alone of the three, it
doesn't create a function that could be explicitly called from several
locations to produce "the next" result; Icon's generators are tied into
Icon's unique control structures to work their magic, and breaking that
connection requires moving to full-blown Icon coroutines. It doesn't need
to be that way, though.
The Scheme solution was the hardest to write, but is a largely mechanical
transformation of a recursive fringe-lister that constructs the entire
fringe in one shot. Continuations are used twice: to enable the recursive
routine to resume itself where it left off, and to get each leaf value back
to the caller. Getting that to work required rebinding non-local
identifiers in delicate ways. I doubt the intent would be clear to an
average Scheme programmer.
So what would this look like in Continuation Python? Note that each place
the Scheme says "lambda" or "letrec", it's creating a new lexical scope, and
up-level references are very common. Two functions are defined at top
level, but seven more at various levels of nesting; the latter can't be
pulled up to the top because they refer to vrbls local to the top-level
functions. Another (at least initially) discouraging thing to note is that
Scheme schemes for hiding the pain of raw call/cc often use Scheme's macro
facilities.
may-not-be-as-fun-as-it-sounds<wink>-ly y'rs - tim
Here's the Icon:
procedure main()
x := [[1, [[2, 3]]], [4], [], [[[5]], 6]]
every writes(fringe(x), " ")
write()
end
procedure fringe(node)
if type(node) == "list" then
suspend fringe(!node)
else
suspend node
end
Here's the Python:
from types import ListType
class Fringe:
def __init__(self, value):
self.stack = [(value, 0)]
def __getitem__(self, ignored):
while 1:
# find topmost pending list with something to do
while 1:
if not self.stack:
raise IndexError
v, i = self.stack[-1]
if i < len(v):
break
self.stack.pop()
this = v[i]
self.stack[-1] = (v, i+1)
if type(this) is ListType:
self.stack.append((this, 0))
else:
break
return this
testcase = [[1, [[2, 3]]], [4], [], [[[5]], 6]]
for x in Fringe(testcase):
print x,
print
Here's the Scheme:
(define list->generator
; Takes a list as argument.
; Returns a generator g such that each call to g returns
; the next element in the list's symmetric-order fringe.
(lambda (x)
(letrec {(produce-value #f) ; set to return-to continuation
(looper
(lambda (x)
(cond
((null? x) 'nada) ; ignore null
((list? x)
(looper (car x))
(looper (cdr x)))
(else
; want to produce this non-list fringe elt,
; and also resume here
(call/cc
(lambda (here)
(set! getnext
(lambda () (here 'keep-going)))
(produce-value x)))))))
(getnext
(lambda ()
(looper x)
; have to signal end of sequence somehow;
; assume false isn't a legitimate fringe elt
(produce-value #f)))}
; return niladic function that returns next value
(lambda ()
(call/cc
(lambda (k)
(set! produce-value k)
(getnext)))))))
(define display-fringe
(lambda (x)
(letrec ((g (list->generator x))
(thiselt #f)
(looper
(lambda ()
(set! thiselt (g))
(if thiselt
(begin
(display thiselt) (display " ")
(looper))))))
(looper))))
(define test-case '((1 ((2 3))) (4) () (((5)) 6)))
(display-fringe test-case)
Sam mentioned using coroutines to compare the fringes of two trees, and I
picked a simpler problem: given a nested list structure, generate the leaf
elements one at a time, in left-to-right order. A solution to Sam's problem
can be built on that, by getting a generator for each tree and comparing the
leaves a pair at a time until there's a difference.
Attached are solutions in Icon, Python and Scheme. I have the least
experience with Scheme, but browsing around didn't find a better Scheme
approach than this.
The Python solution is the least satisfactory, using an explicit stack to
simulate recursion by hand; if you didn't know the routine's purpose in
advance, you'd have a hard time guessing it.
The Icon solution is very short and simple, and I'd guess obvious to an
average Icon programmer. It uses the subset of Icon ("generators") that
doesn't require any C-stack trickery. However, alone of the three, it
doesn't create a function that could be explicitly called from several
locations to produce "the next" result; Icon's generators are tied into
Icon's unique control structures to work their magic, and breaking that
connection requires moving to full-blown Icon coroutines. It doesn't need
to be that way, though.
The Scheme solution was the hardest to write, but is a largely mechanical
transformation of a recursive fringe-lister that constructs the entire
fringe in one shot. Continuations are used twice: to enable the recursive
routine to resume itself where it left off, and to get each leaf value back
to the caller. Getting that to work required rebinding non-local
identifiers in delicate ways. I doubt the intent would be clear to an
average Scheme programmer.
So what would this look like in Continuation Python? Note that each place
the Scheme says "lambda" or "letrec", it's creating a new lexical scope, and
up-level references are very common. Two functions are defined at top
level, but seven more at various levels of nesting; the latter can't be
pulled up to the top because they refer to vrbls local to the top-level
functions. Another (at least initially) discouraging thing to note is that
Scheme schemes for hiding the pain of raw call/cc often use Scheme's macro
facilities.
may-not-be-as-fun-as-it-sounds<wink>-ly y'rs - tim
Here's the Icon:
procedure main()
x := [[1, [[2, 3]]], [4], [], [[[5]], 6]]
every writes(fringe(x), " ")
write()
end
procedure fringe(node)
if type(node) == "list" then
suspend fringe(!node)
else
suspend node
end
Here's the Python:
from types import ListType
class Fringe:
def __init__(self, value):
self.stack = [(value, 0)]
def __getitem__(self, ignored):
while 1:
# find topmost pending list with something to do
while 1:
if not self.stack:
raise IndexError
v, i = self.stack[-1]
if i < len(v):
break
self.stack.pop()
this = v[i]
self.stack[-1] = (v, i+1)
if type(this) is ListType:
self.stack.append((this, 0))
else:
break
return this
testcase = [[1, [[2, 3]]], [4], [], [[[5]], 6]]
for x in Fringe(testcase):
print x,
Here's the Scheme:
(define list->generator
; Takes a list as argument.
; Returns a generator g such that each call to g returns
; the next element in the list's symmetric-order fringe.
(lambda (x)
(letrec {(produce-value #f) ; set to return-to continuation
(looper
(lambda (x)
(cond
((null? x) 'nada) ; ignore null
((list? x)
(looper (car x))
(looper (cdr x)))
(else
; want to produce this non-list fringe elt,
; and also resume here
(call/cc
(lambda (here)
(set! getnext
(lambda () (here 'keep-going)))
(produce-value x)))))))
(getnext
(lambda ()
(looper x)
; have to signal end of sequence somehow;
; assume false isn't a legitimate fringe elt
(produce-value #f)))}
; return niladic function that returns next value
(lambda ()
(call/cc
(lambda (k)
(set! produce-value k)
(getnext)))))))
(define display-fringe
(lambda (x)
(letrec ((g (list->generator x))
(thiselt #f)
(looper
(lambda ()
(set! thiselt (g))
(if thiselt
(begin
(display thiselt) (display " ")
(looper))))))
(looper))))
(define test-case '((1 ((2 3))) (4) () (((5)) 6)))
(display-fringe test-case)