Изучай Haskell ради Добра! Функциональное решение задач |
- Statistics
- Participants
- Translate into Russian
- Translation result
- Translated in draft, editing and proof-reading required. Completed: 12%.
If you do not want to register an account, you can sign in with OpenID.
Изучай Haskell ради Добра! Функциональное решение проблем | Изучай Haskell ради Добра! Функциональное решение задач | |
Functionally Solving Problems | ||
In this chapter, we'll take a look at a few interesting problems and how to think functionally to solve them as elegantly as possible. We probably won't be introducing any new concepts, we'll just be flexing our newly acquired Haskell muscles and practicing our coding skills. Each section will present a different problem. First we'll describe the problem, then we'll try and find out what the best (or least worst) way of solving it is. | В этой главе мы рассмотрим несколько интересных проблем, узнаем как мыслить функционально, для того чтобы решить их настолько элегантно, насколько возможно. Скорее всего мы не будем вводить новых концепций, просто разомнем вновь приобретенные Хаскелл мускулы и попрактикуем навыки программирования. Каждый раздел представляет отдельную проблему. Мы будем давать описание проблемы и будем искать лучшее (или не самое худшее) решение. | |
Reverse Polish notation calculator | ||
Usually when we write mathematical expressions in school, we write them in an infix manner. For instance, we write 10 - (4 + 3) * 2. +, * and - are infix operators, just like the infix functions we met in Haskell (+, `elem`, etc.). This makes it handy because we, as humans, can parse it easily in our minds by looking at such an expression. The downside to it is that we have to use parentheses to denote precedence. | Обычно мы записываем математические выражения в инфиксной нотации. Например, мы пишем 10 - (4 + 3) * 2. "+", "*" и "-" - инфиксные операторы, такие же как инфиксные функции Хаскелля (+, 'elem', и т.д.). Так нам, людям, удобнее, потому что мы можем легко разобрать такую формулу в уме. Отрицательной стороной такой записи является то, что приходится использовать скобки для обозначения приоритета операций. | |
Reverse Polish notation is another way of writing down mathematical expressions. Initially it looks a bit weird, but it's actually pretty easy to understand and use because there's no need for parentheses and it's very easy to punch into a calculator. While most modern calculators use infix notation, some people still swear by RPN calculators. This is what the previous infix expression looks like in RPN: 10 4 3 + 2 * -. How do we calculate what the result of that is? Well, think of a stack. You go over the expression from left to right. Every time a number is encountered, push it on to the stack. When we encounter an operator, take the two numbers that are on top of the stack (we also say that we pop them), use the operator and those two and then push the resulting number back onto the stack. When you reach the end of the expression, you should be left with a single number if the expression was well-formed and that number represents the result. | Обратная польская запись является способом записи математических выражений. Поначалу она воспринимается с трудом, но ее довольно просто понять и использовать, так как нет необходимости в скобках, и ее очень легко превратить в вычислитель. Хоть большинство современных калькуляторов используют инфиксную нотацию, некоторые люди до сих пор являются приверженцами калькуляторов использующих ПолИЗ. Вот как предыдущее инфиксное выражение выглядит в ПолИЗ: 10 4 3 + 2 * -. Как мы можем вычислить результат? Представьте себе стек. Вы проходите по выражению слева направо. Если текущий элемент - число, надо его поместить (втолкнуть, push) в стек. Если мы рассматриваем оператор, надо взять (вытолкнуть, pop) два числа с вершины стека, применить к ним оператор и втолкнуть результат обратно в стек. Когда вы достигните конца выражения, у вас должно остаться одно число, если, конечно, выражение было правильно записано. Это число и будет результатом. | |
Let's go over the expression 10 4 3 + 2 * - together! First we push 10 on to the stack and the stack is now 10. The next item is 4, so we push it to the stack as well. The stack is now 10, 4. We do the same with 3 and the stack is now 10, 4, 3. And now, we encounter an operator, namely +! 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, the stack for now is 10, 7, 2. We've encountered an operator again, so let's pop 7 and 2 off the stack, multiply them and push that result to the stack. Multiplying 7 and 2 produces a 14, so the stack we have now is 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 and because there are no more numbers or operators in our expression, that's our result! | Давайте разберем выражение 10 4 3 + 2 * - вместе. Сначала мы помещаем 10 в стек, в стеке теперь содержится одно число. Следующий элемент - число 4, мы помещаем его в стек. То же самое делаем с тройкой, стек теперь равен 10, 4, 3. И, наконец-то, нам встречается оператор, а именно "плюс". Мы выталкиваем предыдущие два числа из стека (в стеке останется 10), складываем их, помещаем результат в стек. Теперь в стеке 10, 7. Заталкиваем 2 в стек, теперь там 10, 7, 2. Мы снова дошли до оператора, вытолкнем 7 и 2 из стека, перемножим их, положим результат в стек. Умножение 7 на 2 даст 14, в стеке будет 10, 14. Получаем последний оператор, минус. Выталкиваем 10 и 14 из стека, вычитаем 10 из 14, получаем -4, помещаем его в стек, и так как у нас больше нет чисел и операторов для разбора, мы получили результат! |
© Miran Lipovača. License: creative commons attribution noncommercial blah blah blah ... license
