где каждое ei является выражением типа г и n > 1. Это соответствует интуитивному понятию списка значений данного типа, при этом nil играет роль завершителя списка.

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

В случае списков, начальным случаем является nil, а индуктивным шагом является применение операции : :. Индуктивные определения типов играют важную роль в функциональном программировании, поскольку организация функциональной программы во многом определяется структурой обрабатываемых данных.

Ниже приводятся примеры использования nil и : : для построения списков:

>[] : a list

-3 :: 4 :: nil;

>[3,4] : int list

-(3:: nil):: (4 :: 5 :: nil) :: nil;

>[[3], [4,5]]: int list list

-["This", "is", "it" ] ;

>["This","is","it"]: string list

Обратите внимание на то, что ML выводит списки в сокращенном формате: последовательность разделенных запятыми элементов списка, заключенная в квадратные скобки. Этот формат может использоваться и для ввода списков - но помните, что это лишь сокращение для полного формата.

Тип списка nil - особый: он включает переменную типа (выводится как а и произносится как "альфа"). Причиной этого является то, что в пустом списке нет никакой информации о том, списком элементов какого типа он является. Было бы глупо требовать, чтобы имелись отдельные константы, обозначающие пустой список целых, пустой список логических и т.д. Поэтому ML трактует nil как полиморфный объект, т.е. как такой объект, который может принадлежать любому типу из некоторого класса. Константа nil может рассматриваться как int list, как bool list или как int list list в зависимости от контекста, в котором она

6Индуктивное определение задает определяемый класс предметов в соответствии со следующими тремя пунктами: (1) всякий предмет, описанный одним из начальных случаев, является определяемым предметом: (2) всякий предмет, полученный из уже построенных определяемых предметов путем применения какого-либо индуктивного шага, является определяемым предметом; (3) никаких других определяемых предметов, кроме полученных с помощью пунктов (1) и (2), нет. (Прим. перев.)

находится. Это выражается тем, что константе nil приписывается тип a list, где а является переменной, пробегающей множество типов. Частные случаи типа, включающего переменные типа (такой тип мы будем также называть полиморфным типом, или, короче, политипом), получаются путем замены всех вхождений данной переменной типа на какой-либо тип (при этом все вхождения данной переменной заменяются на один и тот же тип); подставляемый вместо переменной тип сам может быть полиморфным. Например, типы int list и (int*b) list являются частными случаями политипа a list. Типы, которые не содержат переменных типа, называются мономорфными типами (или, короче, монотипами).

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

-[1,2,3] = 1 :: 2 :: 3 :: nil;

>true : bool

-[[1], [2,4] ] = [ [2 div 2], [1+1, 9 div 3] ];

>false : bool

2.2.8 Записи

Последний составной тип, который мы рассмотрим в настоящем разделе, есть тип записи. Записи в ML аналогичны записям в Pascale, структурам в С и т.д. Запись состоит из конечного множества помеченных полей, каждое из которых является значением некоторого типа; как и в случае упорядоченных энок, различные поля могут иметь различные типы. Запись задается последовательностью равенств в форме l=e (где l есть метка и e - выражение), заключенной в фигурные скобки. Каж-l el e

l т lт

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

-{name="Foo",used=true };

>{name="Foo",used=true }: {name:string, used:bool}

-{name="Foo",used=true } = { used=not false, name="Foo"};

>true : bool

-{name="Bar", used=true} = {name="Foo", used=true}; > false : bool

Упорядоченные энки являются частным случаем записей: упорядоченная энка типа ai*02*. . -*an является сокращенным обозначением для записи типа { l:ai, 2:02,...,n:ara }. Например, выражения (3,4) и {1=3, 2=4} обозначают в точности одно и то же.

На этом завершается наше введение в первичные типы, значения и выражения языка ML. Мы хотим обратить ваше внимание на то, что значения всех рассмотренных типов строятся некоторым единообразным методом. Для каждого типа имеется свой набор форматов выражений, задающих значения этого типа. Для атомарных типов такими выражениями являются константы этих типов. Например, константами типа int являются последовательности цифр со знаком, а константами типа string являются последовательности литер, заключенных в двойные кавычки. Для составных типов значения строятся с помощью конструкторов значений, функцией которых является построение значений составного типа из значений компонент. Например, конструктор пары, записываемый как ( , ), берет два значения и формирует из них значение типа "упорядоченная пара". Аналогично, nil и : : являются конструкторами, которые формируют значение типа "список". Синтаксис записи может также рассматриваться как конструктор. Такой взгляд на данные, как на формируемые из констант с помощью конструкторов, является основополагающим в ML и будет играть важную роль в последующих рассмотрениях.

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

2.3 Идентификаторы, привязки и объявления

В этом разделе мы введем понятие объявления; объявления используются в ML для введения идентификаторов. Каждый идентификатор перед использованием должен быть объявлен (имена встроенных функций

-таких, как + или size - считаются объявленными заранее). Идентификаторы в ML могут использоваться многими различными способами, и в соответствии с этими способами существуют различные формы объявлений. В настоящем разделе мы рассмотрим идентификаторы значений, или переменные. Переменная вводится путем привязки идентификатора к значению. Например:

- val х = 4*5;

> val х = 20 : int