Ещё немного рекурсивных функций

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

Функция replicate

Для начала реализуем функцию replicate. Функция replicate берёт целое число (типа Int) и некоторый элемент и возвращает список, который содержит несколько повторений заданного элемента. На- пример, replicate 3 5 вернёт список [5,5,5]. Давайте обдумаем ба- зовые случаи. Сразу ясно, что возвращать, если число повторений равно нулю или вообще отрицательное — пустой список. Для отри- цательных чисел функция вовсе не имеет смысла.

В общем случае список, состоящий из n повторений элемен- та x, – это список, имеющий «голову» x и «хвост», состоящий из (n- 1)-кратного повторения x. Получаем следующий код:

replicate':: Int –> a –> [a] replicate' n x

| n <= 0 = []

| otherwise = x: replicate' (n–1) x

Мы использовали сторожевые условия вместо образцов пото- му, что мы проверяем булевы выражения.

 

Функция take

Теперь реализуем функцию take. Эта функция берёт определённое количество первых элементов из заданного списка. Например, take 3 [5,4,3,2,1] вернёт список [5,4,3]. Если мы попытаемся по- лучить ноль или менее элементов из списка, результатом будет пус- той список. Если попытаться получить какую-либо часть пустого

 

списка, функция тоже возвратит пустой список. Заметили два базо- вых случая? Ну, давайте это запишем:

take':: (Num i, Ord i) => i –> [a] –> [a] take' n _

| n <= 0 = []

take' _ [] = []

take' n (x:xs) = x: take' (n–1) xs

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

маску. Маска _ используется для сопоставления со списком, потому что сам список нас в данном случае не интересует. Также обратите внимание, что мы применяем охранное выра- жение, но без части otherwise. Это означает, что если значе- ние n будет больше нуля, срав- нение продолжится со следую- щего образца. Второй образец обрабатывает случай, когда мы

пытаемся получить часть пустого списка, – возвращается пустой спи- сок. Третий образец разбивает список на «голову» и «хвост». Затем мы объявляем, что получить n элементов от списка – это то же са- мое, что взять «голову» списка и добавить (n–1) элемент из «хвоста».

 

Функция reverse

Функция reverse обращает список, выстраивая элементы в обрат- ном порядке. И снова пустой список оказывается базовым случаем, потому что если обратить пустой список, получим тот же пустой список. Хорошо... А что насчёт всего остального? Ну, можно ска- зать, что если разбить список на «голову» и «хвост», то обращённый список – это обращённый «хвост» плюс «голова» списка в конце.

reverse':: [a] –> [a] reverse' [] = []

reverse' (x:xs) = reverse' xs ++ [x]

Готово!

 

Функция repeat

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

repeat':: a –> [a] repeat' x = x:repeat' x

Вызов repeat 3 даст нам список, который начинается с тройки и содержит бесконечное количество троек в хвостовой части. Вызов будет вычислен как 3:repeat 3, затем как 3:(3:repeat 3), 3:(3:(3: repeat 3)) и т. д. Вычисление repeat 3 не закончится никогда, а вот take 5 (repeat 3) выдаст нам список из пяти троек. Это то же самое, что вызвать replicate 5 3.

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

 

Функция zip

Функция zip берёт два списка и стыкует их, образуя список пар (по аналогии с тем, как застёгивается замок-молния). Так, например, zip [1,2,3] ['a','b'] вернёт список [(1,'a'),(2,'b')]. При этом более длинный список, как видите, обрезается до длины коротко- го. Ну а если мы состыкуем что-либо с пустым списком? Получим пустой список! Это базовый случай. Но так как функция принима- ет на вход два списка, то на самом деле это два базовых случая.

zip':: [a] –> [b] –> [(a,b)] zip' _ [] = []

zip' [] _ = []

zip' (x:xs) (y:ys) = (x,y):zip' xs ys

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

Например, если мы вызовем zip' со списками [1,2,3] и ['a','b'], то первым элементом результирующего списка ста- нет пара (1, 'a'), и останется склеить списки [2,3] и ['b']. После

 

ещё одного рекурсивного вызова функция попытается склеить [3] и [], что будет сопоставлено с первым образцом. Окончательным результатом теперь будет список (1,'a'):((2,'b'):[]), то есть, по

сути, [(1,'a'),(2,'b')].

Функция elem

Давайте реализуем ещё одну функцию из стандартной библиоте- ки – elem. Она принимает элемент и список и проверяет, есть ли заданный элемент в этом списке. Как обычно, базовый случай — это пустой список. Мы знаем, что в пустом списке нет элементов, так что в нём определённо нет ничего, что мы могли бы искать.

elem':: (Eq a) => a –> [a] –> Bool elem' a [] = False

elem' a (x:xs)

| a == x = True

| otherwise = a `elem'` xs

Довольно просто и ожидаемо. Если «голова» не является иско- мым элементом, мы проверяем «хвост». Если мы достигли пустого списка, то результат – False.

 

Сортируем, быстро!..

Итак, у нас есть список элементов, ко- торые могут быть отсортированы. Их тип – экземпляр класса Ord. А теперь требуется их отсортировать! Для это- го предусмотрен очень классный алго- ритм, называемый быстрой сортировкой (quicksort). Это довольно-таки хитро- умный способ. В то время как его реа- лизация на императивных языках зани- мает многим более 10 строк, на языке Haskell он намного короче и элегант- нее. Настолько, что быстрая сортиров- ка на Haskell стала притчей во языцех. Только ленивый не приводил пример

СОРТИРУЕМ, БЫСТРО! 85

 

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

 

Алгоритм

Итак, сигнатура функции будет следующей:

quicksort:: (Ord a) => [a] –> [a]

Ничего удивительного тут нет. Базовый случай? Пустой спи- сок, как и следовало ожидать. Отсортированный пустой список – это пустой список. Затем следует основной алгоритм: отсортиро- ванный список – это список, в котором все элементы, меньшие либо равные «голове» списка, идут впереди (в отсортированном порядке), посередине следует «голова» списка, а потом – все эле- менты, большие «головы» списка (также отсортированные). За- метьте, в определении мы упомянули сортировку дважды, так что нам, возможно, придётся делать два рекурсивных вызова в теле функции. Также обратите внимание на то, что мы описали ал- горитм, просто дав определение отсортированному списку. Мы не указывали явно: «делай это, затем делай то...» В этом красота функционального программирования! Как нам отфильтровать список, чтобы получить только те элементы, которые больше

«головы» списка, и те, которые меньше? С помощью генерато- ров списков.

Если у нас, скажем, есть список [5,1,9,4,6,7,3] и мы хотим от- сортировать его, этот алгоритм сначала возьмёт «голову», которая равна 5, и затем поместит её в середину двух списков, где хранятся элементы меньшие и большие «головы» списка. То есть в нашем примере получается следующее: [1,4,3] ++ [5] ++ [9,6,7]. Мы зна- ем, что когда список будет отсортирован, число 5 будет находиться на четвёртой позиции, потому что есть три числа меньше и три числа больше 5. Теперь, если мы отсортируем списки [1,4,3] и [9,6,7], то получится отсортированный список! Мы сортируем эти два списка той же самой функцией. Рано или поздно мы достигнем пустого списка, который уже отсортирован – в силу своей пустоты. Проиллюстрируем (цветной вариант рисунка приведён на форзаце книги):

 

 

Элемент, который расположен на своём месте и больше не бу- дет перемещаться, выделен оранжевым цветом. Если вы просмот- рите элементы слева направо, то обнаружите, что они отсорти- рованы. Хотя мы решили сравнивать все элементы с «головами», можно использовать и другие элементы для сравнения. В алго- ритме быстрой сортировки элемент, с которым производится сравнение, называется опорным. На нашей картинке такие отме- чены зелёным цветом. Мы выбрали головной элемент в качест- ве опорного, потому что его легко получить при сопоставлении с образцом. Элементы, которые меньше опорного, обозначены светло-зелёным цветом; элементы, которые больше, – темно-зелё- ным. Желтоватый градиент демонстрирует применение быстрой сортировки.

 

Определение

quicksort:: (Ord a) => [a] –> [a] quicksort [] = []

quicksort (x:xs) =

let smallerSorted = quicksort [a | a <– xs, a <= x] biggerSorted = quicksort [a | a <– xs, a > x]

in smallerSorted ++ [x] ++ biggerSorted

Давайте немного «погоняем» функцию – так сказать, испыта- ем её в действии:

ghci> quicksort [10,2,5,3,1,6,7,4,2,3,4,8,9]

[1,2,2,3,3,4,4,5,6,7,8,9,10]

ДУМАЕМ РЕКУРСИВНО 87

 

ghci> quicksort "съешь ещё этих мягких французских булок, да выпей чаю" ",ааабвгдеееёзииийккклмнопрсстууфхххцчшщъыьэюя"

Ура! Это именно то, чего я хотел!

 

Думаем рекурсивно

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

это первый его элемент, умножен- ный на произведение оставшейся части. Длина списка – это единица плюс длина «хвоста» списка. И так далее, и тому подобное...

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

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

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

 

нуль – нейтральный элемент для сложения. В быстрой сортировке базовый случай – это пустой список; он же является нейтральным элементом, поскольку если присоединить пустой список к некото- рому списку, мы снова получим исходный список.

Итак, пытаясь мыслить рекурсивным образом при решении задачи, попробуйте придумать, в какой ситуации рекурсивное решение не подойдёт, и понять, можно ли использовать этот ва- риант как базовый случай. Подумайте, что является нейтральным элементом, как вы будете разбивать параметры функции (напри- мер, списки обычно разбивают на «голову» и «хвост» путём сопос- тавления с образцом) и для какой части примените рекурсивный вызов.

 

ФУНКЦИИ ВЫСШЕГО

ПОРЯДКА

Функции в языке Haskell могут принимать другие функции как па- раметры и возвращать функции в качестве результата. Если некая функция делает что-либо из вышеперечисленного, её называют функцией высшего порядка (ФВП). ФВП – не просто одна из значитель- ных особенностей характера программирования, присущего языку Haskell, – она по большей части и определяет этот характер. Как вы- ясняется, ФВП незаменимы, если вы хотите программировать ис- ходя из того, что вы хотите получить, вместо того чтобы продумы- вать последовательность шагов, описывающую, как это получить. Это очень мощный способ решения задач и разработки программ.

 

Каррированные функции

Каждая функция в языке Haskell официаль- но может иметь только один параметр. Но мы определяли и использовали функции, которые принимали несколько параметров. Как же такое может быть? Да, это хитрый трюк! Все функции, которые принимали несколько параметров, были каррированы. Функция называется каррированной, если она всегда принимает только один параметр вместо нескольких. Если потом её вызвать,

 

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

Легче всего объяснить на примере. Возьмём нашего старого друга – функцию max. Если помните, она принимает два параметра и возвращает максимальный из них. Если сделать вызов max 4 5, то вначале будет создана функция, которая принимает один пара- метр и возвращает 4 или поданный на вход параметр – смотря что больше. Затем значение 5 передаётся в эту новую функцию, и мы получаем желаемый результат. В итоге оказывается, что следующие два вызова эквивалентны:

ghci> max 4 5

ghci> (max 4) 5

5

Чтобы понять, как это работает, давайте посмотрим на тип фун- кции max:

ghci>:t max

max:: (Ord a) => a –> a –> a

То же самое можно записать иначе:

max:: (Ord a) => a –> (a –> a)

Прочитать запись можно так: функция max принимает параметр типа a и возвращает (–>) функцию, которая принимает параметр ти- па a и возвращает значение типа a. Вот почему возвращаемый фун- кцией тип и параметры функции просто разделяются стрелками.

Ну и чем это выгодно для нас? Проще говоря, если мы вызы-

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

 

новых функций «на лету»: мы можем передать их другой функции или передать им ещё какие-нибудь параметры.

Посмотрим на эту простую функцию:

multThree:: Int -> Int -> Int -> Int multThree x y z = x * y * z

Что происходит, если мы вызываем multThree 3 5 9 или ((multThree 3) 5) 9? Сначала значение 3 применяется к multThree, так как они разделены пробелом. Это создаёт функцию, которая при- нимает один параметр и возвращает новую функцию, умножающую на 3. Затем значение 5 применяется к новой функции, что даёт фун- кцию, которая примет параметр и умножит его уже на 15. Значение 9 применяется к этой функции, и получается результат 135. Вы мо- жете думать о функциях как о маленьких фабриках, которые берут какие-то материалы и что-то производят. Пользуясь такой аналоги- ей, мы даём фабрике multThree число 3, и, вместо того чтобы выдать число, она возвращает нам фабрику немного поменьше. Эта новая фабрика получает число 5 и тоже выдаёт фабрику. Третья фабри- ка при получении числа 9 производит, наконец, результат — чис- ло 135. Вспомним, что тип этой функции может быть записан так:

multThree:: Int -> (Int -> (Int -> Int))

Перед символом –> пишется тип параметра функции; после записывается тип значения, которое функция вернёт. Таким об- разом, наша функция принимает параметр типа Int и возвращает функцию типа Int -> (Int –> Int). Аналогичным образом эта новая функция принимает параметр типа Int и возвращает функцию типа Int -> Int. Наконец, функция принимает параметр типа Int и возвращает значение того же типа Int.

Рассмотрим пример создания новой функции путём вызова функции с недостаточным числом параметров:

ghci> let multTwoWithNine = multThree 9 ghci> multTwoWithNine 2 3

54

В этом примере выражение multThree 9 возвращает функ- цию, принимающую два параметра. Мы называем эту функцию multTwoWithNine. Если при её вызове предоставить оба необходимых

 

параметра, то она перемножит их между собой, а затем умножит произведение на 9.

Вызывая функции не со всеми параметрами, мы создаём новые функции «на лету». Допустим, нужно создать функцию, которая принимает число и сравнивает его с константой 100. Можно сде- лать это так:

compareWithHundred:: Int -> Ordering compareWithHundred x = compare 100 x

Если мы вызовем функцию с 99, она вернёт значение GT. Доволь- но просто. Обратите внимание, что параметр х находится с правой стороны в обеих частях определения. Теперь подумаем, что вернёт выражение compare 100. Этот вызов вернёт функцию, которая при- нимает параметр и сравнивает его с константой 100. Ага-а! Не этого ли мы хотели? Можно переписать функцию следующим образом:

compareWithHundred:: Int -> Ordering compareWithHundred = compare 100

Объявление типа не изменилось, так как выражение compare 100 возвращает функцию. Функция compare имеет тип (Ord a) => a –> (a –> Ordering). Когда мы применим её к 100, то получим функцию, при- нимающую целое число и возвращающую значение типа Ordering.

 

Сечения

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

divideByTen:: (Floating a) => a –> a divideByTen = (/10)

Вызов, скажем, divideByTen 200 эквивалентен вызову 200 / 10, равно как и (/10) 200:

ghci> divideByTen 200

20.0

 

ghci> 200 / 10

20.0

ghci> (/10) 200

20.0

А вот функция, которая проверяет, находится ли переданный символ в верхнем регистре:

isUpperAlphanum:: Char –> Bool isUpperAlphanum = (`elem` ['А'..'Я'])

Единственная особенность при использовании сечений – при- менение знака «минус». По определению сечений, (–4) – это функ- ция, которая вычитает четыре из переданного числа. В то же время для удобства (–4) означает «минус четыре». Если вы хотите создать функцию, которая вычитает четыре из своего аргумента, выпол- няйте частичное применение таким образом: (subtract 4).

 

Печать функций

До сих пор мы давали частично применённым функциям имена, после чего добавляли недостающие параметры, чтобы всё-таки посмотреть на результаты. Однако мы ни разу не попробовали на- печатать сами функции. Попробуем? Что произойдёт, если мы поп- робуем выполнить multThree 3 4 в GHCi вместо привязки к имени с помощью ключевого слова let либо передачи другой функции?

ghci> multThree 3 4

<interactive>:1:0:

No instance for (Show (a –> a))

arising from a use of `print' at <interactive>:1:0–12 Possible fix: add an instance declaration for (Show (a –> a)) In the expression: print it

In a 'do' expression: print it

GHCi сообщает нам, что выражение порождает функцию типа a –> a, но он не знает, как вывести её на экран. Функции не име- ют экземпляра класса Show, так что мы не можем получить точное строковое представление функций. Когда мы вводим, скажем, 1 + 1 в терминале GHCi, он сначала вычисляет результат (2), а затем вызы- вает функцию show для 2, чтобы получить текстовое представление

 

этого числа. Текстовое представление 2 – это строка "2", которая и выводится на экран.

ПРИМЕЧАНИЕ. Удостоверьтесь в том, что вы поняли, как рабо- тает каррирование и частичное применение функций, поскольку эти понятия очень важны.

Немного о высоких материях

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

applyTwice:: (a –> a) –> a –> a applyTwice f x = f (f x)

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

ление в каррированном стиле, но, чтобы избежать головной боли, просто скажем, что функция принимает два параметра и возвра- щает результат. Первый параметр – это функция (она имеет тип a –> a), второй параметр имеет тот же тип a. Заметьте, что совер- шенно неважно, какому типу будет соответствовать типовая пере- менная a – Int, String или вообще чему угодно – но при этом все значения должны быть одного типа.

ПРИМЕЧАНИЕ. Отныне мы будем говорить, что функция прини- мает несколько параметров, вопреки тому что в действительности каждая функция принимает только один параметр и возвращает

частично применённую функцию. Для простоты будем говорить, что a –> a –> a принимает два параметра, хоть мы и знаем, что происходит «за кулисами».

Тело функции applyTwice достаточно простое. Мы используем параметр f как функцию, применяя её к параметру x (для этого раз- деляем их пробелом), после чего передаём результат снова в функ- цию f. Давайте поэкспериментируем с функцией:

ghci> applyTwice (+3) 10

ghci> applyTwice (++ " ХА-ХА") "ЭЙ" "ЭЙ ХА-ХА ХА-ХА"

ghci> applyTwice ("ХА-ХА " ++) "ЭЙ" "ХА-ХА ХА-ХА ЭЙ"

ghci> applyTwice (multThree 2 2) 9

ghci> applyTwice (3:) [1]

[3,3,1]

Красота и полезность частичного применения очевидны. Если наша функция требует передать ей функцию одного аргумента, мы можем частично применить функцию-параметр таким образом, чтобы оставался неопределённым всего один параметр, и затем передать её нашей функции. Например, функция + принимает два параметра; с помощью сечений мы можем частично применить её так, чтобы остался только один.

 

Реализация функции zipWith

Теперь попробуем применить ФВП для реализации очень полез- ной функции из стандартной библиотеки. Она называется zipWith. Эта функция принимает функцию и два списка, а затем соединяет списки, применяя переданную функцию для соответствующих эле- ментов. Вот как мы её реализуем:

zipWith':: (a –> b –> c) –> [a] –> [b] –> [c] zipWith' _ [] _ = []

zipWith' _ _ [] = []

zipWith' f (x:xs) (y:ys) = f x y: zipWith' f xs ys

Посмотрите на объявление типа. Первый параметр – это функ- ция, которая принимает два значения и возвращает одно. Пара-

 

метры этой функции не обязательно должны быть одинакового типа, но могут. Второй и третий параметры – списки. Результат тоже является списком. Первым идёт список элементов типа а, потому что функция сцепления принимает значение типа а в качестве пер- вого параметра. Второй должен быть списком из элементов типа b, потому что второй параметр у связывающей функции имеет тип b. Результат – список элементов типа c. Если объявление функции гово- рит, что она принимает функцию типа a –> b –> c как параметр, это оз- начает, что она также примет и функцию a –> a –> a, но не наоборот.

ПРИМЕЧАНИЕ. Запомните: когда вы создаёте функции, особен- но высших порядков, и не уверены, каким должен быть тип, вы мо- жете попробовать опустить объявление типа, а затем проверить, какой тип выведет язык Haskell, используя команду:t в GHCi.

Устройство данной функции очень похоже на обычную функ- цию zip. Базовые случаи одинаковы. Единственный дополнитель- ный аргумент – соединяющая функция, но он не влияет на базовые случаи; мы просто используем для него маску подстановки _. Тело функции в последнем образце также очень похоже на функцию zip – разница в том, что она не создаёт пару (x, y), а возвращает f x y. Одна функция высшего порядка может использоваться для решения множества задач, если она достаточно общая. Покажем на небольшом примере, что умеет наша функция zipWith':

ghci> zipWith' (+) [4,2,5,6] [2,6,2,3]

[6,8,7,9]

ghci> zipWith' max [6,3,2,1] [7,3,1,5]

[7,3,2,5]

ghci> zipWith' (++) ["шелдон ", "леонард "] ["купер", "хофстадтер"] ["шелдон купер","леонард хофстадтер"]

ghci> zipWith' (*) (replicate 5 2) [1..]

[2,4,6,8,10]

ghci> zipWith' (zipWith' (*)) [[1,2,3],[3,5,6],[2,3,4]] [[3,2,2],[3,4,5],[5,4,3]]

[[3,4,6],[9,20,30],[10,12,12]]

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

 

Реализация функции flip

Теперь реализуем ещё одну функцию из стандартной библиотеки,

flip. Функция flip принимает функцию и возвращает функцию.

 

Единственное отличие результирующей функции от исходной – первые два параметра переставлены местами. Мы можем реализо- вать flip следующим образом:

flip':: (a –> b –> c) –> (b –> a –> c) flip' f = g

where g x y = f y x

Читая декларацию типа, мы видим, что функция принимает на вход функцию с параметрами типов а и b и возвращает функцию с параметрами b и a. Так как все функции на самом деле каррирова- ны, вторая пара скобок не нужна, поскольку символ –> правоассо- циативен. Тип (a –> b –> c) –> (b –> a –> c) – то же самое, что и тип (a –> b –> c) –> (b –> (a –> c)), а он, в свою очередь, представляет то же самое, что и тип (a –> b –> c) –> b –> a –> c. Мы записали, что g x y = f y x. Если это верно, то верно и следующее: f y x = g x y. Де- ржите это в уме – мы можем реализовать функцию ещё проще.

flip':: (a –> b –> c) –> b –> a –> c flip' f y x = f x y

Здесь мы воспользовались тем, что функции каррированы. Ког- да мы вызываем функцию flip' f без параметров y и x, то получаем функцию, которая принимает два параметра, но переставляет их при вызове. Даже несмотря на то, что такие «перевёрнутые» фун- кции обычно передаются в другие функции, мы можем воспользо- ваться преимуществами каррирования при создании ФВП, если подумаем наперёд и запишем, каков будет конечный результат при вызове полностью определённых функций.

ghci> zip [1,2,3,4,5,6] "привет" [(1,'п'),(2,'р'),(3,'и'),(4,'в'),(5,'е'),(6,'т')]

ghci> flip' zip [1,2,3,4,5] "привет" [('п',1),('р',2),('и',3),('в',4),('е',5),('т',6)]

ghci> zipWith div [2,2..] [10,8,6,4,2]

[0,0,0,0,1]

ghci> zipWith (flip' div) [2,2..] [10,8,6,4,2]

[5,4,3,2,1]

Если применить функцию flip' к zip, то мы получим функцию, похожую на zip, за исключением того что элементы первого списка будут оказываться вторыми элементами пар результирующего спис- ка, и наоборот. Функция flip' div делит свой второй параметр на

 

первый, так что если мы передадим ей числа 2 и 10, то результат будет такой же, что и в случае div 10 2.