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

                       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