>solveRPN :: String –> Double
>solveRPN = head . foldl foldingFunction [] . words
> where foldingFunction stack item = ...
То-то! Намного лучше. Итак, функция для свёртки принимает стек и элемент и возвращает новый стек. Мы будем использовать сопоставление с образцом для того, чтобы получать первые элементы стека, и для сопоставления с операторами, например >* и >–.
>solveRPN :: String –> Double
>solveRPN = head . foldl foldingFunction [] . words
> where
> foldingFunction (x:y:ys) "*" = (x * y):ys
> foldingFunction (x:y:ys) "+" = (x + y):ys
> foldingFunction (x:y:ys) "–" = (y – x):ys
> foldingFunction xs numberString = read numberString:xs
Мы уложились в четыре образца. Образцы будут сопоставляться транслятором в порядке записи. Вначале функция свёртки проверит, равен ли текущий элемент >"*". Если да, то функция возьмёт список, например >[3,4,9,3], и присвоит двум первым элементам имена >x и >y соответственно. В нашем случае >x будет соответствовать тройке, а >y – четвёрке; >ys будет равно >[9,3]. В результате будет возвращён список, состоящий из >[9,3], и в качестве первого элемента будет добавлено произведение тройки и четвёрки. Таким образом, мы выталкиваем два первых числа из стека, перемножаем их и помещаем результат обратно в стек. Если элемент не равен >"*", сопоставление с образцом продолжается со следующего элемента, проверяя >"+", и т. д.
Если элемент не совпадёт ни с одним оператором, то мы предполагаем, что это строка, содержащая число. Если это так, то мы вызываем функцию >read с этой строкой, чтобы получить число, добавляем его в вершину предыдущего стека и возвращаем получившийся стек.
Для списка >["2","3","+"] наша функция начнёт свёртку с самого левого элемента. Стек в начале пуст, то есть представляет собой >[]. Функция свёртки будет вызвана с пустым списком в качестве стека (аккумулятора) и >"2" в качестве элемента. Так как этот элемент не является оператором, он будет просто добавлен в начало стека >[]. Новый стек будет равен >[2], функция свёртки будет вызвана со значением >[2] в качестве стека и >"3" в качестве элемента; функция вернёт новый стек, >[3,2]. Затем функция свёртки вызывается в третий раз, со стеком равным >[3,2] и элементом >"+". Это приводит к тому, что оба числа будут вытолкнуты из стека, сложены, а результат будет помещён обратно в стек. Результирующий стек равен >[5] – это число мы вернём.
Погоняем нашу функцию:
>ghci> solveRPN "10 4 3 + 2 * -"
>-4.0
>ghci> solveRPN "2 3.5 +"
>5.5
>ghci> solveRPN "90 34 12 33 55 66 + * - +"
>-3947.0
>ghci> solveRPN "90 34 12 33 55 66 + * - + -"