Определение функций с помощью уравнений

Конечно, для того чтобы написать хоть сколь-нибудь полезную программу, необходимо помимо новых идентификаторов для объектов и написания выражений уметь самому определять новые функции. Каждая функция в Haskell — это тоже некоторое значение, для которого определен тип. В типе функции указывают тины ее аргументов и тип значения функции, при этом типы аргументов и значения функции отделяются друг от друга символами так что, например, тип функции одного вещественного аргумента с вещественным результатом (такой, как, например, функция вычисления синуса) можно записать в виде Double -> Double.

а тип функции с двумя целыми аргументами и одним логическим результатом (такой, как, например, операция сравнения двух целых значений по величине) — в виде Int -> Int -> Bool.

Саму функцию можно определить с помощью «уравнения», в котором выясняется, как функция должна себя вести, если ей задать значение аргумента. Например, определим функцию удвоения, которая удваивает значение своего вещественного аргумента и выдает получившееся значение. Для этого зададим идентификатор функции twice, зададим ее тип и напишем уравнение, в котором покажем, что вызов этой функции с заданным значением аргумента эквивалентен выражению, в котором это значение умножается на 2: twice:: Double -> Double twice x = 2 * x.

Запишем нашу простую программу в некоторый файл, скажем, ~/ Haskell/test. hs, и загрузим этот файл в интерпретатор в виде программного модуля. Теперь мы можем использовать загруженную и скомпилированную функцию для удвоения вещественных чисел:

>> :cd ^/Haskell >> :load test. hs >> twice 3.14 6.28.

it:: Double.

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

>> twice 12 24.0.

it:: Double.

Становится понятно, что число 12 здесь рассматривается как вещественное, поскольку контекст выражения twice 12 требует, чтобы аргумент функции twice был вещественным. Здесь есть некоторое отличие от модели, привычной нам при работе с другими языками программирования. Например, в языке Java число 12 рассматривается как целое, а при вызове функции, аргументом которой должно быть вещественное число, неявно добавляется операция преобразования этого числа в вещественное. Здесь же само число 12 может рассматриваться как целое или вещественное в зависимости от контекста.

Вернемся к определению нашей простой функции. В уравнении, определяющем поведение функции twice, можно выделить левую часть, задающую форму вызова функции, и правую часть, в которой записывается выражение, заменяющее вызов функции в тот момент, когда будет задано значение ее аргумента. Если функция twice определена, то вычисление выражения twice 5.5 можно представить следующим образом. Сначала происходит сопоставление фактического значения аргумента 5.5с формальным аргументом х. Затем вызов функции заменяется правой частью уравнения, в которой вместо формального аргумента используется сопоставленное с ним значение фактического аргумента. Таким образом, после сопоставления и замены вместо выражения twice 5.5 получаем выражение 2 * 5.5, которое после вычисления (применения операции умножения) дает значение 11. Процесс преобразования (вычисления) выражения можно записать следующим образом: twice 5.5 —" 2*5.5 —" 11.

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

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

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

if then else

При вычислении условного выражения прежде всего вычисляется условие. Тип вычисленного выражения-условия должен быть логическим (Bool). Если вычисленное значение оказывается истинным (True), то вместо всего условного выражения подставляется выражение-«то», а выражение-«иначе» отбрасывается. Если же, наоборот, условие оказалось ложным (False), то отбрасывается выражение-«то», а вместо всего условного выражения остается только часть, определенная выражением- «иначе».

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

factorial n = if n == 0 then 1 else n * factorial (n-1).

Проследим за тем, как происходит вычисление выражения factorial 3, записывая последовательно все этапы преобразования выражения в соответствии с определением функции factorial (листинг 2.2). Вместо символа —>_f который мы использовали выше для того, чтобы показать один шаг редукции, мы будем просто записывать результаты последовательных редукций в последовательных строках текста.

Листинг 2.2. Процесс преобразования выражения при вычислении факториала числа

factorial 3.

if 3 == 0 then 1 else 3 * factorial 2 if False then 1 else 3 * factorial 2 3 * factorial 2.

• 3 * if 2 == 0 then 1 else 2 * factorial 1 3*2* factorial 1
• 3 * 2 * if 1 == 0 then 1 else 1 * factorial 0 3*2*1* factorial 0
• 3*2*1* if 0==0 then 1 else 0 * factorial (-1) 3 * 2 * 1 * 1 6

Вместо применения условного выражения можно использовать более наглядную запись уравнения с «охраняющими условиями» («сторожами», guards). Выражения-сторожа последовательно проверяются, и в качестве выражения для выполнения редукции выбирается первое из тех, в которых сторож выдал истинное значение условия (листинг 2.3).

Листинг 2.3. Программа вычисления факториала натурального числа.

factorial: Integer -> Integer factorial n | n == 0 = 1.

I n > 0 = n * factorial (n-1).

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

>> factorial (-2).

*** Exception: test. hs: (2,1) — (3,41): Non-exhaustive patterns in function factorial.

Для определения функции можно записать и несколько уравнений, определяющих поведение функции при различных значениях аргумента. Например, можно переопределить функцию вычисления факториала, задав для нее два уравнения, обусловленных выражениями-сторожами, определяющими, какое из двух уравнений на самом деле следует применять: factorial: Integer -> Integer factorial n | n == 0 = 1.

factorial n | n > 0 = n * factorial (n-1).

Если первое уравнение применить не удается (ни один из сторожей не стал истинным для заданного значения аргумента), то проверяется второе уравнение. Рано или поздно либо будет найдено уравнение, в котором один из сторожей «сработает», либо работа функции завершится аварийно.

Еще один способ определения той же функции состоит в том, что в уравнениях, определяющих функцию, можно сразу же задать случай, когда аргументом вызова будет нулевое значение. Определение функции теперь может выглядеть так: factorial: Integer -> Integer factorial 0=1.

factorial n = n * factorial (n-1).

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

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

Определим функцию, которая по заданным натуральным числам определяет их наибольший общий делитель согласно алгоритму Евклида. Назовем эту функцию gcd (greatest common divider — наибольший общий делитель). Идея Евклида состоит в том, что если ни одно из чисел не равно нулю, то наибольший общий делитель таких двух чисел равен наибольшему общему делителю наименьшего из них и остатка от деления большего на меньшее. Поскольку остаток от деления одного натурального числа на другое можно вычислить с помощью стандартной бинарной операции mod, то функцию gcd можно определить следующим образом (листинг 2.4).

Листинг 2.4. Наибольший общий делитель двух чисел

gcd:: Integer -> Integer -> Integer.

• — если первый аргумент меньше второго, то меняем их местами gcd m n | m < n = gcd n m
• — функция определена только для неотрицательных аргументов | п < 0 = error «gcd: Negative argument»
• — собственно алгоритм Евклида: gcd m 0 = m

gcd m n = gcd n (m 'mod' n).

В этом примере использованы различные виды уравнений, определяющих функцию. Стандартная функция error задает «неопределенный результат», выводя при этом в стандартный выходной поток сообщение, являющееся ее аргументом. Если такое неопределенное значение действительно будет получено в результате работы программы, то программа будет завершена аварийно. Эта функция обычно, как и в этом примере, используется для вывода диагностических сообщений и аварийного завершения работы программы в случае неверно заданных аргументов функции.

Замечание. Функция error является примером функции с побочным эффектом, т. е. она не есть «чистая» функция. Язык Haskell содержит помимо чисто функциональных средств также и набор средств, выходящих за рамки собственно функционального программирования. Функция error — это один из примеров применения нефункциональных средств в функциональном языке программирования. Еще один пример функций, обладающих побочным эффектом — функции ввода-вывода данных. Такие функции выделяются особо — гак, чтобы не смешивать.

«чистый» и «нечистый» код. Средство для такого разделения кода мы рассмотрим в гл. 8.

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

" :t gcd.

gcd:: Integral a => a -> a -> a.

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

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

Листинг 2.5. Проверка простоты натурального числа

prime:: Integer -> Bool prime 1 = False prime 2 = True.

prime p | p <= 0 = error «prime: Non-positive argument» .

I p 'mod' 2 == 0 = False | otherwise = prime' 3 p.

• — вспомогательная функция prime' проверяет простоту числа — при условии, что уже проверена его делимость на все числа,
• — меньшие заданного.

prime': Integer -> Integer -> Bool — начинаем проверку с числа 3.

• — рассматриваем три случая, заданные тремя уравнениями:
• — не найдено делителей числа, не превышающих его корня;
• — найден делитель — число не простое;
• — делитель пока не найден, продолжаем проверку, prime' d р | d * d > р = True

I p 'mod' d == 0 = False.

| otherwise = prime' (d+2) p.

В приведенной программе кроме основной функции prime описана вспомогательная функция prime*. Это сделано потому, что рекурсию по основному аргументу функции — проверяемому числу — организовать очень трудно. В то же время при введении дополнительного аргумента, представляющего возможный делитель числа, рекурсия организуется очень легко. Еще одна особенность приведенной программы — использование идентификатора otherwise в качестве условия при написании уравнения для функции prime ¹. Это тождественно истинное условие, так что можно было бы вместо него просто написать True. Специальное слово otherwise используется для большей наглядности (по крайней мере, для программистов, владеющих английским языком; otherwise означает «иначе» или «в противном случае»).

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

>> prime 2 True.

>> prime 25 False.

" prime 31 True.

" prime 222 222 222 222 222 218 493 952 False.