「学习笔记」Chapter 10 FUNCTIONALLY SOLVING PROBLEMS　in Haskell

Chapter 10 FUNCTIONALLY SOLVING PROBLEMS

In this chapter, we’ll look at a couple of interesting problems, and we’ll think about how to solve them as elegantly as possible using functional programming techniques.

Table of Contents1 Reverse Polish Notation Calculator1.1 Calculating RPN Expressions1.2 Writing an RPN Function1.3 Adding More Operators

Usually, when we work with algebraic expressions in school, we write them in an infix manner. For instance, we write 10 - (4 + 3) * 2. Another way to write algebraic expressions is to use reverse polish nota- tion, or RPN.So, instead of writing 4 + 3, we write 4 3 +

Every time a number is encountered, put it on top of the stack (push it onto the stack). When we encounter an operator, we take the two numbers that are on top of the stack (pop them), use the operator with those two, and then push the resulting number back onto the stack. When we reach the end of the expression, we should be left with a single number that represents the result.

Our function will take a string that contains an RPN expression as its parameter (like "10 4 3 + 2 * -") and give us back that expression’s result. It really helps to first think what the type declaration of a function should be before dealing with the implementation. The type of RPN Function is

solveRPN :: String -> Double

For our RPN expression calculation, we treated every number or operator that was separated by a space as a single item. So it might help us if we start by breaking a string like "10 4 3 + 2 * -" into a list of items.

["10","4","3","+","2","*","-"]

Next up, what did we do with that list of items in our head? We went over it from left to right and kept a stack as we did that.In this case, we’re going to use a left fold, because we go over the list from left to right. The accumulator value will be our stack, so the result from the fold will also be a stack. Here’s a sketch of that function:

solveRPN :: String -> DoublesolveRPN expresstion = head . foldl foldingFunction [] . words expresstion  where foldingFunction stack item = ...

Then, we implement foldingFunction.

solveRPN :: String -> DoublesolveRPN  = head . foldl foldingFunction [] . words  where foldingFunction (x:y:ys) "*" = (y*x):ys        foldingFunction (x:y:ys) "+" = (y+x):ys        foldingFunction (x:y:ys) "-" = (y-x):ys        foldingFunction xs numberString = read numberString:xs

Note that if the item is none of the operators, we assume it’s a string that repre- sents a number. If it’s a number, we just apply read to that string to get a number from it and return the previous stack but with that number pushed to the top.

Load and test solveRPN.

ghci>solveRPN "2 3 +"5.0ghci>solveRPN "10 4 3 + 2 * -"-4.0

One nice thing about this solution is that it can be easily modified to support various other operators.