Мы начали с определения очень простой функции listify, которая преобразует аргумент в одноэлементный список. Функция listify2 полностью эквивалентна функции listify за исключением способа ее определения. Результатом вычисления выражения fn х => [х] является функция, которая преобразует аргумент х в список [х] - точно так же, как это делает функция listify. Такое выражение, вырабатывающее функцию, мы можем применять к аргументу непосредственно (как в предпоследнем случае) или передать в качестве аргумента другой функции (как в последнем случае).

Точно так же, как и при использовании fun, при использовании fn можно применять сопоставление с образцом:

-( fn nil => nil I hd::tl => tl ) ([1,2,3]);

>[2,3] : int list

-(fn nil => nil I hd::tl=>tl)( []);

>nil : int list

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

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

Упражнение 2.5.8 Рассмотрим следующую задачу: сколькими способами можно разменять сумму в £1 монетами достоинством в 1, 2, 5 10 20 и 50 пенсов. Предположим, что мы ввели некоторый порядок на множестве достоинств монет. Очевидно, что тогда выполняется следующее соотношение:

=+ собов разменятьразменять сумму а,разменять сумму a - d,

сумму а исполь-используя все типыиспользуя все n типов

зуя n типов мо-монет, кроме перво-монет (где d есть

нетгодостоинство монеты

первого типа)

Это соотношение может быть преобразовано в рекурсивное определение функции, если добавить случаи, описывающие завершение рекурсии. Именно, если а = 0, имеется ровно 1 способ размена; если а < 0 или n = 0, способов размена нет. Эти замечания позволяют записать следующее определение функции:

fun first denom 1=1 I first denom 2=2 I firstdenom 3=5

I first denom 4 = 10 I first denom 5 = 20 I first denom 6 = 50;

fun cc(0, ) = 1 I cc( ,0) = 0

I cc(amount, kinds) = if amount < 0 then 0

else cc( amount-(first denom kinds), kinds) + cc( amount, (kinds-1));

fun count change amount = cc(amount,6);

Измените этот пример так, чтобы в нем использовался список достоинств монет (вместо функции f irst.denomj.

Упражнение 2.5.9 Приведенный выше алгоритм плох в том смысле, что в нем выполняется много излишних вычислений. Можете ли вы предложить более быстрый алгоритм? (Это непростая задача, и вы можете пропустить ее при первом чтении).

Упражнение 2.5.10 (Ханойские башни) Имеется три стержня (обозначим их A B и С). На, стержень A надето n дисков разного размера так, что внизу находится наибольший, над ним - чуть меньший, и т.д.; наверху находится самый маленький диск. Требуется перенести диски со стержня A на стержень С по следующим правилам: за один ход можно переложить с одного из стержней верхний диск на другой стержень при условии, что перекладываемый диск меньше диска, на который он кладется. Определите функцию, решающую эту задачу.

2.6 Полиморфизм и перегрузка

Имеется одна тонкая, но важная деталь, которую нужно знать для понимания реализации полиморфизма в ML. Напомним, что полиморфным типом мы называем тип, в который входят переменные типа (в противоположность мономорфным типам, в которые такие переменные не входят). В предыдущем разделе мы определили полиморфную функцию как функцию, работающую с аргументами различных типов (из некоторого класса) единообразным способом. Ключевая идея состоит в том, что такую функцию "не интересуют" типы значений (или компонент значений); поэтому она работает независимо от этих значений, и, таким образом, допускает различные типы значений. Например, тип функции append есть a list * a list -> a list, что отражает тот факт, что функция append не интересуется типом элементов списка; единственное,

2.6. ПОЛИМОРФИЗМ И ПЕРЕГРУЗКА

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

Полиморфизм отличается от другого понятия - перегрузки (хотя, на первый взгляд, они схожи). Перегрузка связана со способом записи, а не со способом определения функции. Примером перегрузки может служить функция сложения, обозначаемая +. Мы записываем сложение целых чисел 2 и 3 как 2+3, а сложение действительных чисел 2.0 и 3.0

-как 2.0+3.0. Это может показаться похожим на случаи применения функции append к двум спискам целых чисел и двум спискам действительных чисел. Однако схожесть здесь лишь частичная: одна и та же функция append применяется для соединения списков любого типа, но алгоритм сложения целых чисел отличается от алгоритма сложения действительных чисел. (Если вы знакомы с обычным представлением чисел в компьютере, у вас это не вызовет сомнения). Таким образом, один и тот же символ + используется для обозначения двух различных функций - а не одной полиморфной функции. В каждом конкретном случае выбор функции, которую следует использовать, зависит от типа аргументов.

В этом причина того, что нельзя просто написать fun plus(х,у) = х+у: компилятор должен знать типы х и у, чтобы определить, какая из двух функций сложения должна быть использована - и поэтому он не допускает такого определения. Способ решения этой проблемы состоит в явном указании типа аргументов функции plus; это записывается как fun plus(х:int, у:int) = х+у. Интересный факт состоит в том, что, если бы не было перегруженных функций, то никогда бы не возникала необходимость явно указывать типы10. Но для того, чтобы обеспечить возможность перегрузки, и для того, чтобы повысить надежность программы, ML позволяет вам явно указывать тип конструкции путем приписывания к нему типового выражения. Ниже мы приводим примеры использования явного указания типа:

-fun plus(х,у) = х+у; Unresolvable overloaded identifier: +

-fun plus(x:int,y:int) = x+y;

103a исключением случая использования частичных образцов, как. например, fun

f{x, . . .} = X.