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