Создание безопасного калькулятора выражений в обратной польской записи

Решая задачу реализации калькулятора для обратной польской за- писи в главе 10, мы отметили, что он работал хорошо до тех пор,

пока получаемые им входные дан- ные имели смысл. Но если что-то шло не так, это приводило к аварий- ному отказу всей нашей программы. Теперь, когда мы знаем, как сделать уже существующий код монадичес- ким, давайте возьмём наш кальку- лятор и добавим в него обработку ошибок, воспользовавшись мона- дой Maybe.

Мы реализовали наш калькуля- торобратнойпольскойзаписи, полу- чая строку вроде "1 3 + 2 *" и разделяя её на слова, чтобы получить нечто подобное: ["1","3","+","2","*"].

Затем мы сворачивали этот список, начиная с пустого стека и используя бинарную функцию свёртки, кото-

рая добавляет числа в стек либо манипулирует числами на вершине стека, чтобы складывать их или делить и т. п.

Вот это было основным телом нашей функции:

import Data.List

 

solveRPN:: String –> Double

solveRPN = head. foldl foldingFunction []. words

СОЗДАНИЕ БЕЗОПАСНОГО КАЛЬКУЛЯТОРА ВЫРАЖЕНИЙ 455

Мы превратили выражение в список строк и свернули его, ис- пользуя нашу функцию свёртки. Затем, когда у нас в стеке остался лишь один элемент, мы вернули этот элемент в качестве ответа. Вот такой была функция свёртки:

foldingFunction:: [Double] –> String –> [Double] 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

Аккумулятором свёртки был стек, который мы представили списком значений типа Double. Если по мере того, как функция проходила по выражению в обратной польской записи, текущий элемент являлся оператором, она снимала два элемента с верхушки стека, применяла между ними оператор, а затем помещала резуль- тат обратно в стек. Если текущий элемент являлся строкой, пред- ставляющей число, она преобразовывала эту строку в фактическое число и возвращала новый стек, который был как прежний, только с этим числом, протолкнутым на верхушку.

Давайте сначала сделаем так, чтобы наша функция свёртки до- пускала мягкое окончание с неудачей. Её тип изменится с того, ка- ким он является сейчас, на следующий:

foldingFunction:: [Double] –> String –> Maybe [Double]

Поэтому она либо вернёт новый стек в конструкторе Just, либо потерпит неудачу, вернув значение Nothing.

Функция reads похожа на функцию read, за исключением того, что она возвращает список с одним элементом в случае успешно- го чтения. Если ей не удалось что-либо прочитать, она возвраща- ет пустой список. Помимо прочитанного ею значения она также возвращает ту часть строки, которую она не потребила. Мы сейчас скажем, что она должна потребить все входные данные для работы, и превратим её для удобства в функцию readMaybe. Вот она:

readMaybe:: (Read a) => String –> Maybe a readMaybe st = case reads st of [(x, "")] –> Just x

_ –> Nothing

Теперь протестируем её:

 

ghci> readMaybe "1":: Maybe Int Just 1

ghci> readMaybe "ИДИ К ЧЁРТУ":: Maybe Int Nothing

Хорошо, кажется, работает. Итак, давайте превратим нашу функ- цию свёртки в монадическую функцию, которая может завершать- ся неудачей:

foldingFunction:: [Double] –> String –> Maybe [Double] foldingFunction (x:y:ys) "*" = return ((y * x):ys) foldingFunction (x:y:ys) "+" = return ((y + x):ys) foldingFunction (x:y:ys) "-" = return ((y - x):ys)

foldingFunction xs numberString = liftM (:xs) (readMaybe numberString)

Первые три случая – такие же, как и прежние, только новый стек обёрнут в конструктор Just (для этого мы использовали здесь функцию return, но могли и просто написать Just). В последнем случае мы используем вызов readMaybe numberString, а затем отоб- ражаем это с помощью (:xs). Поэтому если стек равен [1.0,2.0], а выражение readMaybe numberString даёт в результате Just 3.0, то ре- зультатом будет [3.0,1.0,2.0]. Если же readMaybe numberString даёт в результате значение Nothing, результатом будет Nothing.

Давайте проверим функцию свёртки отдельно:

ghci> foldingFunction [3,2] "*" Just [6.0]

ghci> foldingFunction [3,2] "-" Just [-1.0]

ghci> foldingFunction [] "*"

Nothing

ghci> foldingFunction [] "1" Just [1.0]

ghci> foldingFunction [] "1 уа-уа-уа-уа" Nothing

Похоже, она работает! А теперь пришла пора для новой и улуч- шенной функции solveRPN. Вот она перед вами, дамы и господа!

import Data.List

 

solveRPN:: String –> Maybe Double solveRPN st = do

КОМПОЗИЦИЯ МОНАДИЧЕСКИХ ФУНКЦИЙ 457

 

[result] <– foldM foldingFunction [] (words st) return result

Как и в предыдущей версии, мы берём строку и превращаем её в список слов. Затем производим свёртку, начиная с пустого сте- ка, но вместо выполнения обычной свёртки с помощью функции foldl используем функцию foldM. Результатом этой свёртки с помо- щью функции foldM должно быть значение типа Maybe, содержащее список (то есть наш окончательный стек), и в этом списке должно быть только одно значение. Мы используем выражение do, чтобы взять это значение, и называем его result. В случае если функция foldM возвращает значение Nothing, всё будет равно Nothing, потому что так устроена монада Maybe. Обратите внимание на то, что мы производим сопоставление с образцом в выражении do, поэтому если список содержит более одного значения либо ни одного, со- поставление с образцом окончится неудачно и будет произведено значение Nothing. В последней строке мы просто вызываем выраже- ние return result, чтобы представить результат вычисления выра- жения в обратной польской записи как результат окончательного значения типа Maybe.

Давайте попробуем:

ghci> solveRPN "1 2 * 4 +"

Just 6.0

ghci> solveRPN "1 2 * 4 + 5 *"

Just 30.0

ghci> solveRPN "1 2 * 4"

Nothing

ghci> solveRPN "1 8 трам-тарарам" Nothing

Первая неудача возникает из-за того, что окончательный стек не является списком, содержащим один элемент: в выражении do сопоставление с образцом терпит фиаско. Вторая неудача возника- ет потому, что функция readMaybe возвращает значение Nothing.