Проведём тест:
>ghci> optimalPath heathrowToLondon
>[(B,10),(C,30),(A,5),(C,20),(B,2),(B,8),(C,0)]
Это практически тот результат, который мы ожидали получить. Чудесно. Он слегка отличается от ожидаемого, так как в конце пути есть шаг >(C,0), который означает, что мы переехали на другую дорогу, как только попали в Лондон; но поскольку этот переезд ничего не стоит, результат остаётся верным.
Получение описания дорожной системы из внешнего источника
Итак, у нас есть функция, которая находит оптимальный путь по заданной системе дорог. Теперь нам надо считать текстовое представление дорожной системы со стандартного ввода, преобразовать его в тип >RoadSystem, пропустить его через функцию >optimalPath, после чего напечатать путь.
Для начала напишем функцию, которая принимает список и разбивает его на группы одинакового размера. Назовём её >groupsOf. Если передать в качестве параметра >[1..10], то >groupsOf 3 должна вернуть >[[1,2,3],[4,5,6],[7,8,9],[10]].
>groupsOf :: Int –> [a] –> [[a]]
>groupsOf 0 _ = undefined
>groupsOf _ [] = []
>groupsOf n xs = take n xs : groupsOf n (drop n xs)
Обычная рекурсивная функция. Для >xs равного >[1..10] и >n = 3, получаем >[1,2,3] :groupsOf 3 [4,5,6,7,8,9,10]. После завершения рекурсии мы получаем наш список, сгруппированный по три элемента. Теперь напишем главную функцию, которая считывает данные со стандартного входа, создаёт >RoadSystem из считанных данных и печатает кратчайший путь:
>import Data.List
>main = do
> contents <– getContents
> let threes = groupsOf 3 (map read $ lines contents)
> roadSystem = map (\[a,b,c] –> Section a b c) threes
> path = optimalPath roadSystem
> pathString = concat $ map (show . fst) path
> pathTime = sum $ map snd path
> putStrLn $ "Лучший путь: " ++ pathString
> putStrLn $ "Время: " ++ show pathTime
Вначале получаем данные со стандартного входа. Затем вызываем функцию >lines с полученными данными, чтобы преобразовать строку вида >"50\n10\n30\n… в список >["50","10","30"…, и функцию >map read, чтобы преобразовать строки из списка в числа. Вызываем функцию >groupsOf 3, чтобы получить список списков длиной >3. Применяем анонимную функцию >(\[a,b,c] –> Section a b c) к полученному списку списков. Как мы видим, данная анонимная функция принимает список из трёх элементов и превращает его в секцию. В итоге >roadSystem содержит систему дорог и имеет правильный тип, а именно >RoadSystem (или >[Section]). Далее мы вызываем функцию >optimalPath, получаем путь и общее время в удобной текстовой форме, и распечатываем их.
Сохраним следующий текст: