Изучай Haskell во имя добра!

ПРИМЕЧАНИЕ. Как можно заметить, функция не устойчива к ошибкам. Если передать ей бессмысленный вход, она вывалится с ошибкой. Мы сделаем её устойчивой к ошибкам, определив её тип как 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 минут). Поможет ли нам это, если нужно узнать кратчайший путь до следующего перекрёстка? Представьте себе, да!