 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
OK, so does anybody know the trick to taking a parse tree such as
(2*(5^2))+((8*6)^(x-1)))
and printing it out *without* several billion brackets?
Printing it with brackets as above, or with no brackets at all, is quite
trivial:
output expr = case expr of
Operator n x y = "(" ++ output x ++ n ++ output y ++ ")"
Variable n = n
Constant v = show v
...
But how do you "decide" when the brackets can or can't be omitted?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] dev null> wrote:
> OK, so does anybody know the trick to taking a parse tree such as
>
> (2*(5^2))+((8*6)^(x-1)))
>
> and printing it out *without* several billion brackets?
>
> Printing it with brackets as above, or with no brackets at all, is quite
> trivial:
>
> output expr = case expr of
> Operator n x y = "(" ++ output x ++ n ++ output y ++ ")"
> Variable n = n
> Constant v = show v
> ...
>
> But how do you "decide" when the brackets can or can't be omitted?
Just a thought:
if the next operator up the tree defers (has lower precedence) to the current
operator, omit the brackets.
eg:
(2*(5^2))+((8*6)^(x-1))) + defers to * --> omit 2*(5^2)+((8*6)^(x-1)))
(2*(5^2)) : * defers to ^ --> omit (2*5^2)
(8*6)^(x-1): ^ doesn't defer to * or - --> don't omit
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] devnull> wrote:
> But how do you "decide" when the brackets can or can't be omitted?
If you have the expression in a parsing tree, then that's trivial:
When printing out the current node (which is an operator), if a child
node has a lower operator precedence, then print that child node in
parentheses. If the child node has a higher precedence, then you can
omit the parentheses.
An example (you'd better use a fixed-width font):
+
/ \
3 *
/ \
4 5
When printing this tree, you start with the root node, ie. the '+'.
Since the root node has no parent, it doesn't need to be printed in
parentheses.
Now you recurseively print the left subtree and the right subtree.
The left subtree is not an operator, and thus doesn't need parentheses.
It can be printed as-is. The right subtree is an operator: '*'. Since
'*' has a higher precedence than '+', you don't need to print parentheses
around it. Recursively print the subtrees of this '*' node, and you are done.
You get:
3+4*5
Another example:
*
/ \
3 +
/ \
4 5
This time when printing the right subtree you notice that '+' has a lower
precedence than '*'. Thus you need to print parentheses around it. Otherwise
everything is the same. Thus you get:
3*(4+5)
If a child node has the *same* precedence as the current node, that's
more interesting. Now it depends on whether the operator is associative
or not, and if not, which side of the current node it is. For example
'+' is associative and thus if it has a child node which is also '+',
that child node does not need parentheses. However '-' is not associative,
and if it's the right child node of '+' (or '-'), it requires parentheses.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> If you have the expression in a parsing tree, then that's trivial:
I knew somebody round here would know the answer...
> When printing out the current node (which is an operator), if a child
> node has a lower operator precedence, then print that child node in
> parentheses. If the child node has a higher precedence, then you can
> omit the parentheses.
>
> An example (you'd better use a fixed-width font):
>
> +
> / \
> 3 *
> / \
> 4 5
>
> When printing this tree, you start with the root node, ie. the '+'.
> Since the root node has no parent, it doesn't need to be printed in
> parentheses.
>
> Now you recurseively print the left subtree and the right subtree.
> The left subtree is not an operator, and thus doesn't need parentheses.
> It can be printed as-is. The right subtree is an operator: '*'. Since
> '*' has a higher precedence than '+', you don't need to print parentheses
> around it. Recursively print the subtrees of this '*' node, and you are done.
> You get:
>
> 3+4*5
>
> Another example:
>
> *
> / \
> 3 +
> / \
> 4 5
>
> This time when printing the right subtree you notice that '+' has a lower
> precedence than '*'. Thus you need to print parentheses around it. Otherwise
> everything is the same. Thus you get:
>
> 3*(4+5)
Hmm. OK.
So... maybe when printing out any given subtree, I make the print
function take the precedence of the parent node as an extra argument?
(And omit brackets at the top-level by starting the function with an
infinitely low precedence?)
> If a child node has the *same* precedence as the current node, that's
> more interesting. Now it depends on whether the operator is associative
> or not, and if not, which side of the current node it is. For example
> '+' is associative and thus if it has a child node which is also '+',
> that child node does not need parentheses. However '-' is not associative,
> and if it's the right child node of '+' (or '-'), it requires parentheses.
Ah yes, associativity is a maddening thing. ;-)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> So... maybe when printing out any given subtree, I make the print
> function take the precedence of the parent node as an extra argument?
I'd to print the parens (if needed) in the parent call before recursing.
--
Darren New, San Diego CA, USA (PST)
My fortune cookie said, "You will soon be
unable to read this, even at arm's length."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 12-3-2009 15:22, Invisible wrote:
> OK, so does anybody know the trick to taking a parse tree such as
>
> (2*(5^2))+((8*6)^(x-1)))
>
> and printing it out *without* several billion brackets?
>
> Printing it with brackets as above, or with no brackets at all, is quite
> trivial:
>
> output expr = case expr of
> Operator n x y = "(" ++ output x ++ n ++ output y ++ ")"
> Variable n = n
> Constant v = show v
> ...
>
> But how do you "decide" when the brackets can or can't be omitted?
Why not in (reverse) polish, no brackets at all
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
andrel wrote:
> Why not in (reverse) polish, no brackets at all
If you think *you* can find a suitable encoding for lambda expressions
in reverse polish notation, be my freakin' guest! :-P
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 13-3-2009 10:01, Invisible wrote:
> andrel wrote:
>
>> Why not in (reverse) polish, no brackets at all
>
> If you think *you* can find a suitable encoding for lambda expressions
> in reverse polish notation, be my freakin' guest! :-P
I'd say that polish would be enormously more simple than standard infix.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> Why not in (reverse) polish, no brackets at all
>>
>> If you think *you* can find a suitable encoding for lambda expressions
>> in reverse polish notation, be my freakin' guest! :-P
>
> I'd say that polish would be enormously more simple than standard infix.
Not once you add case expressions, let expressions, type signatures and
so forth.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
andrel wrote:
> Why not in (reverse) polish, no brackets at all
Fun thing:
12+3*
123+*
These two expressions look different, but are guaranteed to produce the
same answer.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 13-3-2009 11:27, Invisible wrote:
>>>> Why not in (reverse) polish, no brackets at all
>>>
>>> If you think *you* can find a suitable encoding for lambda
>>> expressions in reverse polish notation, be my freakin' guest! :-P
>>
>> I'd say that polish would be enormously more simple than standard infix.
>
> Not once you add case expressions, let expressions, type signatures and
> so forth.
The numerical expressions (which is what your question was about) would
still be more simple and there is no rule that other expressions can not
be implemented in another convenient way.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Fun thing:
>
> 12+3*
> 123+*
>
> These two expressions look different, but are guaranteed to produce the
> same answer.
I thought that 12+3* means (1+2)*3 and 123+* means (2+3)*1 ???
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 13-3-2009 11:35, Invisible wrote:
> andrel wrote:
>
>> Why not in (reverse) polish, no brackets at all
>
> Fun thing:
>
> 12+3*
> 123+*
>
> These two expressions look different, but are guaranteed to produce the
> same answer.
Until now I had never realized that even reversed polish could be
interpreted in more than one way. Your interpretation might be
consistent,though that might require some checking. I would say that the
two expressions reduce to 9 and 5. Note that if you insist that
parameters are eaten from left to right subexpressions are not substrings.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Fun thing:
>>
>> 12+3*
>> 123+*
>>
>> These two expressions look different, but are guaranteed to produce
>> the same answer.
>
> I thought that 12+3* means (1+2)*3 and 123+* means (2+3)*1 ???
I stand corrected.
I was pretty certain I remember there being a way to modify the exact
order in which operations are performed yet always arrive at the same
answer. However, I am currently unable to construct a valid example.
Perhaps my memory is off...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> I was pretty certain I remember there being a way to modify the exact
> order in which operations are performed yet always arrive at the same
> answer. However, I am currently unable to construct a valid example.
> Perhaps my memory is off...
How about these?
ABC+*DE+*F*
ABC+DE+**F*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> How about these?
>
> ABC+*DE+*F*
> ABC+DE+**F*
Yes they seem the same to me...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
scott wrote:
>> How about these?
>>
>> ABC+*DE+*F*
>> ABC+DE+**F*
>
> Yes they seem the same to me...
I'M NOT CRAZY! 6_6
Oh, wait...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 13-3-2009 11:59, Invisible wrote:
> Invisible wrote:
>
>> I was pretty certain I remember there being a way to modify the exact
>> order in which operations are performed yet always arrive at the same
>> answer. However, I am currently unable to construct a valid example.
>> Perhaps my memory is off...
>
> How about these?
>
> ABC+*DE+*F*
> ABC+DE+**F*
such rewriting indeed works for any operator $ that satisfies
(A$B)$C=A$(B$C) i.e. AB$C$=ABC$$ in RPN.
BTW Why did you choose this example with such a lot or irrelevant detail?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> So... maybe when printing out any given subtree, I make the print
>> function take the precedence of the parent node as an extra argument?
>
> I'd to print the parens (if needed) in the parent call before recursing.
It's easier to do it the other way around. The function only has to care
what the precedence of the current operator is before recursing. The
recursive call can decide what to do about it.
Using this technique, I was also able to "hack" in support for
associativity. For example, in Haskell function application has the
highest possible precedence, and left associativity (because of curried
functions). So, when recursing from a function application call, it
tells the left subtree that the parent's precedence was 8, but it tells
the right subtree that the parent's precedence was 9.
The result is that if you have
$
/ \
/ \
$ $
/ \ / \
A B C D
it prints out as "A B (C D)", which is correct.
(Although, needless to say, I spent a day confusing myself with what
"higher" precedence means, and mixing up left and right associativity.
It probably doesn't help that the function type constructor is
right-associative because the function application operator is
left-associative...)
What can I say? Apparently I'm not very smart.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> How about these?
>>
>> ABC+*DE+*F*
>> ABC+DE+**F*
>
> such rewriting indeed works for any operator $ that satisfies
> (A$B)$C=A$(B$C) i.e. AB$C$=ABC$$ in RPN.
So... any associative operation then?
A quick check confirms that
ABC*-DE*-F- ==> (A-(B*C))-(D*E)-F ==> A - BC - DE - F
ABC*DE*--F- ==> (A-((B*C)-(D*E)))-F ==> A - BC + DE - F
which aren't the same.
> BTW Why did you choose this example with such a lot or irrelevant detail?
My brain is like mush this morning. This was the first correct example I
could find. It's about 10 years ago that I discovered this effect, so I
wasn't even sure if I was remembering right!
(Currently attempting to build a Haskell parser, printer and type
interence engine. This stuff is surprisingly non-trivial. Having an
argument about RPN in parallel with these activities is exceeding my
mental capacity!)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 13-3-2009 12:24, Invisible wrote:
>>> How about these?
>>>
>>> ABC+*DE+*F*
>>> ABC+DE+**F*
>>
>> such rewriting indeed works for any operator $ that satisfies
>> (A$B)$C=A$(B$C) i.e. AB$C$=ABC$$ in RPN.
>
> So... any associative operation then?
yes. because associativity is the property that you are using in the
reordering.
> A quick check confirms that
>
> ABC*-DE*-F- ==> (A-(B*C))-(D*E)-F ==> A - BC - DE - F
> ABC*DE*--F- ==> (A-((B*C)-(D*E)))-F ==> A - BC + DE - F
>
> which aren't the same.
>
>> BTW Why did you choose this example with such a lot or irrelevant detail?
>
> My brain is like mush this morning. This was the first correct example I
> could find. It's about 10 years ago that I discovered this effect, so I
> wasn't even sure if I was remembering right!
I think that as soon as you find an example you try to reduce it to the
bare essentials and post that. The same actually as when posting a bug.
> (Currently attempting to build a Haskell parser, printer and type
> interence engine.
One word: why?
> This stuff is surprisingly non-trivial. Having an
> argument about RPN in parallel with these activities is exceeding my
> mental capacity!)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> So... any associative operation then?
>
> yes. because associativity is the property that you are using in the
> reordering.
I guess most people just instinctively "know" that addition and
multiplication are associative (not to mention commutative) without
thinking about it too deeply.
>>> BTW Why did you choose this example with such a lot or irrelevant
>>> detail?
>>
>> My brain is like mush this morning. This was the first correct example
>> I could find. It's about 10 years ago that I discovered this effect,
>> so I wasn't even sure if I was remembering right!
>
> I think that as soon as you find an example you try to reduce it to the
> bare essentials and post that. The same actually as when posting a bug.
Ooo, 2 extra operations. Big deal.
>> (Currently attempting to build a Haskell parser, printer and type
>> interence engine.
>
> One word: why?
Two words: why not?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 13-3-2009 12:41, Invisible wrote:
>> I think that as soon as you find an example you try to reduce it to
>> the bare essentials and post that. The same actually as when posting a
>> bug.
>
> Ooo, 2 extra operations. Big deal.
three and it hides what is actually going on. If you had done it, you
would have realized that it was about associativity yourself.
>
>>> (Currently attempting to build a Haskell parser, printer and type
>>> interence engine.
>>
>> One word: why?
>
> Two words: why not?
Because you can spend the same time and intellect on something that does
help you in your career. Some thing that will in the end give you some
credit when you finish it. Not familiar with you open university, but
they or similar institutes might have courses that are just as
interesting as trying to build haskell from the ground up. Granted if
you finish that it might be something interesting on your CV, but what
is the change that you will?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> I think that as soon as you find an example you try to reduce it to
>>> the bare essentials and post that. The same actually as when posting
>>> a bug.
>>
>> Ooo, 2 extra operations. Big deal.
> three and it hides what is actually going on. If you had done it, you
> would have realized that it was about associativity yourself.
What can I say? It wasn't the primary focus of my concentration. I just
wanted to check that my original hypothesis wasn't completely wrong.
>>>> (Currently attempting to build a Haskell parser, printer and type
>>>> interence engine.
>>>
>>> One word: why?
>>
>> Two words: why not?
>
> Because you can spend the same time and intellect on something that does
> help you in your career.
Well, yeah, that would be better. If I could think of something.
> Some thing that will in the end give you some
> credit when you finish it.
I have serious doubts that such a thing exists. I realise that's not
especially rational, but when you live for so long never receiving any
credit for anything you do, no matter how hard it was to do it, you
start to wonder whether credit actually exists at all.
> Not familiar with you open university, but
> they or similar institutes might have courses that are just as
> interesting as trying to build haskell from the ground up.
I looked. The OU in MK don't have anything remotely interesting.
Somebody else might I guess, but how to find them?
If the guys at Strathclyde get back to me it could be very
interesting... but it's been days now, and I've heard nothing.
> Granted if
> you finish that it might be something interesting on your CV, but what
> is the chance that you will?
I don't know. Depends on how difficult it turns out to be.
FWIW, I'm not really trying to "build Haskell from the ground up".
Rather, I'm trying to make a tool to help untangle complex compile
errors. Basically, I type in some code, and the program tells me what
types it's inferring, so you can try to figure out where it's going wrong.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 13-3-2009 12:58, Invisible wrote:
>
>> Some thing that will in the end give you some credit when you finish it.
>
> I have serious doubts that such a thing exists. I realise that's not
> especially rational, but when you live for so long never receiving any
> credit for anything you do, no matter how hard it was to do it, you
> start to wonder whether credit actually exists at all.
Not in business (your boss simply assumes you do what you are paid for)
but in education we normally do.
>> Not familiar with you open university, but they or similar institutes
>> might have courses that are just as interesting as trying to build
>> haskell from the ground up.
>
> I looked. The OU in MK don't have anything remotely interesting.
Does Open here not mean that you don't have to physically go somewhere?
Because I was thinking about one of those. Or the e-learning type of things.
> Somebody else might I guess, but how to find them?
GIYF? Or ask a friend or ask in some random newsgroup.
> If the guys at Strathclyde get back to me it could be very
> interesting... but it's been days now, and I've heard nothing.
>
>> Granted if you finish that it might be something interesting on your
>> CV, but what is the chance that you will?
>
> I don't know. Depends on how difficult it turns out to be.
>
> FWIW, I'm not really trying to "build Haskell from the ground up".
that is what you are thinking now.
> Rather, I'm trying to make a tool to help untangle complex compile
> errors. Basically, I type in some code, and the program tells me what
> types it's inferring, so you can try to figure out where it's going wrong.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> Some thing that will in the end give you some credit when you finish it.
>>
>> I have serious doubts that such a thing exists. I realise that's not
>> especially rational, but when you live for so long never receiving any
>> credit for anything you do, no matter how hard it was to do it, you
>> start to wonder whether credit actually exists at all.
>
> Not in business (your boss simply assumes you do what you are paid for)
> but in education we normally do.
As I say, I'm used to just going through life in the complete absence of
any kind of success, regardless of effort applied. It does things to
your mind.
>> I looked. The OU in MK don't have anything remotely interesting.
>
> Does Open here not mean that you don't have to physically go somewhere?
> Because I was thinking about one of those. Or the e-learning type of
> things.
Well, perhaps. Personally I think *going* somewhere might not be such a
bad idea. At least it would get me away from this job...
A very seriously doubt that adding more letters after my name will have
any measurable effect on my career prospects. But being in a more
positive and supportive environment might.
>> Somebody else might I guess, but how to find them?
>
> GIYF? Or ask a friend or ask in some random newsgroup.
Oh, I can find a few things. But how to apply? I'm afraid I don't really
understand all this stuff.
>> FWIW, I'm not really trying to "build Haskell from the ground up".
>
> that is what you are thinking now.
Meh. Some of the Haskell compilers out there are measured in thousands
of lines of code. Nothing I have ever written is nearly that large. If I
write something and it gets to 1,000 lines, I start trying to find ways
to make it simpler.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 13-3-2009 13:53, Invisible wrote:
> As I say, I'm used to just going through life in the complete absence of
> any kind of success, regardless of effort applied. It does things to
> your mind.
Yeah, I noticed. Which does not mean that I have to accept that.
>>> I looked. The OU in MK don't have anything remotely interesting.
>>
>> Does Open here not mean that you don't have to physically go somewhere?
>> Because I was thinking about one of those. Or the e-learning type of
>> things.
>
> Well, perhaps. Personally I think *going* somewhere might not be such a
> bad idea. At least it would get me away from this job...
I though that this started out as some advise about doing things while
you were still on the job, but that may be just me.
> A very seriously doubt that adding more letters after my name will have
> any measurable effect on my career prospects.
In the Netherlands even dropping a letter before your name can change a lot.
> But being in a more positive and supportive environment might.
yes, but apparently you first have to move to such a place before you
would even contemplate moving. Well, apparently you enjoy recursive
problems.
>
>>> Somebody else might I guess, but how to find them?
>>
>> GIYF? Or ask a friend or ask in some random newsgroup.
>
> Oh, I can find a few things. But how to apply? I'm afraid I don't really
> understand all this stuff.
Apply? You simply fill in some forms I would expect.
Somewhat related: One of my colleagues is very much involved in an
on-line biomedical engineering curriculum (http://www.evicab.eu/). They
have a signal and imaging analysis course, which might be interesting to
you. I can however not immediately find how you can actually do the
on-line exams without being a student on a university.
>>> FWIW, I'm not really trying to "build Haskell from the ground up".
>>
>> that is what you are thinking now.
>
> Meh. Some of the Haskell compilers out there are measured in thousands
> of lines of code. Nothing I have ever written is nearly that large. If I
> write something and it gets to 1,000 lines, I start trying to find ways
> to make it simpler.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> Not once you add case expressions, let expressions, type signatures and
> so forth.
FORTH
--
Darren New, San Diego CA, USA (PST)
My fortune cookie said, "You will soon be
unable to read this, even at arm's length."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
andrel wrote:
> In the Netherlands even dropping a letter before your name can change a
> lot.
I'm not sure what that means?
I have noticed that putting "the" before your name gets you noticed.
"I'd like you to meet Darren New."
"No no. It's The Darren New."
--
Darren New, San Diego CA, USA (PST)
My fortune cookie said, "You will soon be
unable to read this, even at arm's length."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 13-3-2009 17:31, Darren New wrote:
> andrel wrote:
>> In the Netherlands even dropping a letter before your name can change
>> a lot.
>
> I'm not sure what that means?
An MSc is a Drs (short for Doctorandus, he who must/will become a
doctor) and a PhD is a Dr (the actual Doctor) and we place the titles in
front of the name. So when I did my thesis I went from Drs. Linnenbank
to Dr. Linnenbank. Note that Drs does not mean more than one doctorate,
a mistake sometimes made by some foreigners.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
andrel wrote:
> On 13-3-2009 17:31, Darren New wrote:
>> andrel wrote:
>>> In the Netherlands even dropping a letter before your name can change
>>> a lot.
>>
>> I'm not sure what that means?
>
> An MSc is a Drs (short for Doctorandus, he who must/will become a
> doctor) and a PhD is a Dr (the actual Doctor) and we place the titles in
> front of the name. So when I did my thesis I went from Drs. Linnenbank
> to Dr. Linnenbank. Note that Drs does not mean more than one doctorate,
> a mistake sometimes made by some foreigners.
I see. We don't do that here. We don't get any letters before we finish.
Altho some pre-PhD students put "ABT" after their name - All But Thesis. :-)
--
Darren New, San Diego CA, USA (PST)
My fortune cookie said, "You will soon be
unable to read this, even at arm's length."
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 13-3-2009 18:32, Darren New wrote:
> I see. We don't do that here. We don't get any letters before we finish.
But a Drs is a finished MSc.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
