Миран Липовача - Изучай Haskell во имя добра!

Теперь у нас есть функция, которая принимает пару путей и секцию, а также вычисляет новый оптимальный путь, так что мы легко можем выполнить левую свёртку по списку секций. Функция 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

[(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.

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

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

Мы говорили о классах типов, которые определяют операции для проверки двух элементов на равенство и для сравнения двух элементов по размещению их в каком-либо порядке. Это очень абстрактное и элегантное поведение, хотя мы не воспринимаем его как нечто особенное, поскольку нам доводилось наблюдать его большую часть нашей жизни. В главе 7 были введены функторы – они являются типами, значения которых можно отобразить. Это пример полезного и всё ещё довольно абстрактного свойства, которое могут описать классы типов. В этой главе мы ближе познакомимся с функторами, а также с немного более сильными и более полезными их версиями, которые называются аппликативными функторами .

Как вы узнали из главы 7, функторы – это сущности, которые можно отобразить, как, например, списки, значения типа Maybeи деревья. В языке Haskell они описываются классом типов Functor, содержащим только один метод fmap. Функция fmapимеет тип fmap :: (a –> b) –> f a –> f b, который говорит: «Дайте мне функцию, которая принимает aи возвращает bи коробку, где содержится a(или несколько a), и я верну коробку с b(или несколькими b) внутри». Она применяет функцию к элементу внутри коробки.