Миран Липовача - Изучай Haskell во имя добра!

Мы реализовали наш калькулятор обратной польской записи, получая строку вроде "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.

Когда мы говорили о законах монад в главе 13, вы узнали, что функция <=<очень похожа на композицию, но вместо того чтобы работать с обычными функциями типа a –> b, она работает с монадическими функциями типа a –> m b. Вот пример:

ghci> let f = (+1) . (*100)

ghci> f 4

401

ghci> let g = (\x –> return (x+1)) <=< (\x –> return (x*100))

ghci> Just 4 >>= g

Just 401

В данном примере мы сначала произвели композицию двух обычных функций, применили результирующую функцию к 4, а затем произвели композицию двух монадических функций и передали результирующей функции Just 4с использованием операции >>=.

Если у вас есть набор функций в списке, вы можете скомпоновать их все в одну большую функцию, просто используя константную функцию idв качестве исходного аккумулятора и функцию (.)в качестве бинарной. Вот пример:

ghci> letf = foldr (.) id [(+1),(*100),(+1)]

ghci> f 1

201

Функция fпринимает число, а затем прибавляет к нему 1, умножает результат на 100и прибавляет к этому 1.