Миран Липовача - Изучай 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

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вместе с соответствующими путями.