Учебник по Haskell - [23]
тивов, я имел ввиду, что некоторые конструкторы по сути являются константами, а другие функциями.
Эти “методы” определяют базовые значения типа, все другие значения будут комбинациями базовых.
При этом сумма типов, определяет число методов “классе” типа, то есть число базовых значений, а произ-
ведение типов в каждой альтернативе определяет имя метода (именем конструктора) и состав аргументов
(перечислением подтипов).
3.2 Структура констант
Мы уже знаем, что значения могут быть функциями и константами. Объявляя константу, мы даём имя-
синоним некоторой комбинации базовых конструкторов. В функции мы говорим как по одним значениям
получить другие. В этом и следующем разделе мы посмотрим на то, как типы определяют структуру констант
и функций.
Давайте присмотримся к константам:
Succ (Succ Zero)
Neg (Add One (Mul Six Ten))
Not (Follows A (And A B))
Cons 1 (Cons 2 (Cons 3 (Cons 4 Nil)))
Заменим все функциональные конструкторы на букву f (от слова function), а все примитивные конструк-
торы на букву c (от слова constant).
f (f c)
f (f c (f c c))
f (f c (f c c))
f c (f c (f c (f c c)))
Те кто знаком с теорией графов, возможно уже узнали в этой записи строчную запись дерева. Все зна-
чения в Haskell являются деревьями. Узел дерева содержит составной конструктор, а лист дерева содержит
примитивный конструктор. Далее будет небольшой подраздел посвящённый терминологии теории графов,
которая нам понадобится, будет много картинок, если вам это известно, то вы можете спокойно его пропу-
стить.
Структура констант | 41
Несколько слов о теории графов
Если вы не знакомы с теорией графов, то сейчас как раз самое время с ней познакомится, хотя бы на
уровне основных терминов. Теория графов изучает дискретные объекты в терминах зависимостей между
объектами или связей. При этом объекты и связи можно изобразить графически.
Граф состоит из узлов и рёбер, которые соединяют узлы. Приведём пример графа:
8
7
c
f
6
a
b
d
e
5
1
2
g
h
3
4
Рис. 3.1: Граф
В этом графе восемь узлов, они пронумерованы, и восемь рёбер, они обозначены буквами. Теорию графов
придумал Леонард Эйлер, когда решал задачу о кёнингсбергских мостах. Он решал задачу о том, можно ли
обойти все семь кёнингсбергских мостов так, чтобы пройти по каждому лишь один раз. Эйлер представил
мосты в виде рёбер а участки суши в виде узлов графа и показал, что это сделать нельзя. Но мы отвлеклись.
А что такое дерево? Дерево это такой связанный граф, у которого нет циклов. Несвязанный граф образует
несколько островков, или множеств узлов, которые не соединены рёбрами. Циклы – это замкнутые последо-
вательности рёбер. Например граф на рисунке выше не является деревом, но если мы сотрём ребро e, то у
нас получится дерево.
Ориентированный граф – это такой граф, у которого все рёбра являются стрелками, они ориентированы,
отсюда и название. При этом теперь каждое ребро не просто связывает узлы, но имеет начало и конец. В ори-
ентированных деревьях обычно выделяют один узел, который называют корнем. Его особенность заключается
в том, что все стрелки в ориентированном дереве как бы “разбегаются” от корня или сбегаются к корню. Ко-
рень определяет все стрелки в дереве. Ориентированное дерево похоже на иерархию. У нас есть корневой
элемент и набор его дочерних поддеревьев, каждое из поддеревьев в свою очередь является ориентирован-
ным деревом и так далее. Проиллюстрируем на картинке, давайте сотрём ребро e и назначим первый узел
корнем. Все наши стрелки будут идти от корня. Сначала мы проведём стрелки к узлам связанным с корнем:
Затем представим, что каждый из этих узлов сам является корнем в своём дереве и повторим эту процеду-
ру. На этом шаге мы дорисовываем стрелки в поддеревьях, которые находятся в узлах 3 и 6. Узел 5 является
вырожденным деревом, в нём всего лишь одна вершина. Мы будем называть такие поддеревья листьями.
А невырожденные поддеревья мы будем называть узлами. Корневой узел в данном поддереве называют ро-
дительским. А его соседние узлы, в которые направлены исходящие из него стрелки называют дочерними
узлами. На предыдущем шаге у нас появился один родительский узел 1, у которого три дочерних узла: 3, 6,
и 5. А на этом шаге у нас появились ещё два родительских узла 3 и 6. У узла 3 один дочерний узел (4), а у
узла 6 – три дочерних узла (2, 8, 7).
Отметим, что положение узлов и рёбер на картинке не важно, главное это то, какие рёбра какие узлы
соединяют. Мы можем перерисовать это дерево в более привычном виде (рис. 3.4).
Теперь если вы посмотрите на константы в Haskell вы заметите, что очень похожи на деревья. Листья со-
держат примитивные конструкторы, а узлы – составные. Это происходит из-за того, что каждый конструктор
содержит метку и набор подтипов. В этой аналогии метки становятся узлами, а подтипы-аргументы стано-
вятся поддеревьями.
42 | Глава 3: Типы
8
7
c
f
6
a
b
d
5
1
2
g
h
3
4
Рис. 3.2: Превращаем в дерево
8
7
c
f
6
a
b
d
5
1
2
g
h
3
4
Рис. 3.3: Превращаем в дерево...
Но есть одна тонкость, в которой заключается отличие констант Haskell от деревьев из теории графов. В
теории графов порядок поддеревьев не важен, мы могли бы нарисовать поддеревья в любом порядке, главное
В книге кратко изложены ответы на основные вопросы темы «Уголовное право. Особенная часть». Издание поможет систематизировать знания, полученные на лекциях и семинарах, подготовиться к сдаче экзамена или зачета.Пособие адресовано студентам высших и средних образовательных учреждений, а также всем интересующимся данной тематикой.
В книге кратко изложены ответы на основные вопросы темы «Уголовно-исполнительное право». Издание поможет систематизировать знания, полученные на лекциях и семинарах, подготовиться к сдаче экзамена или зачета.Пособие адресовано студентам высших и средних образовательных учреждений, а также всем интересующимся данной тематикой.
Книга посвящена возможностям самого популярного средства цифрового видеомонтажа – Adobe Premiere 6.5. Описываются основные приемы работы с программой, приводятся сведения об управлении проектами и клипами, обсуждаются методы монтажа видео и звука, техника создания титров и добавления спецэффектов, а также освещается процесс окончательного монтирования фильма. На примерах рассматриваются все этапы создания и обработки фильмов для телевидения, видео и мультимедиа.Для широкого круга пользователей.
В учебном пособии в краткой и доступной форме рассмотрены все основные вопросы, предусмотренные государственным образовательным стандартом и учебной программой по дисциплине «Финансовое право».Книга позволит быстро получить основные знания по предмету, а также качественно подготовиться к зачету и экзамену.Рекомендуется студентам, аспирантам и преподавателям по юридическим, экономическим и управленческим специальностям, а также сотрудникам банков.Автор книги, Шевчук Денис Александрович, имеет опыт преподавания различных дисциплин в ведущих ВУЗах Москвы (экономические, юридические, технические, гуманитарные), два высших образования (экономическое и юридическое), более 30 публикаций (статьи и книги), Член Союза Юристов Москвы, Член Союза Журналистов России, Член Союза Журналистов Москвы, Стипендиат Правительства РФ, опыт работы в банках, коммерческих и государственных структурах (в т.ч.
Содержащиеся в пособии контрольно-измерительные материалы (КИМы) для 5 класса, аналогичные материалам ЕГЭ, составлены в соответствии с программой общеобразовательных учреждений по русскому языку и учитывают возрастные особенности учащихся. В конце пособия даны ответы на все варианты тестов, предложены диктанты различных типов.Пособие адресовано учителям, ученикам, их родителям и всем, кому необходимо закрепить и систематизировать знания перед ЕГЭ.
Цель предлагаемого пособия – систематизировать и обогатить представления о природе, структуре и особенностях художественной литературы как вида искусства, помочь совершенствованию читательского мастерства. Книга снабжена кратким словарем основных литературоведческих понятий и терминов (составлен при участии доцента О.В. Быстровой).Для студентов филологических факультетов, учителей, преподавателей литературы высших и средних учебных заведений.