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

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

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

 

0

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

$./heathrow < paths.txt Лучший путь: BCACBBC Время: 75

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

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

$ ghc -O heathrow.hs

Указание флага O включает оптимизацию, которая предотвра- щает переполнение стека в таких функциях, как 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) внут- ри». Она применяет функцию к элементу внутри коробки.

Мы также можем воспринимать значения функторов как значе- ния с добавочным контекстом. Например, значения типа Maybe об- ладают дополнительным контекстом того, что вычисления могли окончиться неуспешно. По отношению к спискам контекстом яв- ляется то, что значение может быть множественным либо отсутс- твовать. Функция fmap применяет функцию к значению, сохраняя его контекст.

Если мы хотим сделать конструктор типа экземпляром класса Functor, он должен иметь сорт * –> *; это значит, что он принимает ровно один конкретный тип в качестве параметра типа. Например, конструктор Maybe может быть сделан экземпляром, так как он по- лучает один параметр типа для произведения конкретного типа, как, например, Maybe Int или Maybe String. Если конструктор типа принимает два параметра, как, например, конструктор Either, мы должны частично применять конструктор типа до тех пор, пока он не будет принимать только один параметр. Поэтому мы не можем написать определение Functor Either where, зато можем написать определение Functor (Either a) where. Затем, если бы мы вообрази- ли, что функция fmap предназначена только для работы со значени- ями типа Either a, она имела бы следующее описание типа:

fmap:: (b –> c) –> Either a b –> Either a c

 

Как видите, часть Either a – фиксированная, потому что час- тично применённый конструктор типа Either a принимает только один параметр типа.