con note: int->money

con check: string*int->money

-fun amount(nomoney) = 0

I amount(coin(pence)) = pence

I amount(note(pounds)) = 100*pounds

I amount(check(bank,pence)) = pence;

>val amount = fn : money -> int

Тип money имеет четыре конструктора, первый из которых является константой, а три остальных имеют аргументы. Функция amount, определенная разбором случаев с использованием этих конструкторов, возвращает сумму в пенсах, представленную объектом типа money.

А что можно сказать по поводу равенства для определенных пользователем рекурсивных типов? Напомним определение равенства для списков: два списка равны тогда и только тогда, когда они либо оба есть nil, либо имеют форму h: :t и h: :t соответственно, и h равно h и t равно t. В общем случае, два значения некоторого рекурсивного типа равны, если они "построены одним и тем же способом" (т.е. на верхнем уровне использованы один и тот же конструктор) и соответствующие компоненты равны между собой. Как следствие такого определения равенства, мы получаем, что определенный пользователем рекурсивный тип данных допускает проверку на равенство тогда и только тогда, когда все аргументы всех конструкторов значений имеют типы, допускающие проверку на равенство. В рассмотренном примере тип money допускает проверку на равенство, поскольку типы int и string допускают ее.

-nomoney = nomoney;

>true : bool

-nomoney = coin(5);

>false : bool

-coin(5) = coin(2+3);

>true : bool

-check("TSB",500) <> check("Clydesdale",500);

>true : bool

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

-datatype btree = empty I leaf I node of btree*btree;

>type btree

con empty: btree con leaf: btree

13B конце концов, не зря же мы его так назвали! (Прим. перев.)

con node : btree*btree->btree

-fun countleaves (empty) = 0

I countleaves (leaf) = 1

I countleaves (node(treel,tree2)) =

countleaves(treel) + countleaves(tree2);

>val countleaves = fn : btree->int

Обратите внимание на то, что рекурсивное определение типа btree следует неформальному определению двоичного дерева. Функция countleaves является рекурсивной функцией, определенной на двоичных деревьях; она подсчитывает количество листьев дерева. Важно отметить, что функция, определенная на рекурсивных данных, является рекурсивной14. Определение функции append, рассмотренное ранее, демонстрирует этот факт. Это не случайно, поскольку можно считать, что предопределенный тип т list объявлен следующим образом15:

-datatype a list = nil I :: of а * a list;

>type a list

con nil : a list

con :: : (a * (a list)) -> (a list)

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

Приведем другой пример рекурсивного типа с параметром:

-datatype a tree = empty I leaf of a I

node of a tree * a tree;

>type a tree

con empty : a tree

con leaf: a -> a tree

con node : a tree * a tree -> a tree

-fun frontier( empty ) = []

I frontier( leaf(x) ) = [x] I frontier ( node(tl,t2) ) =

append(frontier(tl), frontier(t2));

14Это не формальное, а содержательное утверждение. Конечно, мы можем определить функцию с аргументом типа btree как fun f (empty) = 1 I f (leaf) = 2 I f (node ( , )) = 3, и здесь нет никакой рекурсии. Однако все содержательно интересные функции, определенные на рекурсивных типах данных, за редчайшим исключением будут рекурсивными. (Прим. перев.)

18 В этом примере мы игнорируем тот факт, что для конструктора : : используется инфиксная форма записи: это не касается сути рассматриваемого вопроса.

>val frontier = fn : a tree -> a list

-val tree = node(leaf("a"), node(leaf("b"), leaf("c")));

>val tree = node(leaf("a"), node (leaf("b"), leaf("c")))

: string tree

-frontier tree;

>[»a","b","c"] : string list

Функция frontier получает в качестве аргумента дерево и возвращает список значений, приписанных листьям дерева-аргумента.

Упражнение 2.7.1 Определите функцию samefrontier(х,у), которая возвращает true, если деревья х и у имеют одни и те же листья и в одном и том же порядке, независимо от внутренней структуры дерева, и false в противном случае. Правильное, но неудовлетворительное решение будет таким:

fun samefrontier (х, у) = (frontier х) = (frontier у)

Это довольно трудное упражнение; основная проблема состоит в том, чтобы избежать полной развертки дерева в случае, когда функция дол-CHK"HiQj выдать false.

ML также обеспечивает механизм определения абстрактных типов16. Они вводятся с помощью конструкции abstype. Абстрактный тип данных представляет собой некоторый рекурсивный тип данных и набор функций для работы с данными этого типа. Рекурсивный тип данных называется типом реализации абстрактного типа, а набор функций называется его интерфейсом. Тип, определенный с помощью конструкции abstype, является абстрактным в том смысле, что конструкторы его типа реализации недоступны программам, использующим этот тип: доступным является только интерфейс. Поскольку программа, использующая абстрактный тип данных, ничего не знает о его типе реализации, она пользуется для работы с ДАННЫМИ абстрактного типа только функциями интерфейса. Поэтому реализация абстрактного типа данных может быть изменена в любой момент, и это никак не скажется на программе, использующей абстрактный тип данных. Использование абстрактных типов данных - важный элемент структурного программирования, поскольку он позволяет избежать ненужных связей между компонентами большой программы.

Приведем пример объявления абстрактного типа:

-abstype color = blend of int*int*int with val white = blend(0,0,0)

16Более мощным инструментом, однако, оказываются модули, рассматриваемые в следующей главе.