Изучай Haskell во имя добра! - Миран Липовача

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

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 из считанных данных и печатает кратчайший путь: