Реализация функции вычисления выражений в ОПЗ

Наша функция будет принимать строку, содержащую выражение в обратной польской записи, например, "10 4 3 + 2 * -", и возвра-

щать нам результат вычисле- ния этого выражения.

Каковможетбытьтиптакой функции? Мы хотим, чтобы она принимала строку и возвраща- ла число. Давайте договорим- ся, что результат должен быть вещественным числом, потому что среди других операторов хочется иметь и деление. Тип может быть приблизительно таким:

solveRPN:: String –> Double

ПРИМЕЧАНИЕ. В процессе работы очень полезно сначала поду- мать о том, какой будет декларация типа функции, и записать её, прежде чем приступать к её реализации. В языке Haskell деклара- ция типа функции говорит нам очень многое о функции благодаря строгой системе типов.

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

["10","4","3","+","2","*","–"]

Идём дальше. Что мы мысленно делали со списком элементов? Мы проходили по нему слева направо и работали со стеком по мере

 

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

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

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

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

Вот черновик нашей функции:

solveRPN:: String –> Double

solveRPN expr = head (foldl foldingFunction [] (words expr)) where foldingFunction stack item =...

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

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

 

а элемент равен *, то функция должна вернуть [40]. Но прежде все- го давайте перепишем функцию в бесточечном стиле, так как она содержит множество скобок: лично меня они бесят!

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 + * - + -"

4037.0

ghci> solveRPN "90 3.8 -"

86.2

Отлично, работает!

Добавление новых операторов

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

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

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 (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.9932517730102834

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

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

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

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

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

 

Существуют две главные дороги из Хитроу в Лондон, а также некоторое количество более мелких дорог, пересекающих глав- ные. Путь от одного перекрёстка до другого занимает чётко опре- делённое время. Выбор оптимального пути возложен на вас: ваша задача – добраться до Лондона самым быстрым способом! Вы начи- наете с левой стороны и можете переехать на соседнюю главную дорогу либо ехать прямо.

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

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

0

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

 

вить это в виде дерева, мы предполагаем, что есть последняя замы- кающая секция, которую можно проехать за 0 секунд, так как нам неважно, откуда именно мы въедем в город: важно только, что мы в городе.

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

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

2. Подумайте, как вы будете представлять данные в языке Has- kell. В вычислителе ОПЗ мы решили представлять выраже- ние в виде списка строк.

3. Выясните, как манипулировать данными в языке Haskell так, чтобы получить результат. В прошлом разделе мы воспользо- вались левой свёрткой списка строк, используя стек в качес- тве аккумулятора свёртки.

 

Вычисление кратчайшего пути

Итак, как мы будем искать кратчайший путь от Хитроу до Лон- дона, не используя программных средств? Мы можем посмотреть на картинку, прикинуть, какой путь может быть оптимальным – и, вероятно, сделаем правильное предположение... Вероятно, если дорога небольшая; ну а если у неё насчитывается 10 000 секций? Ого! К тому же мы не будем знать наверняка, что наше решение оптимально: можно лишь сказать, что мы более или менее в этом уверены. Следовательно, это плохое решение.

Посмотрим на упрощённую карту дорожной системы. Можем ли мы найти кратчайший путь до первого перекрёстка (первая точ-

 

ка на А, помеченная А1)? Это довольно просто. Легко увидеть, что будет быстрее – проехать по А или проехать по В и повернуть на A. Очевидно, что выгоднее ехать по В и поворачивать: это займет 40 минут, в то время как езда напрямую по дороге А займет 50 минут. Как насчёт пересечения В1? То же самое! Значительно выгоднее ехать по В (включая 10 минут), так как путь по А вместе с поворотом займет целых 80 минут.

Теперь мы знаем, что кратчайший путь до А1 – это движение по дороге В и переезд на дорогу А по отрезку, который мы назовём С (об- щее время 40 минут), а также знаем кратчайший путь до В1 – проезд по дороге В (10 минут). Поможет ли нам это, если нужно узнать крат- чайший путь до следующего перекрёстка? Представьте себе, да!

Найдём кратчайший путь до пункта A2. Мы можем проехать до А2 из А1 напрямую или ехать через В1 (далее – до В2 либо повернуть на перпендикулярную дорогу). Поскольку мы знаем время пути до А1 и В1, можно легко определить кратчайший путь до А2. Наименьшее время пути до А1 – 40 минут, и ещё за 5 минут мы доберёмся до А2; в результате минимальное время пути на отрезке В–С–А составит 45 минут. Время пути до В1 – всего 10 минут, но затем потребует- ся ещё целых 110, чтобы добраться до В2 и проехать поворот. Оче- видно, кратчайший путь до А2 – это В–С–А. Аналогично кратчайший путь до В2 – проезд до А1 и поворот на другую дорогу.

ПРИМЕЧАНИЕ. Возможно, вы задались вопросом: а что если добраться до А2, переехав на В1 и затем двигаясь прямо? Но мы уже рассмотрели переезд из В1 в А1, когда искали лучший путь до А1, так что нам больше не нужно анализировать этот вариант.

Итак, мы вычислили кратчайшие пути до А2 и В2. Продолжать в том же духе можно до бесконечности, пока мы не достигнем пос- ледней точки. Как только мы выясним, как быстрее всего попасть в пункты А4 и В4, можно будет определить самый короткий путь – он и будет оптимальным.

В общем-то для второй секции мы повторяли те же шаги, что и для первой, но уже принимая во внимание предыдущие кратчай- шие пути до А и В. Мы можем сказать, что на первом шаге наилуч- шие пути были пустыми, с «нулевой стоимостью».

Подведём итог. Чтобы вычислить наилучший путь от Хитроу до Лондона, для начала следует найти кратчайший путь до перекрёст- ка на дороге А. Есть два варианта: сразу ехать по А или двигаться по

 

параллельной дороге и затем сворачивать на дорогу А. Мы запоми- наем время и маршрут. Затем используем тот же метод для нахожде- ния кратчайшего пути до следующего перекрёстка дороги В и запо- минаем его. Наконец, смотрим, как выгоднее ехать до следующего перекрёстка на дороге А: сразу по А или по дороге В с поворотом на А. Запоминаем кратчайший путь и производим те же расчёты для параллельной дороги. Так мы анализируем все секции, пока не достигнем конца. Когда все секции пройдены, самый короткий из двух путей можно считать оптимальным.

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