Главная » Haskell » Типы данных

0

Язык Haskell обладает достаточно развитой системой типов, в которую включены не только сами типы данных, но и некоторые другие механизмы, позволяющие работать с типами. Более того, из-за принятой в языке модели типизации (статическая модель Хиндли-Милнера) в трансляторах  имеется мощнейший механизм  вывода типов, который  позволяет самостоятельно вычислять типы  выражений, функций и других объектов. Этот механизм в  дополнение нагружен системой классов, которые могут рассматриваться в качестве ограничений и интерфейсов. Всем этим аспектам языка посвящена эта и следующая главы.

Базовые типы

Как  и любой другой развитый язык программирования, язык Haskell имеет некоторое множество так называемых «базовых типов», или встроенных типов данных, которые не определены где-либо в загрузочных модулях, но внедрены глубоко внутрь трансляторов. Обычно такие встроенные типы данных используются для представления фундаментальных  величин: чисел, символов и прочих сходных объектов. Такие объекты обычно сложно описать во внешних модулях, тем более, что обычно они имеют прямое отображение в систему хранения данных на аппаратном уровне, — именно этим и объясняется подобное положение вещей.

Однако если во многих языках программирования встроенные  типы охватывают довольно большое количество описанных объектов (булевские значения; символы, целые числа простой, двойной, четверной точности; также числа с плавающей точкой нескольких типов точности и даже строки), то язык Haskell отличается в этом вопросе некоторой аскетичностью. Дело в том, что в нём определено всего пять базовых типов, а именно (в алфавитном порядке):

1)                        Char — тип для представления литералов, занимающих в памяти один байт (восемь бит), символьный тип.

2)                        Double — тип для представления десятичных чисел с плавающей  точкой двойной точности (значения типа Double занимают в два раза больше места в памяти, чем значения типа Float).

3)                        Float — тип для представления десятичных чисел с плавающей точкой.

4)                        Int  —   тип   для  представления целых  чисел,  входящих  в   интервал

[-2147483648,   2147483647] ([?231, 231 ? 1]).

5)                        Integer — тип для представления целых чисел любой величины  (вплоть до бесконечности).

Остальные типы данных можно получить из перечисленных при помощи операций конструирования  типов (при этом создаются так  называемые алгебраические типы данных), применения определённых разработчиком конструкторов типов и создания изоморфных типов данных.

Однако в целях оптимизации вычислительных процессов и способов хранения данных в языке Haskell на достаточно глубоком уровне «зашиты» два типа, которые базовыми не являются, но имеют некоторые преимущества (и ограничения) по сравнению с  произвольными алгебраическими типами данных, которые  могут создаваться программистом. Эти типы — список и кортеж. Их и необходимо рассмотреть в первую очередь.

2.1.1.    Кортежи

В математике  кортежом  называется  упорядоченный набор из n  элементов (где n — любое натуральное  число), называемое его компонентами. Различные (то есть стоящие на разных местах в одном и том же кортеже) компоненты могут

между собой и совпадать. Часто синонимом термина «кортеж» является термин

«вектор», что связано с наиболее естественной интерпретацией кортежа как точек n-мерного пространства или упорядоченных  совокупностей их координат. Посредством кортежей удобно характеризовать объекты, описываемые при помощи n независимых друг от друга признаков.

Это понятие довольно широко используется в математике, поэтому в языке Haskell понятие кортежа нашло непосредственную реализацию в системе типов и структур  данных. К сожалению, как  будет показано далее, в языке  Haskell нет возможности сделать список, состоящий из элементов разных типов, как это, к примеру, можно сделать в языке Lisp. Это довольно существенное ограничение, которое не позволяет использовать такие значение, как, например, [1, ’a’]. Однако возможность объединения разнотиповых элементов данных в одну структуру дают именно кортежи, которые в языке Haskell имеют тождественное с математическим определение.  Кортеж  выглядит как некоторый набор значений, заключённых в круглые скобки и разделённых запятыми. Например:

(14,  ’r’,  [9,  6, 5])

Представленный выше кортеж состоит из трёх значений  — целого числа, символа и списка целых чисел. Такие кортежи сами  являются самостоятельными элементами данных, которые передаются в вычислительные процессы как одно целое. Хотя, в принципе, их использование в языке Haskell не так необходимо, как это может показаться на первый взгляд. Вполне возможно написать программу и без использования кортежей вовсе. Одно из главных назначений кортежей — написание некаррированных  функций.

В  стандартном модуле Prelude  имеются некоторые функции  для работы с кортежами.  В первую очередь к этим функциям  относятся такие функции, как fst и snd (подробно описаны на стр. 136 и стр. 163 соответственно),  которые принимают на вход кортеж, состоящий из двух элементов любого типа. Первая функция возвращает первый элемент кортежа, вторая — второй.

Что же  касается  типов кортежей,  то они определяются очень  просто. Для любого кортежа, состоящего из n членов, типом будет  считаться кортеж из n членов, на каждой позиции которого стоит тип элемента данных на соответствующей позиции исходного кортежа. В качестве примеров можно привести следующие кортежи:

1)                        (1, 1)  :: (Num  a,  Num  b)  => (a, b)

2)                        (14::Int, ’n’) :: (Int, Char)

3)                        ("Hello",  "World") :: (String, String)

4)                        ([1, 1,  2,  3,  5], ["Fibonacci"], True)  :: Num  a => ([a],  [String],  Bool)

5)                        (fst, snd)  :: ((a, b)  ->  a,  (c, d)  ->  d)

С математической точки зрения общая формула для вычисления типа кортежа записывается следующим образом:

#(a1, a2, . . . , an) : (#a1, #a2, . . . , #an)

Естественно, для вычисления типов кортежей в языке Haskell используется тот же механизм, что и для вычисления типов прочих структур данных и функций (механизм, основанный на модели  типизации Хиндли-Милнера), а потому выводимый тип будет наиболее общим. Это видно на первом примере, где имеется контекст (Num  a,  Num  b)  =>, который обозначает, что типы a и b принадлежат классу числовых величин Num.

2.1.2.    Списки

Традиционно списки являются основной структурой данных, которая обрабатывается при помощи функциональных языков программирования. Эта ситуация сложилась из-за того, что в первом  таком языке  —  Lisp —  списки были той структурой данных, при  помощи которой  описывалось  вообще всё, вплоть до самих программ на этом языке.

В языке Haskell используется реализация списков, максимально приближенная математическому  определению. Определение типа «список над элементами типа a» на языке Haskell выглядит следующим образом (синтаксис для определения структур данных описывается в разделе 2.2.):

data  [a]

= []

| a:[a]

Данное определение в целях оптимизации обычно встроено в глубины трансляторов языка  Haskell (поэтому оно некорректно с точки  зрения синтаксиса

языка, а приведено исключительно в целях понимания). Тем не  менее основные функции и экземпляры классов для типа  «список» всегда определяются вне транслятора во внешних библиотеках или модулях. Например, в стандартном модуле Prelude, который автоматически импортируется во все проекты и модули, определены функции для доступа к элементам списка и для проверки списков на пустоту (данные функции подробно описываются на стр. 251 и стр. 393):

head  ::  [a]  -> a head  (x:_)  = x

tail  ::  [a]  ->  [a] tail  (_:xs)  = xs

null ::  [a] ->  Bool null []        =  True null  (_:_) =  False

На самом деле в связи с тем, что в русском языке имеется некоторая двусмысленность слова «список», далее рассматриваются  аспекты применения списков именно как типа, а не как элемента данных. Это значение подразумевает лишь тот факт, что структура  данных «список» имеет тип «список над элементами типа a». Поэтому в языке Haskell нотация с квадратными скобками используется как в записи типов выражений, так и в записи структур данных.

Определение  типа данных, приведённое  выше, предполагает,  что в языке Haskell в списке могут находиться только значения одного типа — a. Это может быть совершенно любой тип, даже другой список. Но факт остаётся фактом, такой гибкости и даже волюнтаризма в определении списка, которые наблюдаются в языке Lisp, в языке Haskell нет. Для группировки значений разных типов в одну структуру данных необходимо использовать рассмотренные ранее кортежи.

Математическая формула для определения типа структуры данных, являющейся списком, выглядит следующим образом:

#[a1, a2, . . . , an] : [A]

где A = #a1  = #a2  = . . . = #an.

Остаётся отметить, что кортежи и списки в языке Haskell могли бы стать универсальным средством для организации любых структур данных, как это сделано в языке Lisp, в котором списки по своей сути являются некоторым слиянием

возможностей кортежей и списков в единый формализм. Однако этого не произошло, и в языке Haskell имеются достаточно серьёзные инструменты для создания сложных типов вроде структур, перечислений и объектов.

Источник: Душкин Р. В., Справочник по языку Haskell. М.: ДМК Пресс, 2008. 544 с., ил.

По теме:

  • Комментарии