Представление пути на языке Haskell

Следующий наш шаг: как представить дорожную систему в системе типов языка Haskell? Один из способов – считать начальные точки и перекрёстки узлами графа, которые ведут к другим перекрёсткам. Если мы представим, что начальные точки связаны друг с другом до- рогой единичной длины, мы увидим, что каждый перекрёсток (или узел графа) указывает на узел на противоположной стороне, а также на следующий узел с той же стороны. За исключением последних узлов они просто показывают на противоположную сторону.

data Node = Node Road Road | EndNode Road

 

data Road = Road Int Node

Узел – это либо обычный узел, указывающий путь до противо- положной дороги и путь до следующего узла по той же дороге, либо конечный узел, который содержит информацию только о проти- воположной дороге. Дорога хранит информацию о длине отрезка и об узле, к которому она ведёт. Например, первая часть дороги А будет представлена как Road 50 a1, где a1 равно Node x y; при этом x и y – дороги, которые ведут к B1 и A2.

Мы могли бы использовать тип Maybe для определения данных

Road, которые указывают путь по той же дороге. Все узлы содержат

 

путь до параллельной дороги, но только те узлы, которые не явля- ются конечными, содержат пути, ведущие вперёд.

data Node = Node Road (Maybe Road) data Road = Road Int Node

Можно решить задачу, пользуясь таким способом представле- ния дорожной системы; но нельзя ли придумать что-нибудь поп- роще? Если вспомнить решение задачи в уме, мы всегда прове- ряли длины трёх отрезков дороги: отрезок по дороге А, отрезок по дороге В и отрезок С, который их соединяет. Когда мы искали кратчайший путь к пунктам А1 и В1, то рассматривали длины пер- вых трёх частей, которые были равны 50, 10 и 30. Этот участок сети дорог назовём секцией. Таким образом, дорожная система в нашем примере легко может быть представлена в виде четырёх секций: (50, 10, 30), (5, 90, 20), (40, 2, 25) и (10, 8, 0).

Всегда лучше делать типы данных настолько простыми, на- сколько это возможно – но не проще!

data Section = Section { getA:: Int, getB:: Int, getC:: Int } deriving (Show)

 

type RoadSystem = [Section]

Так гораздо ближе к идеалу! Записывается довольно просто, и у меня есть предчувствие, что для решения нашей задачи такое описание подойдёт отлично. Секция представлена обычным алгеб- раическим типом данных, который содержит три целых числа для представления длин трёх отрезков пути. Также мы определили си- ноним типа, который говорит, что RoadSystem представляет собой список секций.

ПРИМЕЧАНИЕ. Для представления секции дороги мы могли бы использовать кортеж из трёх целых чисел: (Int, Int, Int). Кортежи вместо алгебраических типов данных лучше применять для реше- ния маленьких локальных задач, но в таких случаях, как наш, лучше создать новый тип. Это даёт системе типов больше информации о том, что есть что. Мы можем использовать (Int, Int, Int) для пред- ставления секции дороги или вектора в трёхмерном пространстве и оперировать таким представлением, но тут не исключена пута- ница. А вот если использовать типы данных Section и Vector, мы не сможем случайно сложить вектор с секцией дорожной системы.

Теперь дорожная система между Хитроу и Лондоном может быть представлена так:

heathrowToLondon:: RoadSystem heathrowToLondon = [ Section 50 10 30

, Section 5 90 20

, Section 40 2 25

, Section 10 8 0

]

Всё, что нам осталось сделать, – разработать решение на языке Haskell.