infixorder

infixorder

[oriana paro]

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.




------------------------------------------------------
Passa a Infostrada. ADSL e Telefono senza limiti e senza canone Telecom
http://click.libero.it/infostrada30gen07




_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-user

Re: infixorder

[Mikael Djurfeldt]

2007/1/30, oriana paro <orianaparo@libero.it>:
> 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.


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-user

Re: infixorder

[Ian Grant]

On Tue, 30 Jan 2007 15:43:31 +0100
"Mikael Djurfeldt" <mikael@djurfeldt.com> wrote:

> 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.

As witnessed by the fact that they've apparently learned nothing from
the answers they got to last week's homework problem.


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-user

Re: infixorder

[Jon Wilson]

Hi Oriana,
Well, since you're learning scheme, here is a tip: Use the conventional 
indentation and such.  It will seem weird and you will find yourself 
counting parens at first, but quickly you will get used to it, and begin 
to not even see the parens.  Your code snippet should be written:

(equal?
  (infixwalk
    '((a) b ((c) d (e))))
  '(b a d c e))
=> #t

That little => at the end means "the above (or left) expression 
evaluates to the expression on the right."

The indentation rules for Common Lisp at
"http://dept-info.labri.fr/~strandh/Teaching/MTP/Common/Strandh-Tutorial/indentation.html"
apply more or less to scheme as well.  As that page says, indentation 
rules are /not/ a matter of personal taste, but a matter of /shared 
culture/.
Best of luck with your homework,
Jon Wilson

oriana paro wrote:
> 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.
>
>
>
>
> ------------------------------------------------------
> Passa a Infostrada. ADSL e Telefono senza limiti e senza canone Telecom
> http://click.libero.it/infostrada30gen07
>
>
>
>
> _______________________________________________
> Guile-user mailing list
> Guile-user@gnu.org
> http://lists.gnu.org/mailman/listinfo/guile-user
>   



_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-user

Re: infixorder -- more hints for Oriana, and a slightly OT but interesting consideration

[Luca Saiu]

Hi Oriana.
I see a problem in your statement.

You don't say how a binary tree is encoded as an S-expression. From your 
example I'd initially deduce (let's call this encoding (i)) that you 
represent a leaf tree as a one-element list:
   (node)
and a non-leaf tree as a three element list:
   (left-subtree root-node right-subtree)
Your trees can't be empty. Fine, all of this is reasonable.

Of course you must have all of this *completely* clear in your mind 
before even starting to write your procedure.

The tree in your example '((a) b ((c) d (e))) would be:

     b
    / \
   a   d
      / \
     c   e

How would you traverse the tree in an infix walk? Definitely not as
'(b a d c e) as you say, but as '(a b c d e). What you give is a 
*prefix* order walk, not an infix order walk. Unless, of course, I 
misunderstood the way you represent a tree.
'(b a d c e) would be a correct infix walk for, e.g., this tree:

     a
    / \
   b   c
      / \
     d   e

but I can't find a good way to represent it as '((a) b ((c) d (e))).
This alternative and rather counter-intuitive encoding (let's call it 
encoding (ii)) comes close, but it doesn't explain why the subtree 
rooted at e is represented as (e) and not as e.
- leaf tree (a symbol):
   root-node
- non-leaf tree (a three-element list):
   ((root-node) left-subtree right-subtree)
- again, your trees can't be empty

So either I'm more tired than I think, which may well be the case, or 
your teacher made a mistake.

Anyway, whatever encoding you choose, here are some hints:

* Write three utility procedures extracting the root node, the left 
subtree and the right subtree from a given tree.
* Still assuming your trees can't be empty: write another helper 
procedure returning #t if the given tree is a leaf, and #f if it isn't.
* *Don't* worry about efficiency, not even tail-recursion: just write 
something correct and readable. You can optimize later, if needed.

This way your main procedure will be independent from the tree 
representation, and you'll be able to focus on the main task.
As usual, your main procedure is driven by a case analysis:
* base case (leaf tree). This is trivial: you have to walk a single-node 
tree.
* recursive case (non-leaf tree). Quite simple: use recursion, as Mikael 
already suggested: if you suppose you can walk the left and right 
subtrees, and you have the root node, how do you combine those tree 
"pieces"? You just have to append three lists: the infixwalk of the left 
subtree, a singleton list holding just the root node, and the infixwalk 
of the right subtree. By the way, changing the order in which you append 
  those lists you can also easily get prefix-order or postfix-order 
traversals.

I'm now going to give you a little more help than I should, and show you 
a complete solution assuming encoding (i). If you can modify it to fit 
your encoding I'd say you deserve full marks :-).

(define (infixwalk tree)
   "Return a list holding the nodes of tree, ordered as they are
visited in an infix walk"
   (define (leaf? tree)
     "Return #t iff tree is a leaf"
     (null? (cdr tree))) ; leaf trees are one-element lists
   (define (root tree)
     "Return the root node of the given tree"
     (if (leaf? tree)
         (car tree)      ; the only element of a one-element list
         (cadr tree)))   ; the second element of a three-elements list
   (define (left-subtree tree)
     "Return the left subtree of the given non-leaf tree"
     (if (leaf? tree)
         (error "You can't get the left-subtree of a leaf")
         (car tree))) ; the first element of a three-elements list
   (define (right-subtree tree)
     "Return the right subtree of the given tree"
     (if (leaf? tree)
         (error "You can't get the right-subtree of a leaf")
         (caddr tree))) ; the third element of a three-elements list
   ;; Case analysis: we behave in a different way depending on the
   ;; "shape" of the tree:
   (if (leaf? tree)
       ;; Trivial base case: a one-node tree
       (list (root tree))
       ;; Recursive case: visit the left subtree, then the root, then
       ;; the right subtree:
       (append (infixwalk (left-subtree tree))
               (list (root tree))
               (infixwalk (right-subtree tree)))))

Ok, I think I've helped you. Now in return I'd like you to listen, while 
I tell you a little story.

I'm also from Italy, as you seem to be. I'm now in a haste to finish my 
MD thesis in Computer Science at the University of Pisa, before moving 
to Paris. I'm going to leave in March, most probably for good. I'll miss 
some people, but I doubt I'll miss Italy.

When I started University here in Pisa some years ago they used to teach 
functional programming to first year students. They taught some 
theoretical Computer Science, some Maths (a little more than was 
needed), of course some programming (quite a little *less* than was 
needed -- but you could remedy yourself). Excellent professors with few 
exceptions, and also three or four world-famous outstanding geniuses.
Computer Science wasn't the most difficult degree course, but by all 
means it wasn't easy. You met many fellow students, friendly and 
cheerful, who suddenly disappeared. Out of the blue. Then someone told 
you they'd dropped out. A *lot* of them. Sad as it may be, this was 
perceived as natural.
The research environment at the Computer Science department was 
thriving; you actually felt the enthusiasm of discovery.

This was some years ago. Now, two University reforms later, you sharply 
notice the difference. No theoretical Computer Science at all, unless 
you choose it. Semantics? Ha, you're kidding. A couple of pro forma Math 
exams. Java and XML, from the first to the last year.

Professors are practically all the same as before, but most look tired, 
some nearly a bit ashamed. People pass exams at the first try. The 
Italian University system decided to downgrade itself to produce 
programmers (Java programmers, and I'd say *quite crappy* even as Java 
programmers) at the fastest possible rate. The fame of the University of 
Pisa is rapidly dimming, and rightly so.

The first change, the first thing to go in this suicidal process was the 
teaching of functional programming.

May I ask you where you study? It's a welcome surprise that some 
University in Italy is still teaching Scheme in an entry-level course. 
By the way, Scheme is also an excellent *first* language -- Java is not.

Research in Italy seems mostly in the same state as University. Now, to 
survive in these last months while finishing my thesis, I'm working for 
an important research organization in Italy in a project not deserving 
mention, where I seem to be the only one with a theoretical background. 
We're building a (gratuitously) complex distributed system full of 
intricate internal interfaces, with a very complicated behavior due to 
the distributed caching of data. Replication with updates is *tricky*, I 
told it to my fellow workers, but they don't seem to get it. I talk 
about semantics and types, and people just don't understand what the 
fuck I'm saying.

They keep adding more kludges, and spend most of the time trying to 
solve the problems caused by completely wrong technological choices made 
just for fashion (SOAP, HTTP, XML, XML databases). They also seem to 
completely ignore complexity theory.
The thing will never work. It will literally blow in their hands and 
most of them will never understand why. I'm sorry for them, as they have 
my human sympathy; they're really good guys and they work hard, but they 
*don't know Computer Science*.
Anyway I'll be gone by then, to make some research worthy of this name.

Now, Oriana, you're perfectly free to make any choice you like and not 
to listen to my advice. But if you want to have a future in Computer 
Science, I suggest you to don't give up on Scheme (and C, Prolog, 
algorithms, compiler construction, and a lot of other things).
If my intuition is right, you'll probably manage to pass your exams even 
without any real understanding, and although I'd like things to be 
different I'm not deluded enough to think functional programming is a 
primary focus nowadays. But being able to solve problems like the one 
you presented here is part of the difference between someone assembling 
kludges for a living, and a real computer scientist. Make the right choice.

Best wishes for your life,

-- 
Luca Saiu, maintainer of GNU epsilon
http://www.gnu.org/software/epsilon
http://www.di.unipi.it/~saiu


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-user

Re: infixorder -- more hints for Oriana, and a slightly OT but interesting consideration

[Jon Wilson]

Hi Luca,
>
> Ok, I think I've helped you. Now in return I'd like you to listen, 
> while I tell you a little story.
>
--snip all content--
> Best wishes for your life,
>


Hear hear!  I love a good impassioned speech, and particularly when it 
is advocating the Right Thing.

You aren't by any chance doing programming for Pisa's physics 
department, are you?  Because I've had occasion to work with some of 
Pisa's physics code, one project in particular (I'll give you details 
privately if you ask, no need to spread more gossip than necessary), and 
it was really quite full of kruft and kludge.  The assumption was that 
it was probably written that way so it would be faster (as is the case 
with a lot of nasty looking code), but it turns out that it is way too 
slow.  Just wondering if that was your project (although I think not... 
no SOAP, HTTP, etc involved here... just FORTRAN77 style programming 
(psuedo common blocks) in C++) or if you knew anything about it.

Sorry if this post is slightly incoherent, I'm very sleepy now, and I 
just finished a proof for abstract algebra that really had me by the 
throat for a while.
Regards,
Jon


_______________________________________________
Guile-user mailing list
Guile-user@gnu.org
http://lists.gnu.org/mailman/listinfo/guile-user