Re: infixorder

[Mikael Djurfeldt]

2007/1/30, oriana paro <address@hidden>:
> Hi. I'm learning scheme (Guile) and I have some problem with the infix order 
> walk in a tree...
> I want to write a function infixwalk that walks though a tree in infix order 
> (left tree - node - righ tree) so that the call
> (equal?
>    (infixwalk
>        '( (a) b ( (c) d (e) ) )
>     )
>     '(b a d c e)
> )
> returns #t.
> Anyone can help me?? Thanks in advance.

This type of question usually turns up when a student wants help with
homework and is therefore usually dismissed---in any case you wouldn't
learn anything if you got the complete code.  But I guess a couple of
hints doesn't do any harm:

Try recursion:

1. If you assume that "infixwalk" already exists and works, is there
some way you can break down a complex version of the problem (for
example the full tree above) so that you can write the solution in
terms of one or more calls to "infixwalk" applied to simpler versions
of the problem?

2. Is there some way you can distinguish such a complex version of the
problem (where you need to use infixwalk to compute the solution) from
a version of the problem which is so simple that you can return the
result directly?

3. Write infixwalk as a conditional which chooses between the simple
and complex version.  You need the simple case so that your recursion
on the complex version terminates cleanly with a simple case.