Создание безопасного калькулятора выражений в обратной польской записи
Решая задачу реализации калькулятора для обратной польской записи в главе 10, мы отметили, что он работал хорошо до тех пор, пока получаемые им входные данные имели смысл. Но если что-то шло не так, это приводило к аварийному отказу всей нашей программы. Теперь, когда мы знаем, как сделать уже существующий код монадическим, давайте возьмём наш калькулятор и добавим в него обработку ошибок, воспользовавшись монадой Maybe.
Мы реализовали наш калькулятор обратной польской записи, получая строку вроде "1 3 + 2 *" и разделяя её на слова, чтобы получить нечто подобное: ["1","3","+","2","*"]. Затем мы сворачивали этот список, начиная с пустого стека и используя бинарную функцию свёртки, которая добавляет числа в стек либо манипулирует числами на вершине стека, чтобы складывать их или делить и т. п.
Вот это было основным телом нашей функции:
import Data.List
solveRPN :: String –> Double
solveRPN = head . foldl foldingFunction [] . words
Мы превратили выражение в список строк и свернули его, используя нашу функцию свёртки. Затем, когда у нас в стеке остался лишь один элемент, мы вернули этот элемент в качестве ответа. Вот такой была функция свёртки:
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
[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.