Изучай Haskell во имя добра! - Миран Липовача

ghci> 4 * (let a = 9 in a + 1) + 2

42

Ключевое слово let подойдёт для определения локальных функций:

ghci> [let square x = x * x in (square 5, square 3, square 2)]

[(25,9,4)]

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

ghci> (let a = 10; b = 20 in a*b, let foo="Эй, "; bar = "там!" in foo ++ bar)

(200,"Эй, там!")

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

ghci> (let (a,b,c) = (1,2,3) in a+b+c) * 100

600

Если определения let настолько хороши, то почему бы только их всё время и не использовать? Ну, так как это всего лишь выражения, причём с локальной областью видимости, то их нельзя использовать в разных охранных выражениях. К тому же некоторые предпочитают, чтобы их переменные вычислялись после использования в теле функции, а не до того. Это позволяет сблизить тело функции с её именем и типом, что способствует большей читабельности.

Выражения 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

29

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

14

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

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 = "длинный."

4

Рекурсия

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

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

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

Многие понятия в математике даются рекурсивно. Например, последовательность чисел Фибоначчи. Мы определяем первые два числа Фибоначчи не рекурсивно. Допустим, 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.