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

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