* Re: infixorder -- more hints for Oriana, and a slightly OT but interesting consideration
2007-01-30 13:39 infixorder oriana paro
2007-01-30 14:43 ` infixorder Mikael Djurfeldt
2007-01-30 15:46 ` infixorder Jon Wilson
@ 2007-02-01 5:39 ` Luca Saiu
2007-02-05 6:41 ` Jon Wilson
2 siblings, 1 reply; 6+ messages in thread
From: Luca Saiu @ 2007-02-01 5:39 UTC (permalink / raw)
To: oriana paro; +Cc: guile-user
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
^ permalink raw reply [flat|nested] 6+ messages in thread