[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Luca Saiu
Subject: Re: infixorder -- more hints for Oriana, and a slightly OT but interesting consideration
Date: Thu, 01 Feb 2007 06:39:52 +0100
User-agent: Thunderbird (X11/20060928)

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

   / \
  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:

   / \
  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):
- 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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]