Изучай Haskell во имя добра! (Липовача) - страница 171
>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 (это список секций), указывая в качестве начального значения аккумулятора пару пустых путей. Результат свёртки – пара путей, так что нам потребуется сопоставление с образцом, чтобы добраться до самих путей. Затем мы проверяем, который из двух путей короче, и возвращаем его. Прежде чем вернуть путь, мы его обращаем, так как мы накапливали оптимальный путь, добавляя элементы в начало.