Learn You a Haskell for Great Good! - Miran Lipovaca [90]
Many times, you can convert a program that uses normal strings to a program that uses bytestrings just by doing the necessary imports and then putting the qualified module names in front of some functions. Sometimes, you need to convert functions that you wrote to work on strings so that they work on bytestrings, but that’s not hard.
Whenever you need better performance in a program that reads a lot of data into strings, give bytestrings a try. Chances are you’ll get some good performance boosts with very little effort on your part. I usually write programs using normal strings and then convert them to use bytestrings if the performance is not satisfactory.
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. This will give you the opportunity to flex your newly acquired Haskell muscles and practice your coding skills.
Reverse Polish Notation Calculator
Usually, when we work with algebraic expressions in school, we write them in an infix manner. For instance, we write 10 - (4 + 3) * 2. Addition (+), multiplication (*), and subtraction (-) are infix operators, just like the infix functions in Haskell (+ `elem`, and so on). As humans, we can parse this form easily in our minds. The downside is that we need to use parentheses to denote precedence.
Another way to write algebraic expressions is to use reverse polish notation, or RPN. In RPN, the operator comes after the numbers, rather than being sandwiched between them. So, instead of writing 4 + 3, we write 4 3 +. But how do we write expressions that contain several operators? For example, how would we write an expression that adds 4 and 3 and then multiplies that by 10? It’s simple: 4 3 + 10 *. Because 4 3 + is equivalent to 7, that whole expression is the same as 7 10 *.
Calculating RPN Expressions
To get a feel for how to calculate RPN expressions, think of a stack of numbers. We go over the expression from left to right. 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 (assuming the expression was well formed).
Let’s see how we would calculate the RPN expression 10 4 3 + 2 * -:
We push 10 onto the stack, so the stack consists of 10.
The next item is 4, so we push it onto the stack as well. The stack is now 10, 4.
We do the same with 3, and the stack is now 10, 4, 3.
We encounter an operator: +. We pop the two top numbers from the stack (so now the stack is just 10), add those numbers together, and push that result to the stack. The stack is now 10, 7.
We push 2 to the stack, and the stack becomes 10, 7, 2.
We encounter another operator. We pop 7 and 2 off the stack, multiply them, and push that result to the stack. Multiplying 7 and 2 produces 14, so the stack is now 10, 14.
Finally, there’s a -. We pop 10 and 14 from the stack, subtract 14 from 10, and push that back.
The number on the stack is now -4. Because there are no more numbers or operators in our expression, that’s our result!
So, that’s how to calculate an RPN expression by hand. Now let’s think about how to make a Haskell function to do the same thing.
Writing an RPN Function
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.
What would the type of that function be? We want it to take a string as a parameter and produce a number as its result. Let’s say that we want the result to be a floating-point number of double precision,