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

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.