and red = blend(15,0,0)

and blue = blend(0,15,0)

and yellow = blend(0,0,15)

fun mix (parts:int, blend(r,b,y),

parts:int, blend(x,y,z)) = if parts<0 orelse parts<0 then white else let val tp = parts+parts

and rp = (parts*r+parts*r) div tp and bp = (parts*b+parts*b) div tp and yp = (parts*y+parts*y) div tp in blend(rp,bp,yp) end;

>type color

val white = - : color val red = - : color val blue = - : color val yellow = - : color

val mix = fn : int*color*int*color->color

-val green = mix(2, yellow, 1, blue);

>val green = - : color

-val black = mix (1, red, 2, mix(l, blue, 1, yellow));

>val black = - : color

Мы должны сделать несколько замечаний относительно приведенного примера. То, что идет после слова abstype, является рекурсивным определением типа (и здесь используется тот же самый синтаксис). Эта часть есть определение типа реализации. Далее идет описание интерфейса, заключенное в синтаксические скобки with и end. В выдаче ML мы видим, что после слова color нет знака равенства; это отражает тот факт, что color - это новый тип, не совпадающий ни с каким другим. Но в отличие от рекурсивного определения типа, в результате выполнения abstype не создано никаких конструкторов: это делает невозможным создание новых значений типа color иначе, как путем использования значений и функций интерфейса. Это обеспечивает высокую степень изоляции программы, использующей абстрактный тип данных, от его определения. Заметьте то, что функции, определенные внутри with, все же имеют доступ к типу реализации и его конструкторам - иначе бы этот тип был бесполезным!

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

Итак, имеется три способа определения новых типов в ML. Прозрачные определения предназначены для сокращенной записи сложных типовых выражений; их задача - повысить читабельность текста программы, а не создание новых типов как таковых. Рекурсивные типы обеспечивают расширение системы типов ML. Объявление рекурсивного типа вводит новый конструктор типа и некоторый набор конструкторов значений этого типа. Рекурсивное определение типа подходит для сложных структур данных (как, например, деревья), внутренняя структура которых должна быть доступна программе. Если же важным является только поведение значений нового типа (как, например, в случае стека или очереди), более подходящим является определение абстрактного типа, структура реализации которого невидима для использующей абстрактный тип программы, и может использоваться только функциями, определяющими поведение данных.

Упражнение 2.7.2 Абстрактный тип set может быть определен как:

abstype a set = set of a list with val emptyset: a set = ...

fun singleton(e: a ): a set = ... fun union(sl: a set, s2: a set): a set = ... fun member(e: a, s: a set) : bool = ... I member(e, set(h::t)) = (e=h)

orelse member(e, set t) fun intersection (si: a set, s2: a set): a set = ...

Завершите определение этого абстрактного типа данных.

Упражнение 2.7.3 Модифицируйте свое решение так, чтобы элементы множества хранились в виде упорядоченного списка. (Подсказка: Один из путей решения состоит в том, чтобы передавать отношение порядка (т.е. функцию типа a*a->bool в качестве дополнительного параметра каждой функции. Другой путь состоит в том, чтобы отношение порядка передавать только тем функциям, которые строят множества из исходных элементов - с тем, чтобы они вставляли его в представление множества. Тогда, например, функция построения объединения могла бы извлечь отношение порядка из своих аргументов и использовать его для построения результата. Мы вернемся к этой проблеме позже, когда будем в состоянии предложить более элегантный механизм параметризации такого сорта).

2.8 Исключения

Предположим, что мы хотим написать функцию head, вырабатывающую первый элемент списка-аргумента. Первый элемент непустого списка легко получить путем сопоставления с образцом, но что должна возвращать head, если ее аргумент есть nil? Ясно, что что-то нужно сделать, - ведь head должна быть определена для всех значений аргумента, в том числе и для nil, - но что именно нужно делать, не очень понятно. Возвращать какое-либо стандартное значение не очень хорошо по двум причинам: во-первых, непонятно, какое же значение выбрать стандартным, а, во-вторых, это ограничит область определения функции: например, если мы положим head (nil) равным nil, то функция head будет применима только к спискам списков).

Для того, чтобы можно было описать разумное поведение программы в подобных случаях, ML предлагает механизм обработки исключительных событий. Целью этого механизма является предоставление функции возможности завершить работу изящным и не нарушающим правила согласования типов способом в тех ситуациях, когда она не может или не хочет возвратить результат. Например, функцию head можно было бы записать следующим способом:

-exception Head;

>exception Head

-fun head(nil) = raise Head

I head(x::y) = x;

>val head = fn : a list -> a

-head [1,2,3] ;

>1 : int

-head nil; Failure: Head

Первая строка является привязкой к исключению (исключительному значению): она объявляет, что идентификатор Head является именем исключения. Функция head определяется обычным способом путем разбора случаев. В случае непустого списка значение функции head есть просто первый элемент списка. Но в случае nil функция head не в состоянии вернуть какое-либо разумное значение, поэтому она возбуждает исключение. Результат этого виден в следующих за определением head строках: в ответ на применение head к nil выводится сообщение Failure: Head, показывающее, что вычисление выражения head (nil) привело к тому, что было возбуждено исключение Head. Напомним, что попытка деления на 0 приводит к аналогичному результату, и это не случайно: во встроенной функции div при попытке деления на 0 возбуждается исключение Div.