Discussion:
iterative functional copying of binary trees
(too old to reply)
Jean Guillaume Pyraksos
2009-05-21 16:49:55 UTC
Permalink
Hi, a small problem. Let's represent binary trees. Leaves are themselves
and nodes are built with tree(r,ls,rs).

Ex: tree(+,tree(*,x,2),tree(-,y,1))
which represents (+ (* x 2) (- y 1)) in Lisp for example.

Problem : program copytree(t) which returns a copy of the tree t,
functionally of course, but with an iterative (tail recursive)
process, using a stack.

I solve this with a two-phase algorithm :
- first build *iteratively* the postfix walking of the tree into a list :
[+,x,2,*,y,1,-,+]
- then walk *iteratively* this list to rebuild a new tree.

Is there a more simple one-phase way (iterative and functional,
first order please, no CPS) to get this algorithm ?

*iteratively* means as usual that the stack space usage is O(1).

Thanks,

JG
Jon Harrop
2009-05-21 17:55:33 UTC
Permalink
Post by Jean Guillaume Pyraksos
Hi, a small problem. Let's represent binary trees. Leaves are themselves
and nodes are built with tree(r,ls,rs).
Ex: tree(+,tree(*,x,2),tree(-,y,1))
which represents (+ (* x 2) (- y 1)) in Lisp for example.
Problem : program copytree(t) which returns a copy of the tree t,
functionally of course, but with an iterative (tail recursive)
process, using a stack.
[+,x,2,*,y,1,-,+]
- then walk *iteratively* this list to rebuild a new tree.
Is there a more simple one-phase way (iterative and functional,
first order please, no CPS) to get this algorithm ?
*iteratively* means as usual that the stack space usage is O(1).
Check out the traversal of balanced binary trees in the Set module of the
OCaml standard library in the "compare" function.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Paul Rubin
2009-05-21 22:23:42 UTC
Permalink
Post by Jean Guillaume Pyraksos
Is there a more simple one-phase way (iterative and functional,
first order please, no CPS) to get this algorithm ?
The very general solution is to use a zipper data structure. I don't
know if that's the kind of answer that would interest you.
Jean Guillaume Pyraksos
2009-05-23 15:03:26 UTC
Permalink
I didn't think of zippers ! Didn't use them for a long time...
Thanks,

JG
Post by Paul Rubin
Post by Jean Guillaume Pyraksos
Is there a more simple one-phase way (iterative and functional,
first order please, no CPS) to get this algorithm ?
The very general solution is to use a zipper data structure. I don't
know if that's the kind of answer that would interest you.
Chung-chieh Shan
2009-05-23 18:46:27 UTC
Permalink
Post by Jean Guillaume Pyraksos
Is there a more simple one-phase way (iterative and functional,
first order please, no CPS) to get this algorithm ?
For "first order please", just defunctionalize the output of CPS.
--
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
We want our revolution, and we want it now! -- Marat/Sade
We want our revolution, and we'll take it at such time as
you've gotten around to delivering it -- Haskell programmer
Jean Guillaume Pyraksos
2009-05-24 10:11:23 UTC
Permalink
Yes, this one tackles me, but I don't have access to a clean litterature
for doing this !
Thanks for some pointers...

JG
Post by Chung-chieh Shan
Post by Jean Guillaume Pyraksos
Is there a more simple one-phase way (iterative and functional,
first order please, no CPS) to get this algorithm ?
For "first order please", just defunctionalize the output of CPS.
Jan Midtgaard
2009-05-25 19:52:45 UTC
Permalink
Post by Jean Guillaume Pyraksos
Post by Chung-chieh Shan
For "first order please", just defunctionalize the output of CPS.
Yes, this one tackles me, but I don't have access to a clean
litterature for doing this ! Thanks for some pointers...
Danvy and Nielsen: "Defunctionalization at Work"

is available at:

http://www.brics.dk/RS/01/23/

It contains a range of examples.



//Jan

Loading...