Изучай Haskell ради Добра! Функциональное решение задач

Функциональное решение задач

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

Вычислитель выражений в обратной польской записи

Обычно мы записываем математические выражения в инфиксной нотации. Например, мы пишем 10 - (4 + 3) * 2. "+", "*" и "-" - инфиксные операторы, такие же как инфиксные функции Хаскелля (+, 'elem', и т.д.). Так нам, людям, удобнее, потому что мы можем легко разобрать такую формулу в уме. Отрицательной стороной такой записи является то, что приходится использовать скобки для обозначения приоритета операций.

Обратная польская запись является способом записи математических выражений. Поначалу она воспринимается с трудом, но ее довольно просто понять и использовать, так как нет необходимости в скобках, и ее очень легко превратить в вычислитель. Хоть большинство современных калькуляторов используют инфиксную нотацию, некоторые люди до сих пор являются приверженцами калькуляторов использующих ПолИЗ. Вот как предыдущее инфиксное выражение выглядит в ПолИЗ: 10 4 3 + 2 * -. Как мы можем вычислить результат? Представьте себе стек. Вы проходите по выражению слева направо. Если текущий элемент - число, надо его поместить (втолкнуть, push) в стек. Если мы рассматриваем оператор, надо взять (вытолкнуть, pop) два числа с вершины стека, применить к ним оператор и втолкнуть результат обратно в стек. Когда вы достигните конца выражения, у вас должно остаться одно число, если, конечно, выражение было правильно записано. Это число и будет результатом.

Давайте разберем выражение 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, помещаем его в стек, и так как у нас больше нет чисел и операторов для разбора, мы получили результат!

Теперь, когда мы знаем как вычислять выражения на ПолИЗ вручную, давайте подумаем, как бы нам написать функцию Хаскелла, которая будет принимать строку с выражением на ПолИЗ, например "10 4 3 + 2 * -", и возвращать нам результат.

Каков может быть тип такой функции? Мы хотим, чтобы она принимала строку и возвращала число. Тип может быть приблизительно таким: solveRPN :: (Num a) => String -> a.

Рекомендация: Очень помогает сначала подумать о том, какой будет декларация типа функции, и записать ее до того как начать ее имплементацию. В Хаскелле, декларация типа функции говорит нам очень многое о функции, благодаря очень строгой системе типов.

Отлично. При реализации решения проблемы на Хаскелле, хорошо припомнить, как вы делали это вручную, и попытаться выделить какую-то идею. В нашем случае мы видим, что мы рассматривали каждое число и оператор как отдельный элемент. Так что будет полезно разбить строку вида "10 4 3 + 2 * -" на список элементов, ["10","4","3","+","2","*","-"].

Далее, что мы мысленно делали со списком элементов? Мы проходили по нему слева направо и работали со стеком, по мере разбора. Последнее предложение ничего не напоминает? Помните, в главе посвященной сверткам, мы говорили, что практически любая функция, которая проходит лист слева направо или справа налево, один элемент за другим, и накапливает (аккумулирует) некоторый результат (не важно, число, список или стек), может быть реализована в виде свертки.

В нашем случае будем использовать левую свертку, так как мы проходим список слева направо. Аккумулятором будет стек, и, следовательно, результатом свертки также будет стек, но как мы видели, он будет содержать единственный элемент.

Еще одна вещь, о которой стоит подумать - а как мы будем реализовывать стек? Я предлагаю использовать список. Также я предлагаю в качестве вершины стека использовать голову стека. Потому что добавление элемента к голове (началу) списка работает гораздо быстрее чем добавление к концу списка. Итого, если у нас есть стек, например, 10, 4, 3, мы представим его списком [3,4,10].

Теперь мы знаем достаточно для того чтобы написать черновик функции. Она будет принимать строку, например "10 4 3 + 2 * -", разбивать ее на элементы и формировать из них список, используя функцию words, получится ["10","4","3","+","2","*","-"]. Далее мы выполним левую свертку и в конце получим стек, содержащий единственный элемент, [-4]. Мы получим этот элемент из списка, он и будет конечным результатом.

Вот наш черновик:

import Data.List

solveRPN :: (Num a) => String -> a

solveRPN expression = head (foldl foldingFunction [] (words expression))

where foldingFunction stack item = ...

Мы принимаем выражение и превращаем его в список элементов. Затем выполняем свертку, используя некоторую функцию. Обратите внимание на [], это начальное значение аккумулятора. Аккумулятором будет стек, таким образом [] представляет пустой стек, он таким и должен быть в начале. После получения результирующего списка с единственным элементом, мы вызываем head для получения первого элемента, затем применяем read.

Все что осталось - реализовать функцию для свертки, которая будет принимать стек, например [4,10], элемент, например "3", и возвращать новый стек, [3,4,10]. Если стек содержит [4,10], элемент равен "*", функция должна вернуть [40]. Но прежде всего давайте перепишем функцию в бесточечном стиле, так как она содержит множество скобок, а они меня бесят.

import Data.List

solveRPN :: (Num a) => String -> a

solveRPN = head . foldl foldingFunction [] . words

where foldingFunction stack item = ...

Вот так. Намного лучше. Итого, функция для свертки принимает стек и элемент, возвращает новый стек. Мы будем использовать сопоставление с образцом для того чтобы получать первые элементы стека и для сопоставления с операторами, например "*" и "-".

solveRPN :: (Num a, Read a) => String -> a

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

И все! Обратите внимание, что мы добавили ограничение на класс в декларации функции Read, так как мы применяем read к строкам, чтобы получить число. Декларация означает, что результат может быть любого типа, который является частью классов типов Num и Read (например, Int, Float, и т.д.)

Для списка ["2","3","+"], наша функция начнет свертку с самого левого элемента. Стек в начале пуст, []. Функция свертки будет вызвана с пустым списком в качестве стека (аккумулятор) и "2" в качестве элемента. Так как этот элемент не является оператором, он будет считан и добавлен в начало []. Новый стек будет равен [2], функция свертки будет вызвана с [2] в качестве стека, и "3" в качестве элемента, функция вернет новый стек, [3,2]. Затем функция свертки вызывается в третий раз, со стеком равным [3,2] и элементом "+". Это приводит к тому, что оба числа будут вытолкнуты из стека, сложены, и результат будет помещен обратно в стек. Результирующий стек равен [5], это число мы вернем.

Погоняем нашу функцию:

ghci> solveRPN "10 4 3 + 2 * -"

-4

ghci> solveRPN "2 3 +"

5

ghci> solveRPN "90 34 12 33 55 66 + * - +"

-3947

ghci> solveRPN "90 34 12 33 55 66 + * - + -"

4037

ghci> solveRPN "90 34 12 33 55 66 + * - + -"

4037

ghci> solveRPN "90 3 -"

87

Отлично, работает! Чем еще хороша наша функция - ее можно легко модифицировать для поддержки других операторов. Операторы не обязательно должны быть бинарными. Например, мы можем создать оператор "log", который выталкивает из стека одно число, и заталкивает обратно его логарифм. Также мы можем создать тернарный оператор, который будет извлекать из стека три числа, и помещать назад результат, например, можно реализовать оператор sum, который будет поднимать их стека и суммировать все числа.

Давайте изменим нашу функцию так, чтобы она понимала еще несколько операторов. Чтобы упростить себе задачу, изменим тип функции так, чтобы она возвращала числа типа Float.

import Data.List

solveRPN :: String -> Float

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 (x:y:ys) "/" = (y / x):ys

foldingFunction (x:y:ys) "^" = (y ** x):ys

foldingFunction (x:xs) "ln" = log x:xs

foldingFunction xs "sum" = [sum xs]

foldingFunction xs numberString = read numberString:xs

Отлично. "/" это, конечно же, деление, и ** - возведение в степень для дробных чисел. Для логарифма мы осуществляем сравнение с образцом для одного элемента и хвоста стека, потому что нам нужен только один элемент для вычисления натурального логарифма. Для оператора суммы мы возвращаем стек из одного элемента, который равен сумме элементов находящихся в стеке до этого.

ghci> solveRPN "2.7 ln"

0.9932518

ghci> solveRPN "10 10 10 10 sum 4 /"

10.0

ghci> solveRPN "10 10 10 10 10 sum 4 /"

12.5

ghci> solveRPN "10 2 ^"

100.0

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

ghci> solveRPN "43.2425 0.5 ^"

6.575903

Я думаю, это делает функцию, которая может вычислять произвольное выражение в обратной польской записи с дробными числами, которое может быть расширено 10 строчками кода, довольно-таки чудесной.

Как можно заметить, функция не устойчива к ошибкам. Если передать ей бессмысленный вход, она вывалится с ошибкой. Мы сделаем ее устойчивой к ошибкам, определив ее тип как solveRPN :: String -> Maybe Float, как только разберемся с монадами (они не страшные, честно). Мы могли бы написать безопасную версию функции прямо сейчас, но это будет довольно-таки скучно, сравнивать с Nothing на каждом шаге. Но если у вас есть желание, попробуйте! Подсказка - вы можете использовать reads, чтобы проверить, было ли чтение успешным.

Из аэропорта до центра

Наша следующая проблема такова: ваш самолет только что приземлился в Англии, и у вас арендована машина. В скором времени запланировано совещание, и вам надо добраться из аэропорта Хитроу в Лондон настолько быстро, насколько это возможно (но без риска!).

Существует две главные дороги из Хитроу в Лондон, а так же некоторое количество более мелких дорог, пересекающих главные дороги. Дорога от одного перекрестка до другого занимает фиксированное количество времени. Задача выбора оптимального пути лежит на вас, ваша задача добраться до Лондона самым быстрым способом. Вы начинаете с левой стороны, и можете переехать на соседнюю главную дорогу, либо ехать прямо.

Как вы видите на рисунку, самый короткий путь в нашем случае - начать движение по главной дороге В, переехать на А, ехать прямо по А, переехать обратно, дважды ехать прямо по В. Если ехать таким образом, дорога занимает 75 минут. Если бы мы выбрали любой другой путь, дорога заняла бы больше.

Наша задача - создать программу, которая примет на вход некоторое представление системы дорог, и напечатает кратчайший путь. Вот как может выглядеть входная информация в нашем случае:

50

10

30

5

90

20

40

2

25

10

8

0

Чтобы разобрать входной файл в уме, представьте его в виде дерева и разбейте систему дорог на секции. Каждая секция состоит из дороги А, дороги В и пересекающей дороги. Чтобы представить это в виде дерева, мы предполагаем что есть последняя замыкающая секция, которую можно проехать за 0 секунд, так как нам не важно, в каком именно месте мы попадем в город, важно только что мы в городе.

Будем решать проблему за три шага, так же мы поступали при создании вычислителя выражений в ПолИЗ,

* Забудьте Хаскелл на минуту, и подумайте, как бы вы решали эту задачу вручную.

* Подумайте, как мы будем представлять данные в Хаскелле

* Выясните, как манипулировать данными в Хаскелле так, чтобы получить результат

При решении предыдущей задачи мы выяснили, что при ручных вычислениях нам нужно держать в голове некоторое подобие стека и проходить по выражению по одному элементу за раз. Мы решили представлять выражение в виде списка строк. В итоге мы использовали левую свертку для обхода списка, и работали со стеком для того чтобы получить результат.

Итак, как мы будем искать кратчайший путь от Хитроу до Лондона вручную. Мы можем посмотреть на картинку и прикинуть, какой путь может быть оптимальным, и, вероятно, мы сделаем правильное предположение. Такое решение работает для очень маленьких карт, но что если у нашей дороги насчитывается 10000 секций? Ого! Также мы не можем сказать, что наше решение оптимально, мы можем сказать что мы более-менее в этом уверены.