Получение описания дорожной системы из внешнего источника

Итак, у нас есть функция, которая находит оптимальный путь по заданной системе дорог. Теперь нам надо считать текстовое представление дорожной системы со стандартного ввода, преобразовать его в тип 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 10 30 … в список ["50","10","30"…, и функцию map read, чтобы преобразовать строки из списка в числа. Вызываем функцию groupsOf 3, чтобы получить список списков длиной 3. Применяем анонимную функцию ([a,b,c] –> Section a b c) к полученному списку списков. Как мы видим, данная анонимная функция принимает список из трёх элементов и превращает его в секцию. В итоге roadSystem содержит систему дорог и имеет правильный тип, а именно RoadSystem (или [Section]). Далее мы вызываем функцию optimalPath, получаем путь и общее время в удобной текстовой форме, и распечатываем их.

Сохраним следующий текст:

в файле paths.txt и затем «скормим» его нашей программе.

$ ./heathrow < paths.txt

Лучший путь: BCACBBC

Время: 75

Отлично работает!

Можете использовать модуль Data.Random, чтобы сгенерировать более длинные системы дорог и «скормить» их только что написанной программе. Если вы получите переполнение стека, попытайтесь использовать функцию foldl' вместо foldl и foldl' (+) 0 вместо sum. Можно также скомпилировать программу следующим образом:

$ ghc -0 heathrow.hs

Указание флага 0 включает оптимизацию, которая предотвращает переполнение стека в таких функциях, как foldl и sum.