homework help: upn parser

Leon Smith lps at cwru.edu
Mon Dec 15 04:35:34 EST 2003


Hi Max!

This is a type definiton, which says that parsing takes one argument,  a 
String, and gives you back a list of OpTree:

> parsing :: String->[OpTree]
>
This is a function definition.   The part before the = is called the 
left hand side, while the part after the = is called the right hand side.

> parsing (a:b:c:xs) t
>  |isDigit b = ((parsing xs)) ((Term (read a) c (read b)):t)
>  
>
The (a:b:c:xs) is an example of a pattern.   You are using the list 
constructor (:)  to break down the list into  individual items.   
According to your type definition,  this argument is of type String, 
which is the same thing as [Char].    Thus,  a,  b, and c are bound to 
single characters,  while xs is the bound to the rest of the string, 
assuming  your string has at least three characters.   If your string 
has less than three characters,  then this pattern fails and the next 
clause in your function definiton will be tried. 
Then, according to your function definition,  you then bind the second 
argument of the function to the variable "t".   However,  your type 
definition says you only have one argument.   Since they disagree, this 
is an error. 
The right hand side of your function definition contains lots of errors, 
as you suggest.

You probably want to rethink your type definition.   I'd suggest the 
following:

parsing :: String -> [OpTree] -> OpTree

This says that parsing is a function that takes two arguments,   a list 
of characters and a list of OpTrees,  and returns a single OpTree.   You 
are going to treat the second list argument like a stack.   When you run 
across a number in your string,  you are going to take the number off 
the string and push it onto the stack.  When you run across an operation 
in your string,  you are going to take two elements off the stack, 
combine the elements from the stack using the operation,  and push the 
result back on the stack.    Thus,  your solution would contain this 
kind of structure:

parsing  ( string_with_number_in_front )  ( stack )
    = parsing ( string_without_number )  ( Number (the_number) : stack )
parsing  ( string_with_operation_in_front ) (last_element : next_element 
: rest_stack)
    = parsing  ( string_without_operation )   ( Term last_element 
(the_operation) next_element : rest_stack )

Now,  you must consider the boundary cases of the function "parsing".   
What I mean is,  what kinds of clauses do you need for when you are done 
with recursion,  and what should your first call to this function look 
like?

Of course,  you need to try out your code and carefully think about what 
it's doing.  When asking for homework help on haskell-cafe,  Haskellers 
have been known to introduce small intentional errors into their advice.

Also,  it's very impressive that Paul Natorp high school is using 
Haskell in it's coursework!   In the United States,  I've never heard of 
a high school that takes functional programming seriously.   Sadly, many 
American universities don't take functional programming seriously 
either.   Americans are really behind the game in this regard.

Hope this helps.

best,
leon



More information about the Haskell-Cafe mailing list