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

[(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, получаем путь и общее время в удобной текстовой форме, и распечатываем их.

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

50

10

30

5

90

20

40

2

25

10

8

0

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

$ ./heathrow < paths.txt

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

Время: 75

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

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

$ ghc -0 heathrow.hs

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

11 Аппликативные функторы

Сочетание чистоты, функций высшего порядка, параметризованных алгебраических типов данных и классов типов в языке Haskell делает реализацию полиморфизма более простой, чем в других языках. Нам не нужно думать о типах, принадлежащих к большой иерархии. Вместо этого мы изучаем, как могут действовать типы, а затем связываем их с помощью подходящих классов типов. Тип Int может вести себя как множество сущностей – сравниваемая сущность, упорядочиваемая сущность, перечислимая сущность и т. д.

Классы типов открыты – это означает, что мы можем определить собственный тип данных, обдумать, как он может действовать, и связать его с классами типов, которые определяют его поведение. Также можно ввести новый класс типов, а затем сделать уже существующие типы его экземплярами. По этой причине и благодаря прекрасной системе типов языка Haskell, которая позволяет нам знать многое о функции только по её объявлению типа, мы можем определять классы типов, которые описывают очень общее, абстрактное поведение.