Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Представление пути на языке 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.
|
|||||||||||||||||||||||
Последнее изменение этой страницы: 2017-02-17; просмотров: 165; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.226.126.38 (0.014 с.) |