[
Содержание
| 1
| 2
| 3
| 4
| 5
| 5.1
| 5.2
| 5.3
| 5.4
| 5.5
| 5.6
| 5.7
| 5.8
| 5.9
| 6
| 6.1
| 6.2
| 6.3
| 6.4
| 6.5
| 7
| 7.1
| Литература
]
© 2003 И.А. Дехтяренко
7.1. Типы в ML
Разработанный в середине 1970-х годов язык ML
прошел с тех пор значительный путь развития,
заимствуя многие идеи из других языков и
порождая множество диалектов. Предпринятая в 1980-х
попытка стандартизации привела к созданию языка
Standard ML (или SML), который в свою очередь продолжает
развиваться и порождать диалекты. Во всех
современных инкарнациях ML достаточно большой
и сложный язык, но нас будет интересовать пржде
всего то что прославило ML - его система типов.
Практически все реализации ML являются
интерактивными; они основываются на хорошо
знакомом диалоге типа
"прочесть-вычислить-напечатать". В процессе
такого диалога пользователь вводит выражение,
ML-система его анализирует, компилирует,
выполняет и выдает результат на терминал. (Конечно,
можно создавать и независимые программы, но для
изучения языка интерактивный режим -
непревзойденное средство.)
1+2;
val it = 3 : int
Как видно, значение выражения выдается вместе с
его типом. Смысл текста "val it =" прояснится в
дальнейшем, пока его можно читать как
"значение введенного выражения равно".
Простые выражения удобно вводить прямо в
командной строке, более сложные примеры -
загружать командой use.
use "myprogram";
Результат действия этой команды точно такой же,
как если бы текст, находящийся в "myprogram" был
введен непосредственно.
Выражения строятся из идентификаторов (имен) и
(специальных) констант с применением
зарезервированных слов, которым в частности
относятся скобки, запятые и т.п. Каждое правильно
построенное выражение имеет некоторый тип,
определяемый его структурой.
Идентификаторы бывают двух видов: одни
начинаются с буквы и состоят из букв, цифр и
знаков "_" и "'", другие целиком
состоят из специальных символов. Разумеется,
зарезервированные слова не могут использоваться
в качестве имен. Поскольку идентификаторы просто
именуют другие объекты, собственного типа они не
имеют. Тип идентификатора совпадает с тип
обозначаемого им объекта.
Специальные константы относятся к одному из атомарных
типов.
Тип unit состоит из единственной константы ().
Этот тип используется в тех случаях, когда
выражение не имеет какого либо осмысленного
значения, а также вместо аргумента функции в тех
случаях, когда функция не должна иметь
аргументов.
Тип bool состоит из констант true и false,
выражающих логические значения.
Числовые типы int и real призваны
представлять целые и действительные числа
(реально - машинные целые и числа с плавающей
точкой). Числа записываются более-менее обычным
для языков программирования способом, за
исключением того, что для отрицательных чисел
знак записывается тильдой ~ вместо традиционного
минуса. В записи действительного числа должна
присутствовать десятичная точка или знак
экспоненты "Е". ML не обеспечивает включения
одного типа в другой и целые константы должны
отличаться от действительных. (Кроме
"обычных" целых существуют и более
машинно-ориентированные типы, но мы их
рассматривать не будем).
10;
val it = 10 : int
0x10;
val it = 16 : int
10.0;
val it = 10.0 : real
Строки образуют тип string, и записываются
как последовательности литер, заключенные в
двойные кавычки. Для записи строк, содержащих
"небычные" символы применяется нотация,
сходная с употребляемой в Си.
"Hello";
val it = "Hello" : string
"a"
val it = "a" : string
Отдельные литеры представляются константами
типа char и записываются как одноэлементные
строки, предваренные символом "#".
#"a";
val it = #"a" : char
Составные типы содержат выражения, которые
строятся из выражений других типов. Каждый
составной тип имеет собственное имя, отражающее
правило построения выражений этого типа. К
базовым составным типам относятся кортежи,
записи, списки и функции.
Кортежи - последовательность
выражений, отделенных друг от друга запятыми,
заключается в круглые скобки. Если выражения
e1,e2,...,en имеют типы T1,T2,...,Tn соответственно,
выражение (e1,e2,...,en) имеет типом T1*T2*...*Tn. Частным
случаем кортежей являются пары - кортежи из двух
элементов. Обратите внимание что выражения (a,b,c)
(a,(b,c)) ((a,b),c) имеют разные типы. Это может
показаться очевидным, но некоторые языки не
делают такого различия, используя изоморфизм
множеств (A*B)*C и A*(B*C).
Записи - последовательности равенств
вида l = e (где l - метка, а e -выражение), заключенные
в фигурные скобки. Записи в ML аналогичны записям
в Паскале, структурам в Си и т.д. Каждое равенство
l = e устанавливает значение поля, помеченного
меткой l = e , равным значению выражения e. Порядок
равенств, задающих запись, не имеет значения.
Типом записи {l1 = e1, l2 = e2,...,ln = en} является {l1: T1, l2:
T2,..., ln:Tn}.
Метками могут служить идентификаторы и целые
числа. Если все метки в записи - последовательные
числа от 1 до n, то такая запись ничем не
отличается от кортежа. Можно считать, что кортежи
это просто синтаксический сахар для
определенного класса записей: кортеж (e1,e2,...,en)
является сокращенным для записи {1 = e1, 2 = e2,..., n = en}.
{1=1,2=2};
val it = (1, 2) : int * int
Списки - конечные последовательности
выражений одного типа разделенных запятыми и
заключенные в квадратные скобки. Список [e1,e2,...,en],
где все ei типа T имеет тип T list. Выражения,
напоминающие списки, но содержащие элементы
разных типов, не являются правильными.
[1,2,3,4,5];
val it = [1, 2, 3, 4, 5] : int list
[1,true];
Error:
Can't unify bool with int (Different type constructors)
Думаю, никого не удивит, что запись в квадратных
скобках считается всего лишь сокращением полной
формы записи списков, которая строится с
применением конструкторов nil и ::
(обычно произносится как "конс" в память о
лисповской функции cons).
1::2::nil;
val it = [1, 2] : int list
Предопределенные функции.
Простейшими выражениями функционального типа
являются имена предопределенных функций.
Функция, получающая значение типа A и
возвращающая значение типа B имеет тип A
-> B.
not;
val it = fn : bool -> bool
chr;
val it = fn : int -> char
ord;
val it = fn : char -> int
Функции не имеют никакого внешнего
представления, вместо значения печатается fn.
Применения функции к аргументу записывается как
два выражения одно за другим. Значением первого
выражения должна являться функция, а значением
второго - ее аргумент. Исключение из этого
правила - функции определенные как инфиксные
операторы, такие как обычные арифметические
операции и операции сравнения.
~ 1;
val it = ~1 : int
not true;
val it = false : bool
1+2*3;
val it = 7 : int
Очевидно если функция, f имеет тип A -> B, а
выражение e - тип A, то выражение (f e) имеет тип B.
Попытка применения функции к аргументу другого
типа отвергается во время компиляции.
not 1;
Error:
Can't unify bool with int (Different type constructors)
Для чисел предопределены обычные
арифметические операции (+, -, *, div и mod для целых; -,
+, -, *, / для действительных) и операции сравнения
(<, <=, >, >=, = и <>). Необычно только
обозначение "~" для операции взятия
противоположного числа.
op +;
val it = fn : int * int -> int
Этот пример достоин нескольких замечаний:
- Символ "+" имеет статус инфиксного
оператора и должен употребляться в контексте A+B.
Ключевое слово op отменяет этот статус и
позволяет нам ссылаться на функцию как таковую.
Лобой идентификатор может быть объявлен как
инфиксный лево-,право- или не-ассоциативный
оператор посредством объявлений infix, infixr
и nonfix .
- Все функции являются функциями одного
аргумента; при необходимости использовать
функции (содержательно) нескольких аргументов
они обычно "упаковываются" в один кортеж.
Другой подход, использование карринга.
- Функция "+" перегружена, а правильнее
сказать, имя "+" перегружено и обозначает две
разные функции сложения целых и действительных
чисел. По умолчанию берется первая из них, но в
другом контексте может использоваться и вторая.
Из первых двух замечаний следует, что
применение сложения можно записать и в таком
виде.
op+ (1,2);
val it = 3 : int
Приоритеты инфиксных операторов достаточно
привычны, а вот остальные функции доставляют
неудобства новичкам. Применение функции
левоассоциативно, то есть f g h означает (f g) h, а не f
(g h). Например выражение (~ ~ 1) приведет к ошибке,
поскольку означает применение функции ~ к
функции ~, а затем результата этого выражения к 1
что, конечно, не имеет смысла. Правильной записью
будет (~ (~ 1)).
Функция real преобразует целый аргумент в
соответствующее действительное число (это
преобразование всегда производится явно).
Обратное преобразование осуществляется
функциями floor, ceil и round. Обратите
внимание, что имя функции real совпадает с
именем типа real. Это не общее правило
приведения типов, как в Си, а еще один вид
перегрузки имен. Один и тот же идентификатор
может независимо именовать даже совершенно
несвязанные между собой объекты разных
категорий: значения, типы, поля, модули.
Для работы со значениями логического типа
имеются одноместная операция not и две
двухместных операции andalso и orelse,
соответствующие обычным логическим связкам
"не", "и", "или". Несколько
неожиданные названия andalso и orelse вместо более
традиционных and и or призваны подчеркнуть особый
характер вычисления этих операций. В
терминологии Лиспа они являются "специальными
формами", точно так же, как и условные
выражения, записываемые в виде if e1 then e2 else e3.
Условные выражения также должны быть правильно
типизированными - выражение e1, должно иметь
тип bool, а типы выражений e2 и e3 должны
совпадать. Значение условного выражения имеет
тот же тип, что и e2 (и e3).
Типы char и string относительно
независимы. Хотя содержательно строки состоят из
отдельных литер, в системе типов это не отражено.
Для того, чтобы превратить литеру в строку
необходимо явно применить функцию str.
Функция explode отображает строку в список
составляющих ее литер, обратное преобразование
выполняет функция implode.
explode "string";
val it = [#"s", #"t", #"r", #"i", #"n", #"g"] : char list
Длину строки можно узнать с помощью функции size.
Функция ^ является инфиксной двухместной
операцией конкатенации строк.
"Hello " ^ "world!";
val it = "Hello world!" : string
Перегрузка операций сравнения
распространяется и на эти типы. Как обычно,
литеры упорядочены по их кодам, а строки -
лексикографически.
Сравнение на равенство (и неравенство)
распространяется на записи и кортежи. Но для
этого сравниваемые выражения должны
удовлетворять определенным условиям. Во-первых,
они должны быть одного типа. Во-вторых, все их
элементы должны допускать сравнение на
равенство. Может показаться, что второе условие
выполняется автоматически, поскольку все
атомарные типы можно сравнивать. (Для
сомневающихся: значения типа unit также можно
сравнивать и это, пожалуй, единственное, что с
ними можно делать). Проблема в том, что элементами
могут быть и функции, а вот их как раз сравнивать
и нельзя. Это ограничение вполне разумно,
единственное осмысленное равенство для функций -
экстенсиональное равенство, а его установление
задача, алгоритмически неразрешимая.
Специальное обозначение предусмотрено для
выделения одного поля из записи или кортежа: поле
name записи r может быть обозначено как #name. Для
кортежей, естественно, вместо имени поля
используется номер элемента.
#1 (1,2);
val it = 1 : int
Заметим, что #1 - вовсе не функция, хотя
все выражение выглядит как применение функции.
Конструкция (#name R) имеет смысл только в
определенном контексте, когда известна
структура записи R. Чтобы осознать это,
попытайтесь вывести тип "функции" #1.
Функции на списках - превосходный повод
познакомится с концепцией полиморфизма в ML.
Начнем с самого простого. Функция length
вычисляет длину списка, причем любого списка.
length [1,2,3];
val it = 3 : int
length ["a","b"];
val it = 2 : int
Каков будет ее тип? Тип результата понятен - это
int, а вот что собой представляет тип аргумента?
Очевидно, он должен включать в себя и int list и bool
list, и (string* int list) list. Спросим у системы.
length;
val it = fn : 'a list -> int
Выражение 'a list означает "список
элементов любого типа". Идентификатор 'a
(произносится как "альфа", поскольку в
теоретических работах типы принято обозначать
греческими буквами) - типовая переменная,
вместо которой можно подставить любой тип,
получая подходящий тип аргумента для length.
Функция hd возвращает первый элемент списка
hd;
val it = fn : 'a list -> 'a
Здесь типовая переменная встречается в двух
местах и каждое вхождение 'a должно быть
заменено одним и тем же типом. То есть функция hd
получает в качестве аргумента произвольный
список и возвращает результат, тип которого
совпадает с типом элементов списка. У Функции tl
тип результата тот же, что и тип аргумента.
tl;
val it = fn : 'a list -> 'a list
- Упражнение.
- Инфиксный оператор @ выполняет соединение
списков. Определите его тип.
Определите типы конструкторов :: и nil.
На время отвлечемся от списков и рассмотрим еще
одну полиморфную Функцию - операцию композиции
функций, обозначаемую "o".
~ o op +;
val it = fn : int * int -> int
Результат выражения (~ o op +) композиция
функций ~ и +, то есть функция,
вычисляющая сумму двух чисел, а затем изменяющая
ее знак.
(~ o op +) (1,2);
val it = ~3 : int
Посмотрим на тип функции "o".
op o;
val it = fn : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b
Он содержит три типовых переменных: 'a ,'b и 'c.
Вместо каждой из них можно подставить любой тип.
Общая структура типа функции обеспечивает
типовую согласованность аргументов и результата
в соответствии с общепринятыми правилами.
Например, тип аргумента первого операнда должен
совпадать с типом результата второго.
Попробуем угадать, какой тип имеет функция map.
Она имеет два аргумента, функцию и список и
возвращает список, полученный применением
функции к каждому элементу списка. Отсюда
заключаем, что тип элементов списка-аргумента
должен совпадать с типом аргумента функции, а тип
элементов списка-результата должен совпадать с
типом ее значений. Логично предположить, что тип
функции map:
('a -> 'b) * 'a list -> 'b list
Мы почти угадали. Действительно, map могла бы
иметь такой тип. Но на самом деле
map;
val it = fn : ('a -> 'b) -> 'a list -> 'b list
map получает в качестве аргумента функцию типа ('a
-> 'b) и возвращает другую функцию, преобразующую
список элементов типа 'a в список элементов типа
'b. Это позволяет легко записывать "частичное
применение" map.
map ~;
val it = fn : int list -> int list
map ~ [1,2,3];
val it = [~1, ~2, ~3] : int list
Подобным образом определены и функции свертки.
foldr;
val it = fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
foldl;
val it = fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b
Отношение равенства определено и для списков:
два списка равны, если они состоят из одного и
того же числа элементов и соответствующие
элементы равны между собой. Как и в случае
записей, невозможно сравнение двух списков с
элементами разных типов, попытка выполнить такую
операцию приведет к ошибке в согласовании типов.
Таким образом, равенство распространяется на
большой класс типов. Это делает функцию "="
похожей на полиморфные функции. Но это не
настоящий полиморфизм и тому имеются две
причины. Во-первых, алгоритмы вычисления для
разных типов различны, то есть имеет место
перегрузка функции. Во-вторых, аргументы могут
быть не любого типа, а только типа, допускающего
сравнение на равенство. Если мы поинтересуемся
типом "=", получим.
op =;
val it = fn : ''a * ''a -> bool
Особый сорт типовых переменных ''a,
представляет типы, допускающие проверку на
равенство. ML позволяет использовать равенство
"квазиполиморфным" способом. Компилятор
следит за тем, требуется или нет, чтобы какой-либо
тип допускал проверку на равенство, и отражает
этот факт в выведенных типах. Например, тип
выражения (map op =) : (''a * ''a) list -> bool list.
Функциональные выражения
Для конструирования новых функций часто
применяются функциональные выражения,
аналогичные тем, что встречались в Лиспе и в
Эрланге. Результатом вычисления выражения (fn х
=> e) является функция, которая преобразует
аргумент x в значение выражения e. Эту функцию мы
можем применять к аргументу непосредственно или
передать в качестве аргумента другой функции.
Тип функции выводится из типа выражения e (иногда
это нетривиальная задача!).
fn x => x*x;
val it = fn : int -> int
(fn x => x*x) 2;
val it = 4 : int
map (fn x => x*x) [1,2,3];
val it = [1, 4, 9] : int list
Передача аргументов функции осуществляется
путем сопоставления с образцом:
fn (x,y) => (y,x);
val it = fn : 'a * 'b -> 'b * 'a
(fn (x,y) => (y,x)) (1,2);
val it = (2, 1) : int * int
Правила для различных случаев образцов
разделяются вертикальной чертой:
(fn nil => nil | h::t => t) [1,2,3];
val it = [2, 3] : int list
Все образцы в пределах одного функционального
выражения должны иметь один и тот же тип, так же
как и все правые части правил. Это правило
несколько ослабляется возможностью
использования полиморфных типов, но в таком
случае должен существовать общий тип для всех
правил.
fn (1,x) => 1 | (x,1) => 2 | (x,y) => 3;
val it = fn : int * int -> int
В этом примере три правила имеют типы
int * 'a -> int
'a * int -> int
'a * 'b -> int
Система выводит наиболее общий тип выражения: int
* int -> int.
В некоторых случаях приходится явно указывать
типы аргументов.
fn (x,y) => x+y;
val it = fn : int * int -> int
По умолчанию использована целочисленная
функция сложения. Но, возможно, мы имели в виду
сложение действительных чисел. Чтобы избежать
неоднозначности, мы должны указать это явно.
fn (x:real, y:real) => x+y;
val it = fn : real * real -> real
Другой способ сделать то же самое - указать тип
результата.
fn (x,y)=> x+y :real;
val it = fn : real * real -> real
Вообще, любое выражение в ML может
сопровождаться указанием типа. Такое указание
позволяет убедиться в правильности наших
предположений о типе значения и может служить
средством документирования.
Сопоставление с образцом для записей делается
с помощью помеченных полей.
fn {name=n, value=x} => n;
val it = fn : {name: 'a, value: 'b} -> 'a
Иногда удобно выполнить частичное
сопоставление записи с образцом. Для этого
применяются универсальные образцы для записей:
(fn {name=n,...} => n) {name="Name", value=1, check=true};
val it = "Name" : string
При использовании универсального образца для
записей полный тип записи должен определяться на
этапе компиляции по контексту, в который входит
образец. Это ограничение определяется правилами
типизации аналогично тому, которое налагается на
использование селекторов полей. На самом деле #name
является не более чем сокращенным
обозначением для функции fn {name=n,...} => n,
выделяющей поле name.
Сопоставля структуру, можно одновременно
назначать имена и ее частям и структуре целиком.
(fn a as (b,c) => (a,b,c))(1,2);
val it = ((1, 2), 1, 2) : (int * int) * int * int
Еще одно средство для работы с образцами
оператор case
fn a => case a+1 of
1 => "one"
| 2 => "two"
| _ => "other";
val it = fn : int -> string
Универсальный образец, или "джокер",
обозначаемый знаком "_", избавляет от
необходимости выдумывать имена, которые в
дальнейшем все равно не будут использоваться.
Объявления
Каждое имя должно быть объявлено перед
использованием. Имена встроенных функций
считаются объявленными заранее. С некоторыми
способами объявления мы уже имели дело,
используя имена полей записи и аргументов
функций.
Фраза вида (val x = e) называется привязкой
переменной к значению. ML вычисляет значение
выражения e и присваивает его переменной x.
Впрочем, это еще вопрос - что чему присваивается.
С не меньшим основанием мы можем сказать, что имя
x присваивается значению выражения e.
val x=1;
val x = 1 : int
x;
val it = 1 : int
Обратите внимание, что выдача результата
привязки слегка отличается от приводившихся
ранее. Вместо "val it =" перед
значением печатается "val х =". По
соглашению считается, что ввод на верхнем уровне
диалога выражения e является сокращением для "val it = e".
Это позволяет ссылаться на результат последнего
вычисления по имени "it". Привязки ведут себя
подобно определяющим формам define в Лиспе:
повторная привязка того же имени перекрывает
предыдущую.
С помощью ключевого слова and можно
привязать к значениям сразу несколько
идентификаторовю. При выполнении таких привязок,
сначала вычисляются их правые части, а затем уже
имена привязываются к полученным значениям.
val x=1 and y=2;
val x = 1 : int
val y = 2 : int
val x=y and y=x;
val x = 2 : int
val y = 1 : int
В левой части равенства можно использовать и
образцы.
val (x,y) = (1,2);
val x = 1 : int
val y = 2 : int
val (x,y) = (y,x);
val x = 2 : int
val y = 1 : int
Привязывая имена к функциональным выражениям,
мы можем давать имена новым функциям.
val sqr = fn x=>x*x;
val sqr = fn : int -> int
sqr 2;
val it = 4 : int
Но таким образом нельзя описывать рекурсивные
функции. У нас нет способа вызвать функцию,
определяемую функциональным выражениям из этого
выражения. Такую возможность предоставляет
ключевое слово rec.
val rec fact =
fn n => if n=1 then 1 else n* fact (n-1);
val fact = fn : int -> int
Некоторая доля синтаксического сахара -
конструкция fun, определяющая функцию и
одновременно дающая ей имя.
fun sqr x = x*x;
val sqr = fn : int -> int
fun fact n = if n=1 then 1 else n* fact (n-1);
val fact = fn : int -> int
Можно записывать функции и в виде
последовательности правил, разделяемых "|".
При этом имя функции повторяется внутри каждого
правила.
fun fact 1 = 1
| fact n = n* fact (n-1);
val fact = fn : int -> int
Важная особенность конструкции fun,
оправдывющая ее введение то, что она позволяет
наглядно записывать определения функций,
возвращающих функции, например
fun map f nil = nil
| map f (x::xs) = f(x) :: map f xs;
вместо более громоздкого
val rec map =а f = fn nil => nil
| (x::xs) => f(x) :: map f xs;
Часто полезно иметь возможность объявлять
локальные имена, роль которых состоит только в
том, чтобы облегчить построение выражений или
других объявлений. Конструкция let позволяет
вводить локальные имена при вычислении
выражений.
let val x = 10 in x*x end;
val it = 100 : int
Привязка x = 10 действует только между ключевыми
словами in и end.
fun reverse l =
let fun rev(nil, y) = у
| rev(x::xs, y) = rev(xs, x::y);
in
rev(l, nil)
end;
val reverse = fn : 'a list -> 'a list
Здесь let используется для объявления
локальной функции rev.
Сходная с let конструкция local
применяется для объявлений.
local
val pi=3.141592654;
in
fun perimeter r = 2.0 * pi * r
fun area r = pi * r * r
end;
val area = fn : real -> real
val perimeter = fn : real -> real
Вспомогательное имя pi использовано для
объявления двух функций, но сама привязка
невидима за пределами in ... end.
Определения типов
Имеется три формы объявления идентификатора
как нового имени типа. Простейшая из них -
прозрачная привязка имени к типу. По сути, она
означает введение сокращенного наименования для
некоторого (как правило более сложного) типового
выражения.
type intpair = int*int;
type intpair
type intlist = int list;
type intlist
Все использования определенного таким образом
типа полностью эквивалентны использованию
вместо него исходного выражения.
fun fst (x : intpair) = #1 x;
val fst = fn : intpair -> int
fun sum (l : intlist) = foldl op+ 0 l ;
val sum = fn : intlist -> int
Нет никакой разницы между intpair и int*int,
также как и между intlist и int list.
Единственная причина, по которой ML печатает
указывает эти имена в типах функций fst и sum
- эти типы были явно указаны при объявлении
функций.
Конструкторы типов могут иметь параметры,
определяя полиморфные типы.
type 'a pair_list = ('a * 'a) list;
type 'a pair_list
type int_pair_list= int pairlist;
type int_pair_list
Алгебраические типы
Действительно новые типы создаются
конструкцией datatype. В ней указывается имя
нового типа (возможно, с параметрами) и набор
конструкторов значений для построения объектов
этого типа. Такие определения типов называются
алгебраическими. Условно их можно разделить по
степени сложности.
Перечислимые типы подобны
перечислимые типам Паскаля.
datatype color = red | blue | yellow;
datatype color = blue | red | yellow
Это объявление назначает имя color новому
типу данных и одновременно, объявляет три новых
конструктора (red, blue и yellow) которые в данном
случае обычно называют константами.
red;
val it = red : color
Заметим, что встроенный тип bool можно считать
объявленым как:
datatype bool = true | false;
Вариантные типы. Определяемые
пользователем конструкторы значений могут иметь
аргументы. В этом случае получаются структуры,
подобные вариантным записям Паскаля.
datatype Shape = Point
| Circle of real
| Rectangle of real * real;
Вновь определенный тип Shape имеет три
конструктора, первый из которых является
константой, а два остальных имеют аргументы.
Point;
val it = Point : Shape
Circle ;
val it = fn : real -> Shape
Rectangle;
val it = fn : real * real -> Shape
С их помощью и создаются объекты типа Shape.
Circle 2.3;
val it = Circle 2.3 : Shape
Функции, обрабатывающие значения этого типа
удобно определять путем разбора случаев. При
этом конструкторы значений могут быть
использованы в образцах.
fun area Point=0.0
| area (Circle r)= 3.141592654*r*r
| area (Rectangle (a,b)) = a*b;
val area = fn : Shape -> real
ML автоматически выводит тип функции. Более
того, если мы забудем учесть какой либо вариант,
он предупредит нас об этом.
fun area Point=0.0
| area (Circle r)= 3.14*r*r ;
Warning:
Matches are not exhaustive.
Found near fun area(Point) = 0.0 | area(...(...)) = *( ...)
val area = fn : Shape -> real
Крайний случай - определение типа содержит
только один вариант.
datatype IntPair = pair of int*int;
В отличие от определения через type, здесь
определяется новый тип элементы которого
создаются только с помощью конструктора pair.
pair (1,2);
val it = pair (1, 2) : IntPair
Вновь создаваемые типы могут быть и
полиморфными. Например, мы можем обобщить IntPair.
datatype ('a, 'b) Pair = pair of 'a* 'b;
Элементы типа Pair подобны обычным парам и
могут использоваться аналогично. Причиной для
введения такого типа может оказаться желание
отличать их от обычных пар.
pair (1,2);
val it = pair (1, 2) : (int, int) Pair
pair (true,"true");
val it = pair (true, "true") : (bool, string) Pair
Выражение "элементы типа Pair" не
вполне точно. Имеется множество типов вида 'a
'b Pair. Поэтому полиморфные типы вроде Pair
называют конструкторами типов: они создают новые
типы из других типов подобно тому, как
конструкторы значений строит новые значение из
других значений.
Более интересные примеры: "разделенное
объединение"
datatype ('a , 'b) Oneof = first of 'a | second of 'b ;
и полезный частный случай:
datatype 'a Maybe = nothing | some of 'a;
nothing ;
val it = nothing : 'a Maybe
some 1;
val it = some 1 : int Maybe
some [1,2,3];
val it = some [1, 2, 3] : int list Maybe
Полезность Maybe может показаться
сомнительной, но подобные конструкции часто
применяются для работы с "неопределеннымы"
или "неправыльнымы" значениями. Вот
простенький пример
fun mb f nothing = nothing
| mb f (some x) = some (f x);
val mb = fn : ('a -> 'b) -> 'a Maybe -> 'b Maybe
fun good x = if x>32 andalso x<127 then some x else nothing;
val good = fn : int -> int Maybe
map (mb chr) (map good [0,16,32,48,64,80,96,132]);
val it =
[nothing, nothing, nothing, some #"0", some #"@", some #"P",
some #"`", nothing] : char Maybe list
Обратите внимание на функцию mb. Она
преобразует произвольную функцию в функцию
выполняющую ту же операцию, но для элементов типа
Maybe и таким образом позволяет легко
использовать уже готовые функции.
Если среди аргументов конструкторов
встречается определяемый тип, говорят о рекурсивных
типах. Например, можно считать, что
предопределенный тип list объявлен следующим
образом:
datatype 'a list = nil' | :: of 'a * 'a list;
Это наиболее сложный, но одновременно и
наиболее мощный способ определять типы. Без
рекурсии мы не смогли бы приписывать типы
сложным структурам данных, таким как двоичные
деревья или просто деревья.
datatype 'a btree = Empty | Node of 'a * 'a btree * 'a btree
datatype 'a tree = tree of 'a * 'a list;
Абстрактные типы
Третий способ определения типов - абстрактные
типы. Они призваны заставить программистов
соблюдать соглашения абстракции данных.
Абстрактный тип данных представляет собой
некоторый алгебраический тип, называемый типом
реализации, и набор интерфейсных функций для
работы с данными этого типа.
Рассмотрим определение абстрактного типа
«множество».
abstype ''a set = set of ''a list
with
val empty = set []
fun singleton e = set [e]
fun member(e, set []) = false
| member(e, set(h::t)) = (e=h) orelse member(e, set t)
fun join (set s, e) =
if member (e,set s) then set s else set (e::s)
fun union (set [], s) = s
| union (set(h::t), s) = union (set t, join (s,h))
end;
type ''a set
val empty = ? : ''a set
val join = fn : ''a set * ''a -> ''a set
val member = fn : ''a * ''a set -> bool
val singleton = fn : ''a -> ''a set
val union = fn : ''a set * ''a set -> ''a set
Непосредственно после слова abstype идет
определение типа реализации. Далее между with и end
описываются интерфейсные функции. Констуктор
типа реализации set недоступен вне
определения типа, поэтому тип реализации может
быть изменен в любой момент, и это никак не
скажется на программе, использующей абстрактный
тип данных.
set [1];
Error:
Value or constructor (set) has not been declared
singleton 1;
val it = ? : int set
Хотя абстракция данных - важное средство
структуирования программ, конструкция abstype
используется довольно редко и даже признана
устаревшей. Гораздо более мощным инструментом
оказываются модули.
Заметим, что подобного сокрытия представления
можно добится и другими средствами
local
datatype ''a set = set of ''a list
in
val empty = set []
fun singleton e = set [e]
...
end;
Можно сказать, что разница между двумя
способами определеня состоит в том, что local
скрывает имя конструктора, в то время как abstype
скрывает сам конструктор. Практически это
означает, что абстрактный тип не допускает
проверку на равенство. Почему - ясно из нашего
примера. Одно и то же множество может быть
представлено разными списками. Если необходимо
сравнивать объекты абстрактного типа, нужно
определить соответствующую интерфейсную
функцию.
[
Содержание
| 1
| 2
| 3
| 4
| 5
| 5.1
| 5.2
| 5.3
| 5.4
| 5.5
| 5.6
| 5.7
| 5.8
| 5.9
| 6
| 6.1
| 6.2
| 6.3
| 6.4
| 6.5
| 7
| 7.1
| Литература
]
|