Инструментарий функционального программиста 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Инструментарий функционального программиста



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

 

Функция map

 
 

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

map:: (a –> b) –> [a] –> [b] map _ [] = []

 
 

map f (x:xs) = f x: map f xs

Сигнатура функции говорит нам, что функция map принимает на вход функцию, которая вычисляет значение типа b по параметру типа a, список элементов типа a и возвращает список элементов типа b. Интересно, что глядя на сигнатуру функции вы уже можете сказать, что она делает. Функция map – одна из самых универсаль- ных ФВП, и она может использоваться миллионом разных спосо- бов. Рассмотрим её в действии:

ghci> map (+3) [1,5,3,1,6]

[4,8,6,4,9]

ghci> map (++ "!") ["БУХ", "БАХ", "ПАФ"]

["БУХ!","БАХ!","ПАФ!"]

ghci> map (replicate 3) [3..6]

[[3,3,3],[4,4,4],[5,5,5],[6,6,6]]

ghci> map (map (^2)) [[1,2],[3,4,5,6],[7,8]]

[[1,4],[9,16,25,36],[49,64]]

 
 

ghci> map fst [(1,2),(3,5),(6,3),(2,6),(2,5)] [1,3,6,2,2]


 

Возможно, вы заметили, что нечто аналогичное можно сделать с помощью генератора списков. Вызов map (+3) [1,5,3,1,6] – это то же самое, что и [x+3 | x <– [1,5,3,1,6]]. Тем не менее использование функции map обеспечивает более читаемый код в случаях, когда вы просто применяете некоторую функцию к списку. Особенно когда применяются отображения к отображениям (map – к результатам выполнения функции map): тогда всё выражение с кучей скобок мо- жет стать нечитаемым.

 

Функция filter

 
 

Функция filter принимает предикат и список, а затем возвращает список элементов, удовлетворяющих предикату. Предикат – это фун- кция, которая говорит, является ли что-то истиной или ложью, – то есть функция, возвращающая булевское значение. Сигнатура функ- ции и её реализация:

filter:: (a –> Bool) –> [a] –> [a] filter _ [] = []

filter p (x:xs)

| p x = x: filter p xs

 
 

| otherwise = filter p xs

Довольно просто. Если выражение p x истинно, то элемент до- бавляется к результирующему списку. Если нет – элемент пропуска- ется.

 
 

Несколько примеров:

ghci> filter (>3) [1,5,3,2,1,6,4,3,2,1]

[5,6,4]

ghci> filter (==3) [1,2,3,4,5]

[3]

ghci> filter even [1..10] [2,4,6,8,10]

ghci> let notNull x = not (null x) in filter notNull [[1],[],[3,4],[]] [[1],[3,4]]

ghci> filter (`elem` ['а'..'я']) "тЫ СМЕЕШЬСя, ВЕДЬ я ДрУГой" "тяярой"

 
 

ghci> filter (`elem` ['А'..'Я']) "я Смеюсь, Ведь ты такОЙ же" "СВОЙ"

Того же самого результата можно достичь, используя генера-


 

 
 

торы списков и предикаты. Нет какого-либо правила, диктующего вам, когда использовать функции map и filter, а когда – генераторы списков. Вы должны решить, что будет более читаемым, основыва- ясь на коде и контексте. В генераторах списков можно применять несколько предикатов; при использовании функции filter придёт- ся проводить фильтрацию несколько раз или объединять предика- ты с помощью логической функции &&. Вот пример:

ghci> filter (<15) (filter even [1..20])

 
 

[2,4,6,8,10,12,14]

Здесь мы берём список [1..20] и фильтруем его так, чтобы ос- тались только чётные числа. Затем список передаётся функции filter (<15), которая избавляет нас от чисел 15 и больше. Вот вер- сия с генератором списка:

 
 

ghci> [ x | x <- [1..20], x < 15, even x] [2,4,6,8,10,12,14]

Мы используем генератор для извлечения элементов из спис- ка [1..20], а затем указываем условия, которым должны удовлетво- рять элементы результирующего списка.

 
 

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

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

quicksort (x:xs) =

let smallerSorted = quicksort (filter (<= x) xs) biggerSorted = quicksort (filter (> x) xs)

 
 

in smallerSorted ++ [x] ++ biggerSorted

 

Ещё немного примеров использования map и filter

Давайте найдём наибольшее число меньше 100 000, которое делит- ся на число 3829 без остатка. Для этого отфильтруем множество возможных вариантов, в которых, как мы знаем, есть решение.


 

largestDivisible:: Integer

 
 

largestDivisible = head (filter p [100000,99999..]) where p x = x `mod` 3829 == 0

Для начала мы создали список всех чисел меньших 100 000 в по- рядке убывания. Затем отфильтровали список с помощью предика- та. Поскольку числа отсорти-

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

в действии»! Поскольку мы используем только «голову» списка, нам неважно, конечен полученный список или бесконечен. Вычисления прекращаются, как только находится первое подходящее решение. Теперь мы собираемся найти сумму всех нечётных квадратов меньших 10 000. Но для начала познакомимся с функцией takeWhile: она пригодится в нашем решении. Она принимает предикат и спи- сок, а затем начинает обход списка с его «головы», возвращая те его элементы, которые удовлетворяют предикату. Как только найден элемент, не удовлетворяющий предикату, обход останавливается. Если бы мы хотели получить первое слово строки "слоны умеют веселиться", мы могли бы сделать такой вызов: takeWhile (/=' ')

"слоны умеют веселиться", и функция вернула бы "слоны".

Итак, в первую очередь начнём применять функцию (2) к бес- конечному списку [1..]. Затем отфильтруем список, чтобы в нём были только нечётные элементы. Далее возьмём из него значения, меньшие 10000. И, наконец, получим сумму элементов этого списка. Нам даже не нужно задавать для этого функцию – достаточно будет одной строки в GHCi:

 
 

ghci> sum (takeWhile (<10000) (filter odd (map (2) [1..]))) 166650

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


 

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

 
 

ghci> sum (takeWhile (<10000) [m | m <– [n 2 | n <– [1..]], odd m]) 166650

В следующей задаче мы будем иметь дело с рядами Коллатца. Берём натуральное число. Если это число чётное, делим его на два. Если нечётное – умножаем его на 3 и прибавляем единицу. Берём получившееся значение и снова повторяем всю процедуру, получа- ем новое число, и т. д. В сущности, у нас получается цепочка чи- сел. С какого бы значения мы ни начали, цепочка заканчивается на единице. Если бы начальным значением было 13, мы бы получили такую последовательность: 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Всё по вы-

шеприведенной схеме: 13 × 3 + 1 равняется 40; 40, разделённое на 2, равно 20, и т. д. Как мы видим, цепочка имеет 10 элементов.

 
 

Теперь требуется выяснить: если взять все стартовые числа от 1 до 100, как много цепочек имеют длину больше 15? Для начала на- пишем функцию, которая создаёт цепочку:

chain:: Integer -> [Integer] chain 1 = [1]

chain n

| even n = n:chain (n `div` 2)

 
 

| odd n = n:chain (n*3 + 1)

Так как цепочка заканчивается на единице, это базовый случай.

 
 

Получилась довольно-таки стандартная рекурсивная функция.

ghci> chain 10

[10,5,16,8,4,2,1]

ghci> chain 1

[1]

ghci> chain 30

 
 

[30,15,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]

Так! Вроде бы работает правильно. Ну а теперь функция, кото- рая ответит на наш вопрос:

numLongChains:: Int

 
 

numLongChains = length (filter isLong (map chain [1..100])) where isLong xs = length xs > 15


 

Мы применяем функцию chain к списку [1..100], чтобы полу- чить список цепочек; цепочки также являются списками. Затем фильтруем их с помощью предиката, который проверяет длину цепочки. После фильтрации смотрим, как много цепочек осталось в результирующем списке.

ПРИМЕЧАНИЕ. Эта функция имеет тип numLongChains:: Int, по- тому что length возвращает значение типа Int вместо экземпляра класса Num – так уж сложилось исторически. Если мы хотим вер- нуть более общий тип, имеющий экземпляр класса Num, нам надо применить функцию fromIntegral к результату, возвращённому функцией length.

Функция map

для функций нескольких переменных

 
 

Используя функцию map, можно проделывать, например, такие шту- ки: map (*) [0..] – если не для какой-либо практической цели, то хотя бы для того, чтобы продемонстрировать, как работает карри- рование, и показать, что функции (частично применённые) – это настоящие значения, которые можно передавать в другие функции илипомещатьвсписки(нонельзяпредставлятьввидестрок). Досих пор мы применяли к спискам только функции с одним параметром, вроде map (*2) [0..], чтобы получить список типа (Num a) => [a], но с темжеуспехом можемиспользовать(*)[0..] безовсякихпроблем. При этом числа в списке будут применены к функции *, тип которой (Num a)=> a –> a –> a. Применениетолькоодногопараметрак функции двухпараметроввозвращаетфункциюодногопараметра. Применив оператор * к списку [0..], мы получаем список функций, которые принимают только один параметр, а именно (Num a) => [a –> a]. Список, возвращаемый выражением map (*) [0..], также можно получить, записав [(0*),(1*),(2*),(3*),(4*),(5*)...

ghci> let listOfFuns = map (*) [0..] ghci> (listOfFuns!! 4) 5

 
 

20

Элемент с номером четыре из списка содержит функцию, кото- рая выполняет умножение на четыре – (4*). Затем мы применяем значение 5 к этой функции. Это то же самое, что записать (4*) 5 или просто 4 * 5.


 

Лямбда-выражения

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

кую букву лямбда – l), затем записываем параметры, разделяя их пробелами. Далее пишем знак –> и тело функции. Обычно мы за- ключаем лямбду в круглые скобки, иначе она продолжится до конца строки вправо.

 
 

Если вы обратитесь к примеру, приведенному в предыдущем разделе, то увидите, что мы создали функцию isLong в секции where функции numLongChains только для того, чтобы передать её в фильтр. Вместо этого можно использовать анонимную функцию:

numLongChains:: Int

 
 

numLongChains = length (filter (\xs –> length xs > 15) (map chain [1..100]))

Анонимные функции являются выражениями, поэтому мы можем использовать их таким способом, как в примере. Выражение (\xs –> length xs > 15) возвращает функцию, которая говорит нам, больше ли 15 длина переданного списка.

Те, кто не очень хорошо понима- ет, как работает каррирование и час-

тичное применение функций, часто используют анонимные функ- ции там, где не следует. Например, выражения map (+3) [1,6,3,2] и map (\x –> x + 3) [1,6,3,2] эквивалентны, так как (+3) и (\x –> x + 3) – этофункции, которыедобавляют тройку к аргументу. Излишне гово- рить, чтоиспользованиеанонимнойфункциивэтомслучаенеоправ- данно, так как частичное применение значительно легче читается.


ЛЯМБДА-ВЫРАЖЕНИЯ 105

 
 

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

ghci> zipWith (\a b –> (a * 30 + 3) / b) [5,4,3,2,1] [1,2,3,4,5] [153.0,61.5,31.0,15.75,6.6]

 
 

По аналогии с обычными функциями, можно выполнять сопос- тавление с образцом в лямбда-выражениях. Единственное отличие в том, что нельзя определить несколько образцов для одного пара- метра – например, записать для одного параметра образцы [] и (x: xs) и рассчитывать, что выполнение перейдёт к образцу (x:xs) в случае неудачи с []. Если сопоставление с образцом в анонимной функции заканчивается неудачей, происходит ошибка времени вы- полнения, так что поосторожнее с этим!

ghci> map (\(a,b) –> a + b) [(1,2),(3,5),(6,3),(2,6),(2,5)] [3,8,9,8,7]

 
 

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

addThree:: Int -> Int -> Int -> Int addThree x y z = x + y + z

 

 
 

addThree':: Int -> Int -> Int -> Int addThree' = \x -> \y -> \z -> x + y + z

Если мы объявим функцию подобным образом, то станет понят- но, почему декларация типа функции представлена именно в таком виде. И в декларации типа, и в теле функции имеются три симво- ла –>. Конечно же, первый способ объявления функций значитель- но легче читается; второй – это всего лишь очередная возможность продемонстрировать каррирование.

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


 
 

Тем не менее есть случаи, когда использование такой нотации оправдано. Я думаю, что функция flip будет лучше читаться, если мы объявим её так:

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

 
 

Несмотря на то что эта запись равнозначна flip' f x y = f y x, мы даём понять, что данная функция чаще всего используется для создания новых функций. Самый распространённый сценарий ис- пользования flip – вызов её с некоторой функцией и передача ре- зультирующей функции в map или zipWith:

ghci> zipWith (flip (++)) ["люблю тебя", "любишь меня"] ["я ", "ты "] ["я люблю тебя","ты любишь меня"]

ghci> map (flip subtract 20) [1,2,3,4]

 
 

[19,18,17,16]

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

 

Я вас сверну!

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

ками (folds). Свёртки позволяют свести структуру данных (напри- мер, список) к одному значению.

Функция свёртки принимает бинарную функцию, начальное значение (мне нравится называть его «аккумулятором») и список.


 

Бинарная функция принимает два параметра. Она вызывается с ак- кумулятором и первым (или последним) элементом из списка и вы- числяет новое значение аккумулятора. Затем функция вызывается снова, с новым значением аккумулятора и следующим элементом из списка, и т. д. То, что остаётся в качестве значения аккумулятора после прохода по всему списку, и есть результат свёртки.

 

Левая свёртка foldl

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

 
 

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

sum':: (Num a) => [a] –> a

 
 

sum' xs = foldl (\acc x –> acc + x) 0 xs

Проверка – раз, два, три!

ghci> sum' [3,5,2,1]

 
 

11

Давайте посмотрим более внима- тельно, как работает функция foldl. Би- нарная функция – это лямбда-выражение (\acc x –> acc + x), нуль – стартовое зна- чение, и xs – список. В самом начале нуль используется как значение аккумулято- ра, а 3 – как значение образца x (текущий элемент). Выражение (0+3) в результате даёт 3; это становится новым значением аккумулятора. Далее, 3 используется как значение аккумулятора и 5 – как текущий элемент; новым значением аккумулятора становится 8. На следующем шаге 8 – зна-

чение аккумулятора, 2 – текущий элемент, новое значение аккуму- лятора становится равным 10. На последнем шаге 10 из аккумуля- тора и 1 как текущий элемент дают 11. Поздравляю – вы только что выполнили свёртку списка!


 

 
 

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

sum':: (Num a) => [a] –> a sum' = foldl (+) 0

Анонимная функция (\acc x –> acc + x) – это то же самое, что и оператор (+). Мы можем пропустить xs в параметрах, потому что вызов foldl (+) 0 вернёт функцию, которая принимает список. В об- щем, если у вас есть функция вида foo a = bar b a, вы всегда можете переписать её как foo = bar b, так как происходит каррирование.

 
 

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

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

 
 

elem' y ys = foldl (\acc x –> if x == y then True else acc) False ys

Что мы имеем? Стартовое значение и аккумулятор – булевские значения. Тип аккумулятора и стартового значения в свёртках всегда совпадают. Запомните это правило: оно может подсказать вам, что следует использовать в качестве стартового значения, если вы затруд- няетесь. В данном случае мы начинаем со значения False. В этом есть смысл: предполагается, что в списке нет искомого элемента. Если мы вызовем функцию свёртки с пустым списком, то результатом бу- дет стартовое значение. Затем мы проверяем текущий элемент на ра- венство искомому. Если это он – устанавливаем в True. Если нет – не изменяем аккумулятор. Если он прежде был равен значению False, то остаётся равным False, так как текущий элемент – не искомый. Если же был равен True, мы опять-таки оставляем его неизменным.

 

Правая свёртка foldr

Правая свёртка, foldr, работает аналогично левой, только аккумуля- тор поглощает значения, начиная справа. Бинарная функция левой


 

свёртки принимает аккумулятор как первый параметр, а текущее значение – как второй (\acc x –>...); бинарная функция правой свёр- тки принимает текущее значение как первый параметр и аккумуля- тор – как второй (\x acc –>...). То, что аккумулятор находится с пра- вой стороны, в некотором смысле логично, поскольку он поглощает значения из списка справа.

 
 

Значение аккумулятора (и, следовательно, результат) функции foldr могут быть любого типа. Это может быть число, булевское значение или даже список. Мы реализуем функцию map с помощью правой свёртки. Аккумулятор будет списком; будем накапливать пе- ресчитанные элементы один за другим. Очевидно, что начальным элементом является пустой список:

map':: (a –> b) –> [a] –> [b]

 
 

map' f xs = foldr (\x acc –> f x: acc) [] xs

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

 
 

Конечно, можно было бы реализовать эту функцию и при помо- щи левой свёртки:

map':: (a -> b) -> [a] -> [b]

 
 

map' f xs = foldl (\acc x –> acc ++ [f x]) [] xs

Но операция конкатенации ++ значительно дороже, чем конс- труктор списка:, так что мы обычно используем правую свёртку, когда строим списки из списков.

Если вы обратите список задом наперед, то сможете выполнять правую свёртку с тем же результатом, что даёт левая свёртка, и на- оборот. В некоторых случаях обращать список не требуется. Функ- цию sum можно реализовать как с помощью левой, так и с помощью правой свёртки. Единственное серьёзное отличие: правые свёртки работают на бесконечных списках, а левые – нет! Оно и понятно:


 

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

Свёртки могут быть исполь- зованы для реализации любой

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

 

Функции foldl1 и foldr1

 
 

Функции foldl1 и foldr1 работают примерно так же, как и функ- ции foldl и foldr, только нет необходимости явно задавать стар- товое значение. Они предполагают, что первый (или последний) элемент списка является стартовым элементом, и затем начинают свёртку со следующим элементом. Принимая это во внимание, фун- кцию maximum можно реализовать следующим образом:

maximum':: (Ord a) => [a] -> a maximum' = foldl1 max

Мы реализовали функцию maximum, используя foldl1. Вместо использования начального значения функция foldl1 предполага- ет, что таковым является первый элемент списка, после чего пе- ремещается к следующему. Поэтому всё, что ей необходимо, – это бинарная функция и сворачиваемый лист! Мы начинаем с «голо- вы» списка и сравниваем каждый элемент с аккумулятором. Если элемент больше аккумулятора, мы сохраняем его в качестве нового значения аккумулятора; в противном случае сохраняем старое. Мы

 
 

1 Это так. В качестве упражнения повышенной сложности читателю рекоменду- ется реализовать при помощи свёртки функции drop и dropWhile из стандартной библиотеки. – Прим. ред.


передаём функцию max в качестве параметра foldl1, поскольку она ровно это и делает: берёт два значения и возвращает большее. К мо- менту завершения свёртки останется самый большой элемент.

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

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

 

Примеры свёрток

 
 

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

reverse':: [a] -> [a]

 
 

reverse' = foldl (\acc x -> x: acc) []

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

 
 

Функция \acc x -> x: acc – почти то же, что и операция:, за исключением порядка следования параметров. Поэтому функцию reverse' можно переписать и так:

reverse':: [a] -> [a]

 
 

reverse' = foldl (flip (:)) []

Теперь реализуем функцию product:

 
 

product':: (Num a) => [a] -> a product' = foldl (*) 1

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

Вот реализация функции filter:


 

filter':: (a -> Bool) -> [a] -> [a]

 
 

filter' p = foldr (\x acc -> if p x then x: acc else acc) []

Здесь начальное значение аккумулятора является пустым спис- ком. Мы сворачиваем список справа налево и проверяем каждый элемент, пользуясь предикатом p. Если p x возвращает истину, эле- мент x помещается в начало аккумулятора. В противном случае ак- кумулятор остаётся без изменения.

 
 

Напоследок реализуем функцию last:

last':: [a] -> a

 
 

last' = foldl1 (\ x -> x)

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

 

Иной взгляд на свёртки

 
 

Есть ещё один способ представить работу правой и левой свёртки. Скажем, мы выполняем правую свёртку с бинарной функцией f и стартовым значением z. Если мы применяем правую свёртку к списку [3,4,5,6], то на самом деле вычисляем вот что:

f 3 (f 4 (f 5 (f 6 z)))

 
 

Функция f вызывается с последним элементом в списке и акку- мулятором; получившееся значение передаётся в качестве аккуму- лятора при вызове функции с предыдущим значением, и т. д. Если мы примем функцию f за операцию сложения и начальное значе- ние за нуль, наш пример преобразуется так:

3 + (4 + (5 + (6 + 0)))

 
 

Или, если записать оператор + как префиксную функцию, по- лучится:

(+) 3 ((+) 4 ((+) 5 ((+) 6 0)))


 

Аналогичным образом левая свёртка с бинарной функцией g

 
 

и аккумулятором z является эквивалентом выражения

g (g (g (g z 3) 4) 5) 6

 
 

Если заменить бинарную функцию на flip (:) и использовать [] как аккумулятор (выполняем обращение списка), подобная запись эквивалентна следующей:

flip (:) (flip (:) (flip (:) (flip (:) [] 3) 4) 5) 6

Если вычислить это выражение, мы получим [6,5,4,3].

 

Свёртка бесконечных списков

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

 
 

Функция and принимает список значений типа Bool и возвраща- ет False, если хотя бы один из элементов равен False; в противном случае она возвращает True. Мы будем обходить список справа, ис- пользуя True как начальное значение. В качестве бинарной функции будем использовать операцию &&, потому что должны вернуть True только в том случае, когда все элементы списка истинны. Функция && возвращает False, если хотя бы один из параметров равен False, поэтому если мы встретим в списке False, то аккумулятор будет ус- тановлен в значение False и окончательный результат также будет False, даже если среди оставшихся элементов списка обнаружатся истинные значения.

and':: [Bool] -> Bool

 
 

and' xs = foldr (&&) True xs

Зная, как работает foldr, мы видим, что выражение and' [True,False,True] будет вычисляться следующим образом:

 
 

True && (False && (True && True))


 

Последнее True здесь – это начальное значение аккумулято- ра, тогда как первые три логических значения взяты из списка [True,False,True]. Если мы попробуем вычислить результат этого выражения, получится False.

 
 

А что если попробовать то же самое с бесконечным списком, скажем, repeat False? Если мы выпишем соответствуюшие приме- нения, то получится вот что:

False && (False && (False && (False …

Ленивость Haskell позволит вычислить только то, что действи- тельно необходимо. Функция && устроена таким образом, что если её первый параметр False, то второй просто игнорируется, пос- кольку и так ясно, что результат должен быть False.

Функция foldr будет работать с бесконечными списками, если бинарная функция, которую мы ей передаём, не требует обязатель- ного вычисления второго параметра, если значения первого ей до- статочно для вычисления результата. Такова функция && – ей неваж- но, каков второй параметр, при условии, что первый — False.

 

Сканирование

 
 

Функции scanl и scanr похожи на foldl и foldr, только они сохра- няют все промежуточные значения аккумулятора в список. Также существуют функции scanl1 и scanr1, которые являются аналогами foldl1 и foldr1.

ghci> scanl (+) 0 [3,5,2,1]

[0,3,8,10,11]

ghci> scanr (+) 0 [3,5,2,1]

[11,8,3,1,0]

ghci> scanl1 (\acc x –> if x > acc then x else acc) [3,4,5,3,7,9,2,1] [3,4,5,5,7,9,9,9]

 
 

ghci> scanl (flip (:)) [] [3,2,1] [[],[3],[2,3],[1,2,3]]

При использовании функции scanl финальный результат ока- жется в последнем элементе итогового списка, тогда как функция scanr поместит результат в первый элемент.

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


ПРИМЕНЕНИЕ ФУНКЦИЙ С ПОМОЩЬЮ ОПЕРАТОРА $ 115



Поделиться:


Последнее изменение этой страницы: 2017-02-17; просмотров: 201; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.152.77.92 (0.202 с.)