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

Обратная польская запись (ОПЗ) является одним из способов записи математических выражений. В ОПЗ операторы записываются не между числами, а после них. Так, вместо 4 + 3 нужно писать 4 3 +. Но как тогда записать выражения, содержащие несколько операторов? Например, как бы мы записали выражение, складывающее 4 и 3, а потом умножающее сумму на 10? Легко: 4 3 + 10 *. Поскольку 4 3 + равно 7, то всё выражение равно 7 10 *, т. е. 70. Поначалу такая запись воспринимается с трудом, но её довольно просто понять и использовать, так как необходимости в скобках нет и произвести вычисление очень легко. Хотя большинство современных калькуляторов используют инфиксную нотацию, некоторые люди до сих пор являются приверженцами калькуляторов, использующих ОПЗ.

 

Вычисление выражений в ОПЗ

Как мы можем вычислить результат? Представьте себе стек. Вы проходите по выражению слева направо. Если текущий элемент – число, его надо поместить (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, помещаем число в стек, и так как у нас больше нет чисел и операторов для разбора, мы получили конечный результат!

Теперь, когда мы знаем, как вычислять выражения на ОПЗ вручную, давайте подумаем, как бы нам написать функцию на языке Haskell, которая делает то же самое.

 

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

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

 

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

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

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

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

50

10

30

5

90

20

40

2

25

10

8

0

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

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

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

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

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

 

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

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

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

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

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

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

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

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

Подведём итог. Чтобы вычислить наилучший путь от Хитроу до Лондона, для начала следует найти кратчайший путь до перекрёстка на дороге A. Есть два варианта: сразу ехать по A или двигаться по параллельной дороге и затем сворачивать на дорогу A. Мы запоминаем время и маршрут. Затем используем тот же метод для нахождения кратчайшего пути до следующего перекрёстка дороги B и запоминаем его. Наконец, смотрим, как выгоднее ехать до следующего перекрёстка на дороге A: сразу по A или по дороге B с поворотом на A. Запоминаем кратчайший путь и производим те же расчёты для параллельной дороги. Так мы анализируем все секции, пока не достигнем конца. Когда все секции пройдены, самый короткий из двух путей можно считать оптимальным.

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

 

Представление пути на языке Haskell

Следующий наш шаг: как представить дорожную систему в системе типов языка Haskell? Один из способов – считать начальные точки и перекрёстки узлами графа, которые ведут к другим перекрёсткам. Если мы представим, что начальные точки связаны друг с другом дорогой единичной длины, мы увидим, что каждый перекрёсток (или узел графа) указывает на узел на противоположной стороне, а также на следующий узел с той же стороны. За исключением последних узлов они просто показывают на противоположную сторону.

data Node = Node Road Road | EndNode Road

data Road = Road Int Node

Узел – это либо обычный узел, указывающий путь до противоположной дороги и путь до следующего узла по той же дороге, либо конечный узел, который содержит информацию только о противоположной дороге. Дорога хранит информацию о длине отрезка и об узле, к которому она ведёт. Например, первая часть дороги A будет представлена как Road 50 a1, где a1 равно Node x y; при этом x и y – дороги, которые ведут к B1 и A2.

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

data Node = Node Road (Maybe Road)

data Road = Road Int Node

Можно решить задачу, пользуясь таким способом представления дорожной системы; но нельзя ли придумать что-нибудь попроще? Если вспомнить решение задачи в уме, мы всегда проверяли длины трёх отрезков дороги: отрезок по дороге A, отрезок по дороге B и отрезок C, который их соединяет. Когда мы искали кратчайший путь к пунктам A1 и B1, то рассматривали длины первых трёх частей, которые были равны 50, 10 и 30. Этот участок сети дорог назовём секцией. Таким образом, дорожная система в нашем примере легко может быть представлена в виде четырёх секций: (50, 10, 30), (5, 90, 20), (40, 2, 25) и (10, 8, 0).

Всегда лучше делать типы данных настолько простыми, насколько это возможно – но не проще!

data Section = Section { getA :: Int, getB :: Int, getC :: Int }

   deriving (Show)

type RoadSystem = [Section]

Так гораздо ближе к идеалу! Записывается довольно просто, и у меня есть предчувствие, что для решения нашей задачи такое описание подойдёт отлично. Секция представлена обычным алгебраическим типом данных, который содержит три целых числа для представления длин трёх отрезков пути. Также мы определили синоним типа, который говорит, что RoadSystem представляет собой список секций.

ПРИМЕЧАНИЕ. Для представления секции дороги мы могли бы использовать кортеж из трёх целых чисел: (Int, Int, Int) . Кортежи вместо алгебраических типов данных лучше применять для решения маленьких локальных задач, но в таких случаях, как наш, лучше создать новый тип. Это даёт системе типов больше информации о том, что есть что. Мы можем использовать (Int, Int, Int) для представления секции дороги или вектора в трёхмерном пространстве и оперировать таким представлением, но тут не исключена путаница. А вот если использовать типы данных Section и Vector , мы не сможем случайно сложить вектор с секцией дорожной системы.

Теперь дорожная система между Хитроу и Лондоном может быть представлена так:

heathrowToLondon :: RoadSystem

heathrowToLondon = [ Section 50 10 30

                   , Section 5 90 20

                   , Section 40 2 25

                   , Section 10 8 0

                   ]

Всё, что нам осталось сделать, – разработать решение на языке Haskell.

 

Реализация функции поиска оптимального пути

Какой может быть декларация типа для функции, вычисляющей кратчайший путь для дорожной системы? Она должна принимать дорожную систему как параметр и возвращать путь. Мы будем представлять путь в виде списка. Давайте определим тип Label, который может принимать три фиксированных значения: A, B или C. Также создадим синоним типа – Path.

data Label = A | B | C deriving (Show)

type Path = [(Label, Int)]

Наша функция, назовём её optimalPath, будет иметь такую декларацию типа:

optimalPath :: RoadSystem –> Path

Если вызвать её с дорожной системой heathrowToLondon, она должна вернуть следующий путь:

[(B,10),(C,30),(A,5),(C,20),(B,2),(B,8)]

Мы собираемся пройти по списку секций слева направо и сохранять оптимальные пути по A и B по мере обхода списка. Будем накапливать лучшие пути по мере обхода списка – слева направо… На что это похоже? Тук-тук-тук! Правильно, левая свёртка!

При решении задачи вручную был один шаг, который мы повторяли раз за разом. Мы проверяли оптимальные пути по A и B на текущий момент и текущую секцию, чтобы найти новый оптимальный путь по A и B. Например, вначале оптимальные пути по A и B равны, соответственно, [] и []. Мы проверяем секцию Section 50 10 30 и решаем, что новый оптимальный путь до A1 – это [(B,10),(C,30)]; оптимальный путь до B1 – это [(B,10)]. Если посмотреть на этот шаг как на функцию, она принимает пару путей и секцию и возвращает новую пару путей. Тип функции такой: (Path, Path) –> Section –> (Path, Path). Давайте её реализуем – похоже, она нам пригодится.

Подсказка: функция будет нам полезна, потому что её можно использовать в качестве бинарной функции в левой свёртке; тип любой такой функции должен быть a –> b –> a.

roadStep :: (Path, Path) –> Section –> (Path, Path)

roadStep (pathA, pathB) (Section a b c) =

   let timeA = sum $ map snd pathA

       timeB = sum $ map snd pathB

       forwardTimeToA = timeA + a

       crossTimeToA = timeB + b + c

       forwardTimeToB = timeB + b

       crossTimeToB = timeA + a + c

       newPathToA = if forwardTimeToA <= crossTimeToA

                       then (A,a):pathA

                       else (C,c):(B,b):pathB

       newPathToB = if forwardTimeToB <= crossTimeToB

                       then (B,b):pathB

                       else (C,c):(A,a):pathA

   in (newPathToA, newPathToB)

Как это работает? Для начала вычисляем оптимальное время по дороге A, основываясь на текущем лучшем маршруте; то же самое для B. Мы выполняем sum $ map snd pathA, так что если pathA – это что-то вроде [(A,100),(C,20)], timeA станет равным 120.

forwardTimeToA – это время, которое мы потратили бы, если бы ехали до следующего перекрёстка по A от предыдущего перекрёстка на A напрямую. Оно равно лучшему времени по дороге A плюс длительность по A текущей секции.

crossTimeToA – это время, которое мы потратили бы, если бы ехали до следующего перекрёстка на A по B, а затем повернули бы на A. Оно равно лучшему времени по B плюс длительность B в текущей секции плюс длительность секции C.

Таким же образом вычисляем forwardTimeToB и crossTimeToB. Теперь, когда мы знаем лучший путь до A и B, нам нужно создать новые пути до A и B с учетом этой информации. Если выгоднее ехать до A просто напрямую, мы устанавливаем newPathToA равным (A,a): pathA. Подставляем метку A и длину секции a к началу текущего оптимального пути. Мы полагаем, что лучший путь до следующего перекрёстка по A – это путь до предыдущего перекрёстка по A плюс ещё одна секция по A. Запомните, A – это просто метка, в то время как a имеет тип Int. Для чего мы подставляем их к началу, вместо того чтобы написать pathA ++ [(A,a)]? Добавление элемента к началу списка (также называемое конструированием списка) работает значительно быстрее, чем добавление к концу. Это означает, что получающийся путь будет накапливаться в обратном порядке, по мере выполнения свёртки с нашей функцией, но нам легче будет обратить список впоследствии, чем переделать формирование списка. Если выгоднее ехать до следующего перекрёстка по A, двигаясь по B и поворачивая на A, то newPathToA будет старым путём до B плюс секция до перекрёстка по B и переезд на A. Далее мы делаем то же самое для newPathToB, но в зеркальном отражении.

Рано или поздно мы получим пару из newPathToA и newPathToB.

Запустим функцию на первой секции heathrowToLondon. Поскольку эта секция первая, лучшие пути по A и B будут пустыми списками.

ghci> roadStep ([], []) (head heathrowToLondon)

([(C,30),(B,10)],[(B,10)])

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

ПРИМЕЧАНИЕ. Подсказка для оптимизации: когда мы выполняем timeA = sum $ map snd pathA , мы заново вычисляем время пути на каждом шаге. Нам не пришлось бы делать этого, если бы мы реализовали функцию roadStep так, чтобы она принимала и возвращала лучшее время по A и по B вместе с соответствующими путями.

Теперь у нас есть функция, которая принимает пару путей и секцию, а также вычисляет новый оптимальный путь, так что мы легко можем выполнить левую свёртку по списку секций. Функция roadStep вызывается со значением в качестве аккумулятора ([],[]) и первой секцией, а возвращает пару оптимальных путей до этой секции. Затем она вызывается с этой парой путей и следующей секцией и т. д. Когда мы прошли по всем секциям, у нас остаётся пара оптимальных путей; кратчайший из них и будет являться решением задачи. Принимая это во внимание, мы можем реализовать функцию optimalPath.

optimalPath :: RoadSystem –> Path

optimalPath roadSystem =

   let (bestAPath, bestBPath) = foldl roadStep ([],[]) roadSystem

   in if sum (map snd bestAPath) <= sum (map snd bestBPath)

         then reverse bestAPath

         else reverse bestBPath

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

Проведём тест:

ghci> optimalPath heathrowToLondon

[(B,10),(C,30),(A,5),(C,20),(B,2),(B,8),(C,0)]

Это практически тот результат, который мы ожидали получить. Чудесно. Он слегка отличается от ожидаемого, так как в конце пути есть шаг (C,0), который означает, что мы переехали на другую дорогу, как только попали в Лондон; но поскольку этот переезд ничего не стоит, результат остаётся верным.

 

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

Итак, у нас есть функция, которая находит оптимальный путь по заданной системе дорог. Теперь нам надо считать текстовое представление дорожной системы со стандартного ввода, преобразовать его в тип RoadSystem, пропустить его через функцию optimalPath, после чего напечатать путь.

Для начала напишем функцию, которая принимает список и разбивает его на группы одинакового размера. Назовём её groupsOf. Если передать в качестве параметра [1..10], то groupsOf 3 должна вернуть [[1,2,3],[4,5,6],[7,8,9],[10]].

groupsOf :: Int –> [a] –> [[a]]

groupsOf 0 _ = undefined

groupsOf _ [] = []

groupsOf n xs = take n xs : groupsOf n (drop n xs)

Обычная рекурсивная функция. Для xs равного [1..10] и n = 3, получаем [1,2,3] :groupsOf 3 [4,5,6,7,8,9,10]. После завершения рекурсии мы получаем наш список, сгруппированный по три элемента. Теперь напишем главную функцию, которая считывает данные со стандартного входа, создаёт RoadSystem из считанных данных и печатает кратчайший путь:

import Data.List

main = do

   contents <– getContents

   let threes = groupsOf 3 (map read $ lines contents)

       roadSystem = map (\[a,b,c] –> Section a b c) threes

       path = optimalPath roadSystem

       pathString = concat $ map (show . fst) path

       pathTime = sum $ map snd path

   putStrLn $ "Лучший путь: " ++ pathString

   putStrLn $ "Время: " ++ show pathTime

Вначале получаем данные со стандартного входа. Затем вызываем функцию lines с полученными данными, чтобы преобразовать строку вида "50\n10\n30\n… в список ["50","10","30"…, и функцию map read, чтобы преобразовать строки из списка в числа. Вызываем функцию groupsOf 3, чтобы получить список списков длиной 3. Применяем анонимную функцию (\[a,b,c] –> Section a b c) к полученному списку списков. Как мы видим, данная анонимная функция принимает список из трёх элементов и превращает его в секцию. В итоге roadSystem содержит систему дорог и имеет правильный тип, а именно RoadSystem (или [Section]). Далее мы вызываем функцию optimalPath, получаем путь и общее время в удобной текстовой форме, и распечатываем их.

Сохраним следующий текст:

50

10

30

5

90

20

40

2

25

10

8

0

в файле paths.txt и затем «скормим» его нашей программе.

$ ./heathrow < paths.txt

Лучший путь: BCACBBC

Время: 75

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

Можете использовать модуль Data.Random, чтобы сгенерировать более длинные системы дорог и «скормить» их только что написанной программе. Если вы получите переполнение стека, попытайтесь использовать функцию foldl' вместо foldl и foldl' (+) 0 вместо sum. Можно также скомпилировать программу следующим образом:

$ ghc -0 heathrow.hs

Указание флага 0 включает оптимизацию, которая предотвращает переполнение стека в таких функциях, как foldl и sum.