Выражения let в генераторах списков

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

calcBmis:: [(Double, Double)] -> [Double]

calcBmis xs = [bmi | (w, h) <– xs, let bmi = w / h 2]

Мы поместили выражение let в генератор списка так, слов- но это предикат, но он не фильтрует список, а просто определяет имя. Имена, определённые в секции let внутри генератора спис- ка, видны в функции вывода (часть до символа |) и для всех пре- дикатов и секций, которые следуют после ключевого слова let. Так что мы можем написать функцию, которая выводит только толстяков:

calcBmis:: [(Double, Double)] -> [Double]

calcBmis xs = [bmi | (w, h) <– xs, let bmi = w / h ^ 2, bmi > 25.0]

Использовать имя bmi в части (w, h) <– xs нельзя, потому что она расположена до ключевого слова let.

 

Выражения let в GHCi

Часть in также может быть пропущена при определении функций и констант напрямую в GHCi. В этом случае имена будут видимы во время одного сеанса работы GHCi.

ghci> let zoot x y z = x * y + z ghci> zoot 3 9 2

ghci> let boot x y z = x * y + z in boot 3 4 2

 

ghci> boot

<interactive>:1:0: Not in scope: `boot'

Поскольку в первой строке мы опустили часть in, GHCi знает, что в этой строке zoot не используется, поэтому запомнит его до конца сеанса. Однако во втором выражении let часть in присутс- твует, и определённая в нём функция boot тут же вызывается. Вы- ражение let, в котором сохранена часть in, является выражением и представляет некоторое значение, так что GHCi именно это зна- чение и печатает.

 

Выражения для выбора из вариантов

Во многих императивных языках (C, C++, Java, и т. д.) имеется опе- ратор case, и если вам доводилось

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

указывает на то, что они являются... э-э-э... выражениями, так же как if – then – else и let. Мы не только можем вычислять выражения, основываясь на возможных значениях переменной, но и произво- дить сопоставление с образцом.

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

head':: [a] –> a

head' [] = error "Никаких head для пустых списков!" head' (x:_) = x

ВЫРАЖЕНИЯ ДЛЯ ВЫБОРА ИЗ ВАРИАНТОВ 77

head':: [a] –> a head' xs =

case xs of

[] –> error "Никаких head для пустых списков!" (x:_) –> x

Как видите, синтаксис для выражений отбора довольно прост:

case expression of pattern –> result pattern –> result

...

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

Сопоставление с образцом по параметрам функции может быть сделано только при объявлении функции; выражения отбора могут использоваться практически везде. Например:

describeList:: [a] –> String describeList xs = "Список " ++

case xs of

[] –> "пуст."

[x] –> "одноэлементный." xs –> "длинный."

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

describeList:: [a] –> String describeList xs = "Список " ++ what xs

where

what [] = "пуст."

what [x] = "одноэлементный." what xs = "длинный."

 

РЕКУРСИЯ

 

Привет, рекурсия!

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

Если вы всё ещё не знаете, что такое рекурсия, прочтите это предложение ещё раз. Шучу!.. На самом деле рекурсия – это способ определять функции таким

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

лее мелкие. Рано или поздно мы достигаем базовый случай (или ба- зовые случаи) задачи, разбить который на подзадачи не удаётся и который требует написания явного (нерекурсивного) решения.

МАКСИМУМ УДОБСТВА 79

Многие понятия в математике даются рекурсивно. Например, последовательность чисел Фибоначчи. Мы определяем первые два числа Фибоначчи не рекурсивно. Допустим, F (0) = 0 и F (1) = 1; это означает, что нулевое и первое число из ряда Фибоначчи – это ноль и единица. Затем мы определим, что для любого натурально- го числа число Фибоначчи представляет собой сумму двух преды- дущих чисел Фибоначчи. Таким образом, F (n) = F (n – 1) + F (n – 2). Получается, что F (3) – это F (2) + F (1), что в свою очередь даёт (F (1) + F (0)) + F (1). Так как мы достигли чисел Фибоначчи, задан- ных не рекурсивно, то можем точно сказать, что F (3) равно двум. Рекурсия исключительно важна для языка Haskell, потому что,

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

 

Максимум удобства

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

Ну а теперь посмотрим, как можно сформулировать этот алго- ритм рекурсивно. Для начала мы бы определили базовые случаи. В пустом списке невозможно найти максимальный элемент. Если список состоит из одного элемента, то максимум равен этому эле- менту. Затем мы бы сказали, что максимум списка из более чем двух элементов – это большее из двух чисел: первого элемента («голо- вы») или максимального элемента оставшейся части списка («хвос- та»). Теперь запишем это на языке Haskell.

 

maximum':: (Ord a) => [a] –> a

maximum' [] = error "максимум в пустом списке" maximum' [x] = x

maximum' (x:xs) = max x (maximum' xs)

Как вы видите, сопоставление с образцом отлично дополняет рекурсию! Возможность сопоставлять с образцом и разбивать со- поставляемое значение на компоненты облегчает запись подзадач в задаче поиска максимального элемента. Первый образец говорит, что если список пуст – это ошибка! В самом деле, какой максимум у пустого списка? Я не знаю. Второй образец также описывает базо- вый случай. Он говорит, что если в списке всего один элемент, надо его вернуть в качестве максимального.

В третьем образце происходит самое интересное. Мы исполь- зуем сопоставление с образцом для того, чтобы разбить список на «голову» и «хвост». Это очень распространённый приём при работе со списками, так что привыкайте. Затем мы вызываем уже знакомую функцию max, которая принимает два параметра и воз- вращает больший из них. Если x больше наибольшего элемента xs, то вернётся x; в противном случае вернётся наибольший элемент xs. Но как функция maximum' найдёт наибольший элемент xs? Очень просто — вызвав себя рекурсивно.

Давайте возьмём конкретный пример и посмотрим, как всё это работает. Итак, у нас есть список [2,5,1]. Если мы вызовем функ- цию maximum' с этим значением, первые два образца не подойдут. Третий подойдёт – список разобьётся на 2 и [5,1]. Теперь мы зано- во вызываем функцию с параметром [5,1]. Снова подходит третий образец, список разбивается на 5 и [1]. Вызываем функцию для [1]. На сей раз подходит второй образец – возвращается 1. Наконец-то! Отходим на один шаг назад, вычисляем максимум 5 и наибольшего

 

элемента [1] (он равен 1), получаем 5. Теперь мы знаем, что макси- мум [5,1] равен 5. Отступаем ещё на один шаг назад – там, где у нас было 2 и [5,1]. Находим максимум 2 и 5, получаем 5. Таким образом,

наибольший элемент [2,5,1] равен 5.