Standart ML. Урок 12. Определение новых типов

Standart ML   31 октября 2013  Автор статьи:  

Существует три формы объявления идентификатора как нового конструктора типа (прозрачная привязка к типу type, рекурсивное определение типа datatype и реализация абстрактного типа abstype).

Прозрачная привязка к типу

Конструктор типа (возможно, с параметрами) определяется как сокращение для некоторого (сложного) типового выражения. Все использования такого конструктора типа (threeInt) полностью эквивалентны использованию вместо него исходного выражения (int * real * int).

Создаем новый тип threeInt:

- type threeInt = int * real * int;
> type threeInt = int * real * int

Теперь разницы между threeInt и int * real * int нет, т.к. тип threeInt был определен равным типу int * real * int.

Функция f работает с типом threeInt и выводит центральный элемент:


- fun f (x : threeInt) =
let
val (left, centre, rigth) = x
in
centre
end;
> val f = fn : int * real * int -> real
- f (4, 12.4, 8);
> val it = 12.4 : real

[important]
Прозрачные привязки предназначены для сокращенной записи сложных типовых выражений. Задачей прозрачных привязок является повышение читабельности текста программы, а не создание новых типов как таковых.
[/important]

Рекурсивные типы или datatype

В конструкции указывается имя нового типа (возможно, с параметрами) и набор конструкторов значений для построения объектов этого типа.

Объявим новый тип данных car и 4 конструктора:


- datatype car = BMW | Audi | Lexus | Suzuki;
> New type names: =car
datatype car =
(car,{con BMW : car, con Lexus : car, con Suzuki : car, con Audi : car})
con BMW = BMW : car
con Lexus = Lexus : car
con Suzuki = Suzuki : car
con Audi = Audi : car

Теперь идентификатор car привязан к новому типу данных, имеющих конструкторы BMW, Audi, Lexus и Suzuki. Заметим, что конструкторы выводятся после ключевого слова con (а не val).


- Lexus;
> val it = Lexus : car

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

[note]Рекурсивное определение типа одновременно вводит новый конструктор типа и новые конструкторы значений.[/note]

Определяемые пользователем конструкторы значений могут иметь аргументы:


- datatype flowers = noflowers
| amount of int
| name of string
| buket of string * int;
> New type names: =flowers
datatype flowers =
(flowers,
{con amount : int -> flowers,
con buket : string * int -> flowers,
con name : string -> flowers,
con noflowers : flowers})
con amount = fn : int -> flowers
con buket = fn : string * int -> flowers
con name = fn : string -> flowers
con noflowers = noflowers : flowers

Тип flowers имеет четыре конструктора, первый из которых является константой, а три остальных имеют аргументы.

[important]Два значения некоторого рекурсивного типа равны, если они построены одним и тем же способом и соответствующие компоненты равны между собой. Таким образом, рекурсивный тип допускает проверку на равенство тогда и только тогда, когда все аргументы всех конструкторов значений имеют типы, допускающие проверку на равенство.[/important]

В рассмотренном примере тип flowers допускает проверку на равенство, поскольку типы int и string допускают ее:

- noflowers = noflowers;
> val it = true : bool
- noflowers = amount 4;
> val it = false : bool
- amount 4 = amount (4 + 0);
> val it = true : bool

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


- datatype bintree = empty | leaf | node of bintree * bintree;
> New type names: =bintree
datatype bintree =
(bintree,
{con empty : bintree,
con leaf : bintree,
con node : bintree * bintree -> bintree})
con empty = empty : bintree
con leaf = leaf : bintree
con node = fn : bintree * bintree -> bintree

Напишем рекурсивную функцию countLeaves, определенную на двоичных деревьях, которая бы подсчитывала количество листьев дерева:


- fun countLeaves (empty) = 0
| countLeaves (leaf) = 1
| countLeaves (node (treeFirst, treeSecond)) =
countLeaves (treeFirst) + countLeaves (treeSecond);
> val countLeaves = fn : bintree -> int

Определим дерево T:


- val T = node (node (leaf, leaf), node (node (leaf, leaf), leaf));
> val T = node(node(leaf, leaf), node(node(leaf, leaf), leaf)) : bintree
- countLeaves T;
> val it = 5 : int

Определим рекурсивный тип с параметром:


- datatype 'a tree = empty | leaf of 'a | node of 'a tree * 'a tree;
> New type names: =tree
datatype 'a tree =
('a tree,
{con 'a empty : 'a tree,
con 'a leaf : 'a -> 'a tree,
con 'a node : 'a tree * 'a tree -> 'a tree})
con 'a empty = empty : 'a tree
con 'a leaf = fn : 'a -> 'a tree
con 'a node = fn : 'a tree * 'a tree -> 'a tree

[note]Функция, определенная на рекурсивных данных, является рекурсивной.[/note]

[important]
Рекурсивное определение типа подходит для сложных структур данных (например, деревня), внутренняя структура которых должна быть доступна программе.
[/important]

Абстрактные типы или abstype

Абстрактный тип данных состоит из рекурсивного типа данных (тип реализации абстрактного типа) и набора функций (интерфейса) для работы с данными этого типа.

[important]Конструкторы реализации абстрактного типа недоступны программам, использующим этот тип, доступным является только интерфейс. А значит, реализация абстрактного типа данных может быть изменена когда угодно, и это никак не скажется на программе, использующей абстрактный тип данных.[/important]

[note]
Использование абстрактных типов данных позволяет избежать ненужных связей между компонентами большой программы.
[/note]

Пример абстрактного типа данных:


- abstype car = money of int * int * int
with
val suzuki = money (100, 700, 1150)
val toyota = money (110, 200, 800)
val infiniti = money (310, 950, 2300)
val citroen = money (210, 820, 2000)
end;
> New type names: car
type car = car
val suzuki = : car
val toyota = : car
val infiniti = : car
val citroen = : car
- citroen;
> val it = : car

Заметим, что описание интерфейса заключено между with и end.

В результате выполнения abstype не создается никаких конструкторов. Это делает невозможным создание новых значений типа car, кроме как использования значений и функций интерфейса.

Абстрактный тип не допускает проверку на равенство. Если для абстрактного типа должно быть равенство, оно должно быть явно определено как одна из интерфейсных функций.

[note]Абстрактное определение типа является более подходящим для использования, например, в случае стека или очереди.[/note]

В 13 уроке мы познакомимся с исключениями в Standart ML.

Научиться программировать

  • на Delphi

  • на Java

  • на C++