Рекурсия

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

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

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

Кроме того, поскольку Haskell использует модель ленивых вычислений, рекурсивные вызовы, являющиеся аргументами конструкторов данных (например, :), будут вызваны только при необходимости, и даже построение бесконечного списка при помощи рекурсии не приведёт к переполнению стека.

Рекурсия в λ-исчислении реализуется при помощи комбинатора fix (так же известного как Y-комбинатор). В Haskell тоже есть функция, называемая fix (определённая в модуле Data.Function), однако для обычной рекурсии используется более простой синтаксис, позволяющий использовать имя функции в её определении, например:

recursive :: Word -> Word
recursive x = if x == 0 then 0 else 1 + recursive (x-1)

(замечание: эта функция не использует хвостовую рекурсию, и возможно переполнение стека)

В примере выше можно обратить внимание, что чтобы рекурсия завершалась, необходимо определять базовый случай рекурсии. Это можно делать с помощью конструкции if-then-else. Более идиоматичный вариант для Haskell – определение базового случая при помощи сопоставления с шаблоном.

Сопоставление с шаблоном

В любом месте, где происходит связывание значения с именем, вместо имени можно использовать т.н. шаблон – применение конструкторов данных к новым именам. Тогда, если правая часть связывания сконструирована при помощи тех же конструкторов данных, именам будут присвоены значения соответствующих компонентов правой части связывания. В качестве шаблона может быть использован символ _ или идентификатор, начинающийся на символ _. Тогда соответствующее место в шаблоне будет проигнорировано (там может быть что угодно и оно не будет связано с именем)

Для сравнения значения с несколькими шаблонами последовательно можно использовать конструкцию case:

case expression of
  pat1 -> expr1
  pat2 -> expr1
  -- ...

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

case expression of
  pat1 | boolexpr1 -> expr1
  pat2 | boolexpr2 -> expr1
  -- ...

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

Если требуется проверить несколько ограничителей для одного шаблона, для второго и последующих шаблон можно опустить:

case expression of
  pat1 | boolexpr1a -> expr1a
       | boolexpr1b -> expr1b
  pat2 | boolexpr2 -> expr1
  -- ...

Ограничители шаблонов кроме того могут определять новые сопоставления с шаблоном при помощи оператора <-:

case expression of
  pat1 | subpat1 <- patexpr1 -> expr1
  -- ...

Ограничитель, проверяющий несколько условий, может разделять эти условия запятыми:

case expression of
  pat1 | subpat1 <- patexpr1, boolexpr1, {- ... -} -> expr1
  -- ...

Ограничители шаблонов работают в любом месте, где происходит связывание, не только в выражениях case.

Часто бывает удобно определить для шаблона ограничитель, который будет всегда срабатывать (после проверки других ограничителей – они, как и шаблоны, проверяются в порядке определения). Для этого можно было бы использовать логическую истину, True:

case expression of
  pat1 | boolexpr1a -> expr1a
       | boolexpr1b -> expr1b
       -- ...
       | True -> defaultexpr1
  -- ...

Однако это выглядит несколько странно. В Prelude объявлен идентификатор

otherwise :: Bool
otherwise = True

И идиоматически корректным для ограничителя “во всех остальных случаях” использовать его:

case expression of
  pat1 | boolexpr1a -> expr1a
       | boolexpr1b -> expr1b
       -- ...
       | otherwise -> defaultexpr1
  -- ...

Определим рекурсивную функцию recursive используя несколько вариантов сопоставления с шаблоном:

recursive :: Word -> Word
recursive x = case x of
  0 -> 0
  _ -> 1 + recursive (x-1)
-------------------------
recursive :: Word -> Word
recursive x | x == 0 = 0
            | otherwise = 1 + recursive (x-1)
-------------------------
recursive :: Word -> Word
recursive x = case x of
  _ | x == 0 -> 0
    | otherwise -> 1 + recursive (x-1)
-------------------------
recursive :: Word -> Word
recursive x = let res | x == 0 = 0
                      | otherwise = 1 + recursive (x-1)
              in res
-------------------------
recursive :: Word -> Word
recursive x = res
  where res | x == 0 = 0
            | otherwise = 1 + recursive (x-1)
-------------------------
recursive :: Word -> Word
recursive x = res
  where res | 0 <- x = 0
            | otherwise = 1 + recursive (x-1)

Отдельный случай – сопоставление с шаблоном для функций. Функция может быть объявлена несколько раз (но рядом!) с различными шаблонами. В таком случае, все шаблоны будут проверены в порядке определения:

recursive :: Word -> Word
recursive 0 = 0
recursive x = 1 + recursive (x-1)

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

recursive :: Word -> Word
recursive x = 1 + recursive (x-1)
recursive 0 = 0

Действительно, поскольку шаблоны проверяются по очереди, и шаблон x совпадает с любым значением (поскольку является просто именем), шаблон базового случая никогда не будет даже проверен. Если включены предупреждения, GHC предупреждает о таком коде.

Упражнение напишите функцию вычисления факториала:

fac :: Integer -> Integer

учтите, что Integer может быть отрицательным.

“Наивное” решение:

fac :: Integer -> Integer
fac 0 = 1
fac x | x > 0 = x * fac (x-1)
fac _ = error "Negative argument in fac"

“Наивное” решение не использует оптимизацию хвостовой рекурсии. Реализуйте версию fac с хвостовой рекурсией

Решение:

fac :: Integer -> Integer
fac x | x < 0 = error "Negative argument in fac"
fac x = fac' x 1
  where
    fac' 0 acc = acc
    fac' n acc = fac' (n-1) (acc*n)

bottom

Наличие рекурсии ставит вопрос с точки зрения теории типов: какое значение возвращает функция, уходящая в бесконечную рекурсию? По-видимому, это значение “ошибка времени выполнения”, если происходит переполнение стека, либо “зависание”, если переполнения стека не происходит. С точки зрения теории типов, вычисления, которые завершаются ошибкой или не завершаются, имеют значение, называемое “bottom”, или “дно”, и иногда обозначаемое _|_. Любой тип в языке, позволяющем ошибочные или незавершающиеся вычисления, содержит такое значение.

В Haskell стандартные функции error :: String -> a и undefined :: a возвращают именно это значение. При попытке вычисления выражений с error или undefined произойдёт ошибка времени выполнения.

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

partialBool :: Bool -> Integer
partialBool False = 0

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

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

Функции работы со списками

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

walkList :: [a] -> SomeType
walkList (x : xs) = -- случай, когда в списке есть хотя бы один элемент
  walkList xs
  -- xs -- это остаток списка, рекурсивный вызов чтобы пройти по нему
walkList [] = -- базовый случай рекурсии, пустой список

Например, функцию length, возвращающую длину списка, можно определить как

length :: [a] -> Int
length [] = 0
length (x:xs) = 1 + length xs

На практике, используется реализация с хвостовой рекурсией:

length :: [a] -> Int
length xs = lenAcc xs 0
  where lenAcc [] n = n
        lenAcc (_:ys) n = lenAcc ys (n+1)

Перечислим основные функции работы со списками:

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

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

(++) :: [a] -> [a] -> [a]

Оператор конкатенации списков. В современном Haskell обычно используют обобщённый оператор (<>).

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

Выбор из списка элементов, удовлетворяющих предикату (функции, возвращающей Bool). Результат – список, в котором сохранены только элементы, для которых функция, переданная первым аргументом, возвращает True.

head :: [a] -> a

Получить первый элемент списка. Это частично определённая функция! Бросает ошибку времени выполнения на пустом списке. В стандартной библиотеке есть функция listToMaybe, определённая в модуле Data.Maybe, являющаяся “безопасным” (не кидающим ошибок) вариантом:

listToMaybe :: [a] -> Maybe a

last :: [a] -> a

Получить последний элемент списка. Это частично определённая функция! Бросает ошибку времени выполнения на пустом списке. На бесконечном списке работает бесконечно долго.

tail :: [a] -> [a]

Получить все элементы списка кроме первого. Это частично определённая функция! Бросает ошибку времени выполнения на пустом списке. Более безопасной версией этой функции может быть drop 1, которая вернёт пустой список для пустого списка.

init :: [a] -> [a]

Получить все элементы списка кроме последнего. Это частично определённая функция! Бросает ошибку времени выполнения на пустом списке.

null :: [a] -> Bool
-- на самом деле
null :: Foldable t => t a -> Bool

Возвращает True, если список пуст (или в общем случае структура пуста)

length :: [a] -> Int
-- на самом деле
length :: Foldable t => t a -> Int

Возвращает число элементов в списке (или в общем случае в структуре)

(!!) :: [a] -> Int -> a

Оператор получения из списка, переданного первым аргументом, элемента под номером, переданным вторым аргументом. Нумерация элементов с 0. Частично определённая функция! Для отрицательного индекса или индекса, выходящего за границы списка, бросит исключение времени выполнения.

reverse :: [a] -> [a]

Возвращает список с элементами в обратном порядке. Список должен быть конечным.

Свёртки

Свёртка – это проход по структуре с применением бинарной операции к некому “аккумулятору” и каждому значению структуры. Выделяют левые свёртки (операция применяется левоассоциативно, проход по структуре слева направо) и правые свёртки (правоассоциативно, справа налево).

Многие рекурсивные функции можно выразить в терминах свёрток.

Основные свёртки – это

foldr :: (a -> b -> b) -> b -> [a] -> b
-- на самом деле
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

Правая свёртка. Первый аргумент – бинарная операция, второй – начальное значение, третий – структура.

foldl :: (b -> a -> b) -> b -> [a] -> b
-- на самом деле
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

Левая свёртка. Первый аргумент – бинарная операция, второй – начальное значение, третий – структура. Следует отметить, что реализация foldl может быть неэффективной, поскольку “слишком ленивая”. Более эффективная реализация – foldl', определённая в Data.Foldable.

elem :: Eq a => a -> [a] -> Bool
--на самом деле
elem :: (Foldable t, Eq a) => a -> t a -> Bool

Для типов элементов, для которых определено сравнение, проверяет, является ли значение элементом списка. x `elem` xs возвращает True, если x является элементом xs, и False в противном случае.

notElem :: (Foldable t, Eq a) => a -> t a -> Bool

Проверка, обратная elem

concat :: [[a]] -> [a]
-- на самом деле
concat :: Foldable t => t [a] -> [a]

Конкатенация списка списков в список (в общем случае структуры, элементами которой являются списки)

concatMap :: (a -> [b]) -> [a] -> [b]
-- на самом деле
concatMap :: Foldable t => (a -> [b]) -> t a -> [b]

Комбинация map и concat: применить функцию к каждому элементу списка (структуры), затем произвести конкатенацию результатов.

and :: Foldable t => t Bool -> Bool
all :: Foldable t => (a -> Bool) -> t a -> Bool
or :: Foldable t => t Bool -> Bool
any :: Foldable t => (a -> Bool) -> t a -> Bool

Операции над списками булевских значений. and и or соответствуют конъюнкции и дизъюнкции элементов списка, all и any – это их комбинации с map.

Построение списков

scanl :: (b -> a -> b) -> b -> [a] -> [b]
scanr :: (a -> b -> b) -> b -> [a] -> [b]

Аналогично свёрткам, но возвращает список промежуточных результатов.

iterate :: (a -> a) -> a -> [a]

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

repeat :: a -> [a]

Создаёт бесконечный список повторяющегося значения первого аргумента.

replicate :: Int -> a -> [a]

Версия repeat с ограничением числа повторов.

cycle :: [a] -> [a]

Возвращает бесконечный список, полученный зацикливанием списка переданного первым аргументом. Для бесконечного списка xs, cycle xs = xs.

Подпоследовательности

take :: Int -> [a] -> [a]

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

drop :: Int -> [a] -> [a]

Отбросить данное количество первых элементов списка. Возвращает весь список, если данное число меньше или равно 0. Возвращает пустой список, если данное число больше количества элементов в списке.

splitAt :: Int -> [a] -> ([a], [a])

Разрезать список на два в данном месте. Поведение эквивалентно следующему определению:

splitAt n xs = (take n xs, drop n xs)

если n не bottom.

takeWhile :: (a -> Bool) -> [a] -> [a]
dropWhile :: (a -> Bool) -> [a] -> [a]

Получает/отбрасывает элементы списка, пока выполняется предикат, переданный первым аргументом.

span :: (a -> Bool) -> [a] -> ([a], [a])

Комбинация takeWhile и dropWhile, аналогично splitAt

break :: (a -> Bool) -> [a] -> ([a], [a])

Разделяет список, когда предикат становится истинным. Эквивалентно

break p = span (not . p)

lookup :: Eq a => a -> [(a, b)] -> Maybe b

Поиск значения в списке пар по первому элементу. Не слишком эффективная реализация словаря.

“Молнии”

Функции-“молнии” позволяют поэлементно объединить несколько списков.

zip :: [a] -> [b] -> [(a, b)]

Поэлементно объединяет 2 списка в пары значений этих списков

zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]

Поэлементно объединяет 3 списка в тройки значений этих списков

В модуле Data.List есть объявления для zip4 и т.д. до zip7.

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

Объединяет 2 списка при помощи бинарной операции.

zip = zipWith (,)

zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]

Объединяет 3 списка при помощи бинарной операции.

zip3 = zipWith3 (,,)

В модуле Data.List объявлены прочие версии до zipWith7 включительно.

unzip :: [(a, b)] -> ([a], [b])
unzip3 :: [(a, b, c)] -> ([a], [b], [c])

Операции, обратные zip и zip3. В Data.List объявлены до unzip7 включительно.

Поиск в списках

Эти функции объявлены в модуле Data.List.

elemIndex :: Eq a => a -> [a] -> Maybe Int

Найти индекс первого вхождения данного элемента в списке.

elemIndices :: Eq a => a -> [a] -> [Int]

То же, но для всех вхождений

findIndex :: (a -> Bool) -> [a] -> Maybe Int
findIndices :: (a -> Bool) -> [a] -> [Int]

Аналогично, но ищет элемент(ы), удовлетворяющие предикату.

Сортировка

sort :: Ord a => [a] -> [a]
sortOn :: Ord b => (a -> b) -> [a] -> [a]

Сортировка списков. sortOn позволяет преобразовать каждый элемент для определения порядка сортировки.

sortBy :: (a -> a -> Ordering) -> [a] -> [a]

Сортировка в соответствии с данной функцией сравнения.

Списковые включения

Кроме, собственно, функций работы со списками, Haskell поддерживает синтаксис так называемых “списковых включений”. Этот синтаксис происходит из математического синтаксиса включений множеств, какого-то такого вида: \[\{ x | x \in S, x >= 0 \}\]

Синтаксис списковых включений имеет общий вид:

[ expr | pat1 <- listExpr1, guard1, ..., pat2 <- listExpr2, ...]

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

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

Prelude> [ (x, y) | x <- [1..3], y<- ['a'..'c']]
[(1,'a'),(1,'b'),(1,'c'),(2,'a'),(2,'b'),(2,'c'),(3,'a'),(3,'b'),(3,'c')]
Prelude> [ (x, y) | x <- [1..10], x `mod` 3 == 0, y<- ['a'..'c']]
[(3,'a'),(3,'b'),(3,'c'),(6,'a'),(6,'b'),(6,'c'),(9,'a'),(9,'b'),(9,'c')]
Prelude> [ (x, y) | x <- [1..10], y <- [2..x-1], x `mod` y == 0]
[(4,2),(6,2),(6,3),(8,2),(8,4),(9,3),(10,2),(10,5)]

Последний пример выводит делители составных чисел.

Поскольку происходит связывание, возможно сопоставление с шаблоном:

Prelude> [ x | Just x <- [Just 1, Nothing, Just 2, Just 3, Nothing]]
[1,2,3]

Значения, не соответствующие шаблону, будут отброшены.

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

filter p xs = [ x | x <- xs, p x ]
map f xs = [ f x | x <- xs ]

Упражнения

Упражнение 1.

Последовательность Фибоначчи имеет следующее определение:

\[ F(0) = 1 ;\; F(1) = 1 ;\; F(n) = F(n-1) + F(n-2) ; \]

Реализуйте функцию

fibN :: Integer -> Integer

принимающую номер числа в последовательности Фибоначчи и возвращающую соответствующее число.

Реализуйте варианты, использующий и не использующий хвостовую рекурсию. Сравните.

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

Для этого и следующего упражнений в качестве шаблона рекомендуется использовать https://github.com/haskell-course-lierdakil/fibonacci-template, там определены тесты корректности и производительности.

Упражнение 2.

Напишите функцию

fib :: [Integer]

генерирующую бесконечную последовательность Фибоначчи.

Напишите “наивный” вариант, использующий fibN и map.

Напишите рекурсивное определение fib используя zipWith.

Сравните.

Для этого и предыдущего упражнений в качестве шаблона рекомендуется использовать https://github.com/haskell-course-lierdakil/fibonacci-template, там определены тесты корректности и производительности.

Упражнение 3.

Целочисленное деление – это повторённое вычитание. Для двух натуральных чисел, результат деления x на y – это сколько раз можно из x вычесть y, и остаток – это число, оставшееся от x после этого количества вычитаний.

Напишите рекурсивную функцию

myDiv :: Integer -> Integer -> (Integer, Integer)

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

Расширьте Вашу функцию на отрицательные числа.

В качестве шаблона рекомендуется использовать https://github.com/haskell-course-lierdakil/division-template, там определены тесты корректности.

Упражнение 4.

Шифр Виженера – это обобщение шифра Цезаря. Ключ в шифре Виженера – это конечная последовательность алфавитных сдвигов, которые циклически повторяются при проходе по символам сообщения. Шифр Цезаря – это шифр Виженера с длиной ключа 1.

Реализуйте функцию

vigenere :: [Char] -> [Int] -> String -> String
vigenere alphabet key message = undefined

принимающую алфавит (в виде строки), ключ (в виде списка целых чисел – сдвигов) и сообщение (в виде строки) и шифрующее его. Учтите, что сдвиги могут быть отрицательными.

Если в сообщении встречается символ, не входящий в алфавит, пропускайте его.

Указание: используйте функции cycle, zipWith, elemIndex, оператор (!!), и списочные включения.

Реализуйте на основе функции vigenere обратную функцию unvigenere.

В качестве шаблона рекомендуется использовать https://github.com/haskell-course-lierdakil/vigenere-template, там определены тесты корректности.