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

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

data Node = Node Road Road | EndNode Road

data Road = Road Int Node

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

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

data Node = Node Road (Maybe Road)

data Road = Road Int Node

Можно решить задачу, пользуясь таким способом представления дорожной системы; но нельзя ли придумать что-нибудь попроще? Если вспомнить решение задачи в уме, мы всегда проверяли длины трёх отрезков дороги: отрезок по дороге A, отрезок по дороге B и отрезок C, который их соединяет. Когда мы искали кратчайший путь к пунктам A1 и B1, то рассматривали длины первых трёх частей, которые были равны 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.