Декларативное программирование

[ Содержание | 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 И.А. Дехтяренко

5.8. Синтаксический сахар: язык Erlang.

Адепты функциональных языков, часто подчёркивают, что программы на этих языках намного короче и проще, чем те же программы на императивных языках. Во многом это обусловлено высоким уровнем функциональных языков и активным использованием готовых вычислительных образцов в виде функций высшего порядка. Но в значительной степени краткость и простота функциональных программ обязана большому количеству "синтаксического сахара", присутствующего в современных языках. Под синтаксическим сахаром понимаются конструкции языка, не вводящие новых абстракций, а предлагающие более краткое или более привычное обозначение для уже имеющихся. В этой части мы познакомимся с различными украшениями такого рода. Сделать это будет удобно на примере языка Erlang ¹. Этот язык семантически достаточно близок к Лиспу (по крайней мере его функциональное ядро) и в то же время обладает многими синтаксическими элементами, характерными для функциональных языков.

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

> 4+5/2.
6.50000
> 1+2,1-2.
-1
> abs(1 - 2 * 3).
5
> math:sqrt(1.0e8).
1.00000e+4
> erlang:abs(-10).
10

Каждое введённое выражение должно завершаться точкой. Можно ввести и несколько выражений, разделив их запятыми. В этом случае все они будут вычислены, но напечатано значение последнего. Функция abs встроена в язык, а библиотечная функция sqrt определена в модуле math. Чтобы вызвать её из оболочки необходимо указывать имя функции вместе с именем модуля. На встроенные функции можно ссылаться как на определённые в модуле с именем erlang. Значения выражений вычисляются в аппликативном порядке, причем как и в Лиспе порядок вычисления аргументов функций не определён.

Объекты данных, которыми манипулируют программы, называются термами². Их можно разделить на элементарные объекты - константы (числа, атомы и др.) и составные объекты (кортежи и списки).

Числа подразделяются на два типа: целые ³ и вещественные. Обозначения числовых констант - вполне традиционные, но имеется две особенности. Запись $<символ> представляет значение кода символа ($A = 65), а обозначение <основание>#<значение> используется для записи целых чисел по основанию отличному от 10 (допускаются основания от 2 до 16). Например: 16#FFFF = 65535, 2#101=5, 7#123=66.

Для чисел предусмотрены стандартные арифметические операции (+,-, *,/), а для целых чисел ещё и операции деления с остатком (div,rem) и поразрядные логические операции (bnot, band, bor, bxor). Операции "+","-" и "*" возвращают целое число, если оба аргумента целые. Операция деления "/" всегда возвращает вещественное. Преобразовать целое в вещественное можно функцией float, а обратно - функциями trunc и round. Операции сравнения также более-менее привычны.

Разница между парами (==,/=) и (=:=,=/=) состоит в том, что в первом случае допускается приведение целых чисел к вещественным, а во втором - нет, то есть 1==1.0, но 1=/=1.0.

> 4 div 2 == 4/2.
true
> 4 div 2 =:= 4/2.
false
> 4 div 2 =< 4/2.
true

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

В отличие от Лиспа, атомы не используются для именования других объектов (для этого есть переменные). Каждый атом представляет "самого себя" или, если угодно, некоторую сущность достойную того, чтобы иметь собственное имя.

Логические значения представляются атомами true и false. Они не выделены в особый тип данных, то есть могут использоваться и как обычные атомы. Определены стандартные логические функции not, and, or и xor. Эти операции не являются специальными формами - их аргументы вычисляются до вызова функции.

Для атомов нет никаких специальных операций, но их можно сравнивать, причём не только на равенство - атомы упорядочены лексикографически.

> hello == 'hello'
true
> (false < true) and (alpha < beta).
true
> 1 < one.
true
> 1.0e100 < inf.
true

Как видно атомы можно сравнивать и с числами - все числа "меньше" атомов. Очень кстати оказалось и то, что буква "f" предшествует "t".

Списки, хорошо знакомые нам по Лиспу, представляют собой цепочки вложенных пар. Конструктор списков имеет вид [<голова>|<хвост>] (сравните с точечной записью пары в Лиспе). Пустой список обозначается "[]". Аналоги функций car и cdr носят имена hd и tl. Как и в Лиспе предусмотрена сокращенная запись: список [a₁|[a₂|...[a_n|[]]...]] обычно записывают в виде [a₁,a₂,...a_n]. Поскольку синтаксис списков не имеет ничего общего с синтаксисом применения функций, нет необходимости в разного рода ухищрениях вроде тех, к которым приходилось прибегать в Лиспе.

> tl([1,1+1,1+1+1]).
[2,3]
> [1,2|[a,b]].
[1,2,a,b]
> [1,2,3|4].
[1,2,3|4]

Запись [1,2,3|4] аналогична лисповской (1 2 3 . 4), то есть обозначает "неправильный" список, не завершающийся []. Использовать такие списки следует весьма осторожно, так как большая часть библиотечных функций написана, в расчете на правильно построенные списки.

Специальная нотация предусмотрена для записи строк.

> "Hello world!".
"Hello world!"

Внешне выглядит так, будто имеются данные типа "строка". Однако, следующие примеры развеивают эту иллюзию.

> hd("Hello world!").
72
> [72,101,108,108,111,32,119,111,114,108,100,33].
"Hello world!"
> [$H,$e,$l,$l,$o,$ ,$w,$o,$r,$l,$d,$!].
"Hello world!"

В действительности, последовательность символов, заключенная в двойные кавычки, представляет список чисел - кодов этих символов. Конечно, такое представление строк не очень экономно, зато позволяет использовать для их обработки обычные списочные функции. При печати список, содержащий только числа, которые могут представлять символы, выводится в виде строки. Именно с таким представлением работают встроенные функции atom_to_list, integer_to_list и т.п.

> atom_to_list(alpha).
"alpha"
> integer_to_list(10).
"10"
> list_to_float("12.34").
12.3400

Кортежи (tuples) или "n-ки" представляют упорядоченные наборы объектов но, в отличие от списка, каждый кортеж составляет единое целое. Наиболее близкая аналогия - массивы⁴. Кортежи записываются как последовательности термов, разделённые запятыми и заключенные в фигурные скобки. Кортеж может содержать и один элемент или не содержать их вовсе. Размер кортежа можно узнать с помощью функции size. Доступ к элементам производится по их номерам с помощью функции element. Функция setelement возвращает копию кортежа, в которой значение одного элемента заменено новым.

> size({a,b,c}).
3
> element(2,{a,b,c}).
b
> setelement(2,{a,b,c},2*5).
{a,10,c}

Отношение порядка распространяется на все термы. Мы уже знаем, что числа "меньше" атомов. Атомы в свою очередь "меньше" кортежей, которые "меньше" списков. Кортежи упорядочены сначала по размерам, потом по элементам. Списки упорядочены сначала по головам, затем по хвостам. Все нижеследующие выражения вернут true.

1 < {1}
{1,2,3} == {1,2,3}
{a} < {1,2,3}
{1,a} < {a,1}
{a,b} < [a,b]
[a] < [a,b]

Переменные предназначены для именования других объектов. Они представляют собой последовательности букв, цифр и знаков подчёркивания начинаются с прописной буквы или знака подчёркивания. Значение переменной может быть присвоено только однажды ⁵, а попытка обратиться к несвязанной переменной приводит к ошибке. Собственно, термин "переменная" скорее соответствует одноимённому понятию из логики - переменная замещает имя объекта, а не указывает на место в памяти компьютера.

> A = 2 + 2.
4
> A.
4
> A = 5.
** exited: {{badmatch,4},[{erl_eval,expr,3}]} **
> A = 3 + 1.
4

Такое поведение может вызвать недоумение. Сначала мы присваиваем A значение 2+2 и убеждаемся что A = 4. Затем пытаемся присвоить A значение 5 и получаем сообщение об ошибке. Но потом снова присваиваем A значение 3+1 и на этот раз всё проходит!

В действительности, знаком "=" обозначается не присваивание, а операция сопоставления. Если левая часть выражения L = R представляет собой свободную переменную, она получает значение выражения R. В противном случае сравниваются значения обоих выражения. Если они совпадают - сопоставление успешно, а если нет - неудачно.

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

Последние две строчки демонстрируют специальный образец "_" (иногда называемый "анонимной переменной"), который сопоставляется с любым термом, но не вызывает никаких присваиваний.

Сопоставление - чрезвычайно важная операция. Она используется не только для означивания переменных, но и как общий метод передачи параметров.

Функциональные объекты это функции, рассматриваемые как объекты данных. Их можно непосредственно применять к аргументам, а можно присваивать переменным, включать в структуры данных, передавать в качестве аргументов и возвращать в качестве значений функций. Чтобы формировать новые функциональные объекты имеются специальные формы, подобные лисповским лямбда-выражениям. Простейшая форма такого выражения: fun(аргументы) -> тело end .

> fun(X)-> X*X end (2).
4
> Sqr = fun (X)-> X*X end.
#Fun<erl_eval>
> Sqr(3).
9
> Cons = fun (H,T)-> [H|T] end.
#Fun<erl_eval>
> Cons(1,[2,3]).
[1,2,3]

Тело функции - либо выражение либо последовательность выражений, разделённых запятыми. В последнем случае все выражения вычисляются по порядку, а значением тела становится значение последнего выражения. Наличие нескольких выражений в теле имеет смысл при использовании побочных эффектов. Но гораздо чаще дополнительные выражения применяются для означивания локальных переменных.

> Geron = fun(A, B, C) ->
    P = (A + B + C)/2,
    math:sqrt(P*(P-A)*(P-B)*(P-C))
  end.
#Fun<erl_eval>
> Geron(3,4,5).
6.00000

В Erlang, как и в Scheme применяется статическое связывание переменных. Переменная, определенная внутри функции видима до конца этой функции. Можно отметить аналогию с локальными определениями define. В то же время, отсутствуют более тонкие средства управления контекстом подобные let-выражениям.

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

> F = fun
  (1) -> one;
  (2) -> two;
  (3) -> three;
  (N) -> {too_big,N}
  end.
#Fun<erl_eval>
> F(3).
three
> F(5).
{too_big,5}

На функциональные объекты также распространяется отношение порядка. Функции располагаются между атомами и кортежами. Трудно приписать какой-нибудь смысл утверждению, что одна функция больше другой, но какой-то порядок система все же устанавливает. Отношение равенства для функций вполне осмыслено - две функции равны, если выдают одни и те же значения для одних и тех же аргументов. К сожалению, выяснить это по определениям функций не представляется возможным. Поэтому два функциональных объекта считаются равными, только если они ссылаются на одно и то же определение.

> Sqr = fun (X)-> X*X end.
#Fun<erl_eval>
> Sqr1 = Sqr.
#Fun<erl_eval>
> Sqr2 = fun (X)-> X*X end.
#Fun<erl_eval>

> Sqr1 == Sqr.
true
> Sqr2 == Sqr.
false

Условные выражения представлены двумя формами: if и case, имеющими вид

if охрана1 -> тело1;
   ...
   охранаn -> телоn
end

case выбирающее_выражение of
   образец1 [when охрана1] -> тело1
   ...
   образецn [when охранаn] -> телоn
end

Результатом if-выражения будет значение тела, соответствующего первой успешной охране (подробнее об охранах чуть ниже). Если ни одна охрана не выполняется, возникает ошибка. При вычислении case-выражения значение выбирающего выражения поочерёдно сопоставляется со всеми образцами. Если сопоставление успешно для какого-нибудь образца (и выполняется соответствующая охрана, если она присутствует), то значение соответствующего выражения и будет значением условного выражения. В противном случае возникает ошибка.

Роль условных выражений в Erlang скромнее, чем в Лиспе, поскольку синтаксис определения функций позволяет непосредственно использовать охраны и сопоставления с образцами. Например, вместо

Sign = fun(X) ->
  if X = 0 -> 0;
     X > 0 -> 1;
     X < 0 -> -1
  end
end.

Sign = fun
  (0)  -> 0;
  (X) when X>0 -> 1;
  (X) when X<0 -> -1
end.

В охранах можно использовать не любые логические выражения. Выражения, допустимые в охранах (их называют тестами или проверками) могут содержать операции сравнения, арифметические операции и другие встроенные функции. Например, недопустимо выражение.

if math:sin(X) > 1 -> wartime;
   true -> peacetime
end.

case math:sin(X) > 1 of
  true  -> wartime ;
  false -> peacetime
end.

Кроме того есть специальные системные тесты, определяющие тип объекта.

list(X)	X - список
tuple(X)	X - кортеж
constant(X)	X - не список и не кортеж
function(X)	X - функциональный объект
atom(X)	X - атом
number(X)	X - число
integer(X)	X - целое число
float(X)	X - вещественное число

Эти тесты применяются только в охранах. Попытка просто вычислить integer(1) приведёт к ошибке.

Каждая охрана может содержать несколько тестов, разделенных запятыми. Тесты испытываются по порядку слева направо. Если один из них неудачен, то неудачна и вся охрана, а остальные тесты не проверяются. Можно сказать, что ","- аналог and с особым порядком вычислений. Имеется подобный аналог и для or - ";".

Охрана

1<X, X<5 ; -5<X, X< -1

проверяет то же условие, что и

(1<X) and (X<5) or (-5<X) and (X< -1)

но делает это по сокращённой схеме.

Ещё одну особенность охран рассмотрим на примере

> F = fun
   ([])  -> empty_list;
   ([_|_]) -> nonempty_list;
   (N)    when N rem 2 == 0 -> even_number;
   (N)    when N rem 2 == 1 -> odd_number;
   (_)    -> something_else
  end.
#Fun<erl_eval>
> F(1)
odd_number
> F([1])
nonempty_list
> F({1})
something_else

Обратите внимание на последнее выражение. Значение выражения F({1}) - something_else, несмотря на то, что {1} сопоставляется с N и проверка охраны {1} rem 2 == 0 должна бы привести к ошибке, так как функция rem не определена для кортежей. Это общее правило - выражение, приводящее к ошибке, будучи употребленным внутри охраны вызовет всего лишь неудачу.

> A=1.
1
> hd(A)
= ERROR REPORT ===
...

> if hd(A) == 1 -> list_starts_with_1 ;
    true -> something_else  end.
something_else

Функция hd определена только для списков и попытка вычислить hd(1) приводит к ошибке. Но во втором выражении эта же попытка приводит к неуспеху охраны и переходу к другому варианту. Такое поведение может показаться несколько странным, но следует признать, что оно может быть логически обосновано. При этом, правда, потребуется пожертвовать некоторыми законами классической логики Например, если A или B не определены, то оба выражения A==B и A/=B следует признать ложными.

Определения функций

Собственно, понятие программы или приложения, как таковое, отсутствует. Мы записываем определения функций, собирая их в модули. После компиляции модуля  любая общедоступная (экспортируемая из данного модуля) функция, содержащаяся в нем может быть вызвана из оболочки или из другой функции. Таким образом, мы вольны объявить программой любое множество модулей или функций, руководствуясь при этом здравым смыслом.

Модули в Erlang не только единицы компиляции. Каждый модуль имеет собственное пространство имён. Те же самые имена функций можно использовать в различных модулях. Чтобы вызвать функцию из другого модуля надо либо указать её полное имя, либо предварительно импортировать её. Такая модульная организация значительно упрощает сопровождение больших программ. Просматривая текст модуля, всегда можно точно сказать в каком модуле определена та или иная функция, вызываемая из этого модуля.

Наша первая программа повторяет функцию вычисления факториала, написанную на Лиспе.

-module(sample).
-export([fact/1]).

fac(N) ->
   if N == 1 -> 1;
      N > 1  -> N * fac(N-1)
   end.

Первая строка - заголовок модуля, определяет его имя. Следующая - описание экспорта. Она содержит список функций, видимых за пределами модуля. Каждая функция определяется своим именем и количеством аргументов. В одном модуле могут сосуществовать совершенно разные функции с одним и тем же именем, но разной арности. Запись fac/1 указывает, что экспортируется функция одного аргумента с именем fac. Затем идёт собственно определение функции. В данном случае оно очень похоже на определяющую форму define. Теперь скомпилируем модуль и вызовем функцию.

> c(sample).
{ok,sample}
> sample:fac(5).
120

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

fac(1) -> 1;
fac(N) -> N * fac(N-1).

Вместо того чтобы конструировать процедуру с помощью условных выражений, мы записываем набор правил переписывания. Эти правила можно рассматривать и как аксиомы, уравнения которым должна удовлетворять функция. Конечно, эти аксиомы подразумеваются и в первом определении, но здесь они выписаны совершенно явно. Достаточно заменить "->" на "=" и получим два уравнения, однозначно определяющие функцию факториала. Хотя вычисляется одна и та же функция, одним и тем же методом, можно сказать что второе определение "более декларативно", поскольку помогает сосредоточиться на свойствах функции, в то время как первое подчёркивало метод её вычисления. Другими словами, первая процедура описывает как вычислять факториал, а вторая - определяет что такое факториал. Это может показаться риторикой сомнительного толка, но такая разница в нотации действительно оказывает влияние на стиль мышления программиста. Ещё более важно то, что в функции, записанные таком виде гораздо легче поддаются формальному анализу.

Можно заметить, что поведение двух описанных процедур для неположительных аргументов различно. Первая немедленно завершиться ошибкой, а вторая - зациклится. Нетрудно ввести проверку и во второе определение, добавив охрану.

fac(1) -> 1;
fac(N) when N > 1 -> N * fac(N-1).

В общем случае определение функции представляет собой набор правил (предложений)

имя(список_аргументов1) [when охрана1]-> тело1;
...
имя(список_аргументовn) [when охранаn]-> телоn.

Предложения разделяются точками с запятой, а всё определение завершается точкой. Список аргументов в заголовке предложения состоит из образцов, в частном случае - просто переменных. При вызове функции фактические значения аргументов сопоставляются с образцами в заголовках. Если какое-либо сопоставление удачно, проверяется соответствующая охрана. В случае успеха последовательно вычисляются все выражения соответствующего тела и значение последнего из них возвращается. Если же ни одно сопоставление неудачно или ни одна охрана для успешных сопоставлений не выполняется, возникает ошибка ⁶.

В качестве иллюстрации ещё пара знакомых функций.

fib(1) -> 1;
fib(2) -> 1;
fib(N) -> fib(n-1)+fib(n-2).

gcd(A,A) -> A;
gcd(A,B) when A>B -> gcd(A-B,B);
gcd(A,B) when A<B -> gcd(B-A,A).

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

f(X) when tuple(X), size(X)==2, element(1,X)== alpha ->
   g(element(2,X)).

swap(L) when list(L)->
   [hd(tl(L)),hd(L)|tl(tl(L))]

мы можем применить простые сопоставления

f({alpha,Y}) -> g(Y).
swap([A,B|T]) -> [B,A|T].

Иногда анализируя структуру терма, необходимо в то же время оперировать им как целым. В таких случаях полезными оказываются составные образцы вида P1=P2. При сопоставлении терма с таким образцом, он сопоставляется с обеими частями P1 и P2. Например, вместо

dup_head([A|T]) -> [A,A|T].

можно записать

dup_head([A|_]=L) -> [A|L].

Кортежи и записи.

Кортежи применяются для представления объектов, имеющих фиксированное количество элементов. Например, рациональные числа естественно представлять парами {Enum, Denom}, а узлы бинарного дерева - тройками {Label,Left,Right}. Стандартный приём - помещать в первый элемент кортежа признак типа объекта. Те же элементы дерева могут иметь вид {node,Label,Left,Right}. Следует выбрать представление и для пустого дерева, допустим что это атом empty. Тогда процедура проверки, содержится ли элемент в дереве может быть записана следующим образом.

in(X,empty) -> false;
in(X,{node,X,_,_}) -> true;
in(X,{node,Y,L,_}) when X < Y -> in(X,L);
in(X,{node,Y,_,R}) when X > Y -> in(X,R).

Использование кортежей становится неудобным, если они содержат большое число элементов. Приходится выписывать длинные образцы да ещё и помнить местоположение каждого элемента. К тому же изменение представления становится просто мучительным - представьте, что нам понадобилось внести дополнительное поле "значение" и элементы дерева приобрели вид {node,Label,Value,Left,Right}. 

Конечно, можно было бы определить соответствующие конструкторы и селекторы, например

node(X,L,R) -> {node,X,L,R}.
is_node(T) when tuple(T), size(T)==4 -> elem(1,T)== node;
is_node(_) -> false.
label(T) -> elem(2,T).
left(T)  -> elem(3,T).
right(T) -> elem(4,T).

node(X,L,R) -> {node,X,L,R}.
is_node({node,_,_,_}) -> true;
is_node(_) -> false.
label({node,X,_,_}) -> X.
left ({node,_,L,_}) -> L.
right({node,_,_,R}) -> R.

Но при этом теряется возможность использовать образцы и мы будем вынуждены записывать сложные условные выражения вроде

in(X,T) ->
  if is_node(T)->
       Y = label(T);
       if X == Y -> true;
          X < Y  -> in(X,L);
          X > Y  -> in(X,R)
       end;
     true -> false
end.

Специальный синтаксический сахар позволяет приписывать имена элементам кортежей и обращаться к ним по этим именам. При таком обращении кортежи напоминают структуры Си или записи Паскаля, поэтому их и называют записями.

Например, мы можем объявить тип записи node директивой

-record(node,{label,left,right}).

Эта директива определяет одновременно конструктор записи и соответствующие селекторы. Теперь выражение #node{label=X,left=L,right=R} вернет кортеж {node,X,L,R}. Получить значение поля label записи T можно выражением T#node.label, которое эквивалентно element(2,T). Выражение T#node{label=X} означает то же что setelement(2,T,X) - запись, в которой поле label имеет значение X, а значения остальных полей совпадают с их значениями в записи T. Если при вызове конструктора, указаны значения не для всех полей, то в недостающие поля будет подставлено значение undefined. Но если конструктор используется как образец, то недостающие поля заменяются "_". Например, #node{} будет преобразовано в {node,_,_,_}, а #node{label=X} - в {node,X,_,_}.

Наша процедура in приобретает вид.

in(X,empty) -> false;
in(X,node{label=X}) -> X;
in(X,node{label=Y,left=L})  when X<Y -> in(X,L);
in(X,node{label=Y,right=R}) when X>Y -> in(X,R).

Обработка списков.

Многие функции, обрабатывающие рекурсивные структуры данных, такие как списки, легко выражаются в виде наборов очень простых правил.

Для вычисления длины списка достаточно записать два правила:
1) длина пустого списка = 0;
2) длина непустого списка на 1 больше, чем длина его хвоста.

length([])-> 0;
length([H|T])-> 1 + length(T).

Следующая функция определяет содержится ли данный терм в списке. В данном случае имеем три правила.
1) в пустом списке ничего содержаться не может;
2) если терм совпадает с головой списка то он присутствует в списке;
3) терм содержится в списке, если он содержится в его хвосте.

member(X, []) -> false;
member(X, [X|_]) -> true;
member(X, [_|L]) -> member(X, L).

Функция соединения списков удовлетворяет двум правилам:
1) присоединяя список к пустому списку, получим этот же список;
2) соединением непустого списка с любым другим будет список, голова которого - голова первого списка, а хвост - соединение хвоста первого списка со вторым.

append([], L) -> L.
append([H|T], L) -> [H|append(T, L)].

Пожалуй, формальная запись этих условий понятней и точнее их словесных описаний. Подобная ситуация часто возникает при попытке описать словами математические формулы.

Точно так же, как мы делали в Лиспе, мы можем выделить часто встречающиеся образцы вычисленийв функции высшего порядка.

map(F, []) -> [];
map(F, [H|T]) -> [F(H)|map(F, T)].

foldr(F, E, []) -> E;
foldr(F, E, [H|T]) -> F(H, foldr(F, E, T)).

foldl(F, E, []) -> A;
foldl(F, E, [H|T]) -> foldl(F, F(H, E), T).

filter(P, []) -> [];
filter(P, [H|T]) ->
   case P(H) of
      true -> [H|filter(P, T)];
      false -> filter(P, T)
   end.

Часто встречающиеся функции length, member и append встроены в язык (последняя - в виде бинарной операции "++"), а многие другие определены в библиотечном модуле lists ⁷. Встроенная операция "вычитания" списков ("--") удаляет из первого списка элементы, содержащиеся во втором, причём удаляется первый совпавший элемент.

> length([1,2,3]) .
3
> [1,2,3] ++ [a,b,c] .
[1,2,3,a,b,c]

> [1,2,3,2,1] -- [2,4] .
[1,3,2,1]
>
[1,2,3,2,1] -- [2,2] .
[1,3,1]

lists:map(fun (X)-> X*X end,[1,2,3]).
[1,4,9]

F = fun (1)-> 2; (2) -> 1; (_) -> 0 end.
lists:map(F,[1,2,3,4,5]).
[2,1,0,0,0]

В двух последних примерах функции map передавались динамически создаваемые функциональные объекты. Поскольку передать уже определённую функцию просто по имени нельзя (ведь имя функции представляет собой атом - совершенно другой объект), для этого предусмотрена специальная конструкция: fun имя/арность.
Выражение fun f/n эквивалентно fun (X1,...Xn)->  f(X1,...Xn) end. Например:

-import(lists,[map]).

sqr(X)-> X*X.
...
map_sqr(L) -> map(fun sqr/1,L)

Если же функция определена в другом модуле, используется ещё одна форма: {имя_модуля,имя_функции} ⁸.

> lists:map({erlang,'-'},[1,2,3]).
[-1,-2,-3]
> lists:foldl({erlang,'+'},0,[1,2,3]).
6

Очень выразительное средство - конструкторы списков, известные как ZF-выражения или list comprehensions. Их идея заимствована из теории множеств, где популярна аксиоматика Цермело-Френкеля (отсюда и первоначальное название). Например множество чётных чисел можно описать как {n | nОN, n = 0 (mod 2)} или {2k | kОN}, множество их квадратов как {n² | nОN, n = 0 (mod 2)}, а множество пифагоровых троек как {(n,m,k) | nОN,mОN,kОN, n²+m²=k²}.

Аналогично выражение [F(X) || X <- L]обозначает список, полученный применением функции F ко всем элементам L, а выражение [X || X <- L, P(X)] список элементов L, удовлетворяющих условию P (это условие называют фильтром, а подвыражение X <- L генератором). Очевидно, что это просто другая запись применения функций map и filter. Можно даже дать дать им такие определения:

map(F, L) -> [F(X) || X <- L].
filter(P, L) -> [X || X <- L, P(X)].

Чуть более сложное выражение [F(X) || X <- L, P(X)] эквивалентно map(F,filter(P,L)).

> [X*2 || X<-[1,2,3,4,5], X>2].
[6,8,10]

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

 map(fun (X)-> X*2 end,
     filter(fun (X)-> X>2 end,
            [1,2,3,4,5])).

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

> [{X,Y} || X<-[1,2,3], Y<-[a,b]].
[{1,a},{1,b},{2,a},{2,b},{3,a},{3,b}]

> [{X,Y} || X<-[1,2,3], Y<-[1,2,3], X<Y].
[{1,2},{1,3},{2,3}]

> L=lists:seq(2,10).
[2,3,4,5,6,7,8,9,10]
> [{X,Y,Z} || X <- L, Y <- lists:seq(2,X),
              Z <- lists:seq(Y,X), X == Y*Z].
[{4,2,2},{6,2,3},{8,2,4},{9,3,3},{10,2,5}]

Общий вид ZF-выражения: [ образец || описатель₁,...описатель_n], где каждый описатель представляет собой либо генератор, либо фильтр. Если присутствует несколько генераторов, то каждого выдаваемого значения перебираются все значения, выдаваемые последующими генераторами (сравните со вложенными циклами for). Все переменные, входящие в образец должны быть связаны с генераторами, но не всякая генерируемая переменная обязана входить в образец. В крайнем случае он вообще может не содержать переменных.

> [1 || X<-[1,2,3,4,5]].
[1,1,1,1,1]

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

> [{X,Y} || {Y,X} <- [{a,1},{b,2},{c,3}]].
[{1,a},{2,b},{3,c}]

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

permutations([])-> [[]];
permutations([H|T]) ->
   [X || Y <- permutations(T), X <- interleaves(H,T)].

interleaves(A,[])-> [[A]];
interleaves(A,[H|T]) ->
   [A,H|T] ++ [[H|Y] || Y <- interleaves(A,T)].

Сортировка списков.

Тема сортировки очень популярна в контексте анализа сложности алгоритмов. Мы рассмотрим несколько известных методов сортировки и посмотрим как они будут выглядеть применительно к спискам - нашему основному средству преставления последовательностей. Особенности списков придают определенную специфику задаче сортировки. Некоторые алгоритмы, разработанные для массивов, такие как знаменитый метод пузырька практически непригодны для списков и нам придется их проигнорировать. Впрочем, многого мы от этого не потеряем.

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

Наверняка, первое, что приходит в голову: наименьший элемент исходного списка, будет первым в упорядоченном списке и нам остаётся отсортировать оставшуюся часть списка.

ssort([]) -> [];
ssort(L) -> X = lists:min(L), [X| ssort(L--[X])].

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

Пусть первая часть состоит из элементов, меньших некоторого "центрального" элемента, а вторая из больших или равных ему. Отсортировав эти части и соединив результаты получим искомый упорядоченный список. Проще всего в качестве центрального использовать первый элемент.

qsort([]) -> [];
qsort([H|T]) ->
    qsort([ X || X <- T, X < H]) ++
    [H]++
    qsort([ X || X <- T, X >= H])].

Хотя эта процедура порождает древесно-рекурсивный процесс, она быстрее предыдущей. Если предположить, что список делится на равные части, то есть что процедура рекурсивно обращается себе с аргументом в два раза короче, то общее число вызовов будет логарифмом длины списка. Учитывая, что при каждом из этих вызовов потребуется еще линейное время на разбиение списка получаем порядок сложности O(n*log n).

Записанная процедура кратко и изящно выражает сущность алгоритма "быстрой сортировки". Правда, она оставляет простор для оптимизации. Первое, что бросается в глаза, при разбиении список просматривается дважды (подобным недостатком обладает и ssort). Это становится совсем очевидным, если переписать её в виде

qsort([H|T]) ->
    A =[ X || X <- T, X < H]),
    B =[ X || X <- T, X >= H]),
    qsort(A)++[H]++qsort(B).

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

split_by(M,[]) -> {[], []};
split_by(M,[H|T]) ->
  {A, B} = split_by(M,T),
  if H < M  -> {[H|A], B};
     H >= M -> {A, [H|B]}
  end.

qsort([]) -> [];
qsort([H|T]) ->
   {A, B} = split_by(H,T),
   qsort(A) ++ [H|qsort(B)].

Можно избавится и от довольно расточительной операции объединения, если применить метод накапливающего параметра.

qsort(X) -> qsort(X, []).

qsort([], L) -> L;
qsort([H|T], L) ->
   {A, B} = split_by(H,T),
   qsort(A, [H|qsort(B,L)]).

К сожалению быстрая сортировка обладает одним неприятным свойством - она плохо ведёт себя на уже упорядоченных или близких к этому списках. В худшем случае список будет разбиваться на крайне неравномерно и мы получим усложненный вариант сортировки выбором. Поскольку реальные данные часто бывают упорядочены, это становится проблемой. Чтобы избавиться от таких неприятностей часто в качестве центрального выбирают не первый, а средний элемент списка. При этом все равно могут встретится "плохие" последовательности, но вероятность этого очень мала.

В рассмотренных алгоритмах основная тяжесть работы ложится на процедуру разбиения списка. Объединение же просто элементарно. Но можно поступить и по другому - усложнить операцию объединения и за счет этого упростить разбиение. Так, имея упорядоченный список, мы можем вставить в него элемент не нарушая упорядоченности с помощью простой процедуры insert. (Мы уже решали подобную задачу, когда рассматривали представление множеств упорядоченными списками).

insert(X, []) -> [X];
insert(X, [H|T]) when X =< H -> [X,H|T];
insert(X, [H|T]) when X > H -> [H|insert(X,T)]

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

isort(L) -> lists:foldr(fun insert/2,[], L).

isort([])-> [];
isort([H|T]) -> insert(H,isort(T)).

Мы получили хорошо известную "сортировку вставками". Подобно сортировке выбором, она имеет квадратичную сложность. Однако, можно заметить что для уже упорядоченных списков сложность становится линейной. Действительно, в этом случае вставка каждого элемента будет выполнятся за постоянное время. Опять же, можно добиться большей эффективности, если делить список на две равные части, которые затем сортируются и объединяются. Таким образом мы приходим к сортировке слиянием.

msort([])  -> [];
msort([X]) -> [X];
msort(L)   ->
   {A,B} = split(L),
   merge(msort(A), msort(B)).

Общая схема напоминает быструю сортировку, но к разбиению теперь не предъявляется особых требований, зато слияние усложняется. Функция merge получает два упорядоченных списка, и объединяет их элементы в один упорядоченный список. Как мы уже знаем, это можно сделать за время, пропорциональное длине списков.

merge([], L) -> L;
merge(L, []) -> L;
merge([X|Xs], [Y|Ys]) when X = Y ->  [X,Y| merge(Xs,Ys)];
merge([X|Xs], [Y|Ys]) when X < Y ->  [X| merge(Xs, [Y|Ys])];
merge([X|Xs], [Y|Ys]) when X > Y ->  [Y| merge([X|Xs], Ys)].

Единственное, что требуется от процедуры разбиения - выдавать части примерно равной длины. Например, можно распределять элементы поочерёдно

split([]) -> {[], []};
split([H|T]) -> {A,B} = split(T), {[X|B],A}.

split(L) ->
   N= length(L) div 2,
   {lists:sublist(L,1,N),lists:nthtail(N,L)}.

Сортировка слиянием ведёт себя более стабильно, чем быстрая сортировка. Список всегда делится пополам, поэтому порядок O(n*log n) достигается в любом случае. Поскольку это теоретический предел, казалось бы желать больше нечего. Но, как уже говорилось, данные часто бывают уже упорядоченными. И если в случае быстрой сортировки это обстоятельство было проблемой, то теперь мы попытаемся превратить его в преимущество.

Прежде всего, перестроим структуру процедуры, разделив фазы разбиения и слияния.

sort(L) -> mergeAll(split(L)).

Функция split теперь возвращает список, состоящий из упорядоченных подсписков L. Пусть для начала все подсписки будут содержать по одному элементу.

split(L) -> [[A] || A <-L ].

Функция mergeAll сливает все эти подсписки в один упорядоченный список, используя merge. Причём слияния производятся попарно, с тем чтобы после каждого прохода получать в два раза меньше подсписков.

mergeAll([A])  -> A;
mergeAll(L)    -> mergeAll(mergePairs(L)).

mergePairs([A,B|L]) -> [merge(A,B) | mergePairs(L)];
mergePairs(L) -> L.

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

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

split([]) -> [[]];
split(L)-> {L1,L2} = splitA(L),  [L1|split1(L2)].

splitA([])  -> {[],[]} ;
splitA([A]) -> {[A],[]};
splitA([A,B|L]) when A=<B -> {L1,L2} = splitA([B|L]),{[A|L1],L2};
splitA([A,B|L]) -> {[A],[B|L]}.

В худшем случае (если список упорядочен в обратном порядке) эта версия split вернет тот же результат, что и предыдущая. Но в особо благоприятном случае (если список уже правильно упорядочен) получим список из одного подсписка, который mergeAll сразу вернет в качестве результата.

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

split([])->  [[]];
split([A|L])->  splitA(L,[A]).

splitA([],R) -> [lists:reverse(R)];
splitA([X|L],[A|R]) when X>=A -> splitA(L,[X,A|R]);
splitA(L,R) -> [lists:reverse(R)|split(L)].

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

split([])->  [[]];
split([A|L])->  splitD(L,[A]).

splitD([],R) -> [R];
splitD([X|L],[A|R]) when X=<A -> splitD(L,[X,A|R]);
splitD(L,R) -> [R|split(L)].

Но, конечно же, лучше использовать и то и другое.

split([])  -> [[]];
split([X]) -> [[X]];
split([X|L]) -> splitD(L,[X]).

splitD([],Rs) -> [Rs];
splitD([X|L],[A|Zr]) when X<A -> splitD(L,[X,A|Zr]);
splitD([X|L],Rs) -> split2(L,Rs,[X]).

split2([],R,Q) -> [R,lists:reverse(Q)];
split2([X|L],[A|R],[B|Q]) when X=<A -> split2(L,[X,A|R],[B|Q]);
split2([X|L],[A|R],[B|Q]) when X>B -> split2(L,[A|R],[X,B|Q]);
split2(L,R,Q) -> [R,lists:reverse(Q)| split(L) ].

С такой процедурой разбиения наша функция sort сохраняет достоинства обычной сортировки слиянием и в то же время выполняется очень быстро для списков, содержащих длинные возрастающие или убывающие последовательности.

Хотя оптимизация может оказаться увлекательным занятием, она далеко не всегда бывает оправданной. Конечно переход от алгоритма сложности O(n²) к алгоритму сложности O(n*log n) заманчив, и вполне целесообразен, но остальные улучшения приводили к значительному усложнению программ. К тому же умозрительная оценка сложности для функциональных программ практически никогда не бывает правильной. Функциональные языки слишком далеки от архитектуры современных компьютеров, а оптимизирующие компиляторы выдают подчас неожиданные результаты. Поэтому общее правило "сначала измерь, а потом оптимизируй" в функциональном программировании приобретает характер категорического императива.

В ленивых языках ситуация ещё более запутанная. Вычислительная сложность функции зависит не только от её определения, но и от контекста вызова. Например, обе функции ssort и isort имеют квадратичную сложность. Но если мы используем их для поиска наименьшего элемента, то выражения вида hd(isort(L)) потребуют количества редукций, линейно зависящего от длины списка.

¹ Язык программирования Erlang был разработан в конце 1980-х в лаборатории информатики компании Ericsson для программирования систем управления телекоммуникационными сетями. Назван в честь Агнера Эрланга - датского инженера, известного своим вкладом в создание математической теории массового обслуживания. В настоящее время используется в промышленности при создании распределенных отказоустойчивых систем, работающих в реальном масштабе времени.

² Строго говоря, термами называются не сами объекты, а выражения их обозначающие. Но часто допускают подобную вольность речи.

³ Описанием языка гарантируется, по крайней, мере 24-разрядное представление целых чисел, то есть диапазон от -16777215 до 16777215. На деле, однако, в доступной реализации числа имеют неограниченный диапазон.

⁴ В Лиспе также есть подобные структуры, называемые векторами, но работа с ними скорее ориентирована на императивный стиль программирования.

⁵ Хотя оболочка позволяет "забывать" значения переменных, но это средство предназначено только для отладки. В отличие от Лиспа Erlang не имеет оператора присваивания и в этом смысле более строго соответствует функциональному подходу.

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

fact(N) -> N * fact(N-1);
fact(1) -> 1.

⁷ Возможно вы обратили внимание на то, что определение левой свертки (foldl) отличается от "канонического" определения, которое мы давали раньше. Но именно в таком виде встречается в модуле lists.

-module(proper).
-export([foldl/3]).
foldl(_, E, []) -> E;
foldl(F, E, [H|T]) -> foldl(F, F(E,H), T).

> lists:foldl(fun(X,Y)-> {X,Y} end,e,[a,b,c]).
{c,{b,{a,e}}}
> proper:foldl(fun(X,Y)-> {X,Y} end,e,[a,b,c]).
{{{e,a},b},c}

> lists:foldl(fun(X,Y)-> [X|Y] end,[],[1,2,3]).
[3,2,1]
> proper:foldl(fun(X,Y)-> [X|Y] end,[],[1,2,3]).
[[[[]|1]|2]|3]

Это типичный пример того как теоретическая строгость и элегантность приносится в жертву соображениям практического удобства.

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

> apply({math,sqrt},[4]).
2.00000

Функция map определялась следующим образом

map(F,[]) ->    [];
map(F,[H|T]) -> [apply(F,[H])|map(F,T)].

map({math,sqrt},[1,2,3]).

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

> {erlang,'+'}(1,2).
3

[ Содержание | 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 | Литература ]