Изучай Haskell во имя добра! (Липовача) - страница 39

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

>describeList :: [a] –> String

>describeList xs = "Список " ++

>  case xs of

>   [] –> "пуст."

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

>   xs –> "длинный."

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

>describeList :: [a] –> String

>describeList xs = "Список " ++ what xs

>  where

>    what [] = "пуст."

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

>    what xs = "длинный."

В предыдущей главе мы кратко затронули рекурсию. Теперь мы изучим её более подробно, узнаем, почему она так важна для языка 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 – вместо этого мы зачастую должны использовать рекурсию, чтобы описать, что представляет собой та или иная сущность.