Реализация простейших списочных и прочих функций

Давайте еще потренируемся в написании простейших списочных функций, которые мы упоминали.

init :: [a] -> [a]

init [x] = []

init (x:xs) = x : init xs

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

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

Элементарно! Функция просто должна рекурсивно вызвать саму себя от хвоста списка, потребовав вернуть номер с элементом на единицу меньше, чем от нее самой хотят:

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

(!!) [] _ = error “index too large”

(!!) (x:xs) 0 = x

(!!) (x:xs) n = (!!) xs (n-1)

Функция error прерывает выполнение функции, выводя сообщение об ошибке. Мы должны это сделать, если на каком-то шаге выяснилось, что от нас требуют вернуть элемент с каким-то номером из пустого списка. Обратили внимание, как параметр n с каждым шагом становится на единицу меньше? Вот как это будет работать:

(!!) [1,2,3] 2 →

(!!) [2,3] 1 →

(!!) [3] 0 → 3

(!!) [1,2,3] 6 →

(!!) [2,3] 5 →

(!!) [3] 4 →

(!!) [] 3 → error

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

concat :: [[a]] -> [a]

concat [] = []

concat (list : lists) = list ++ concat lists

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

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

take 0 _ = []

take _ [] = []

take n (x:xs) = x : take (n-1) xs

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

drop 0 xs = xs

drop _ [] = []

drop n (_:xs) = drop (n-1) xs

Обратите внимание, и take и drop корректно обрабатывают все терминальные случаи параметров, которые у них могут оказаться. Ну и еще можно обратить внимание на хитрый образец (_:xs), который использует drop. Конечно же, там могло быть написано (x:xs), но эта запись подчеркивает, что само значение головы списка нам не интересно.

Ну и наконец, функция проверки принадлежности элемента списку:

elem :: Eq a => a -> [a] -> Bool

elem x [] = False

elem x (y:ys) = if x == y then True else elem x ys

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

elem x [] = False

elem x (y:ys) = (x == y) || elem x ys

А можно было обойтись без конструкции if:

elem x [] = False

elem x (y:ys) | x==y = True

| otherwise = elem x ys

Еще несколько околосписочных функций. Функции суммы и произведения списка чисел:

sum :: Num a => [a] -> a

sum [] = 0

sum (x:xs) = x + sum xs

product :: Num a => [a] -> a

product [] = 1

product (x:xs) = x * product xs

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

Максимальное и минимальное число из списка:

max :: Ord a => a -> a -> a

max x y = if x > y then x else y

min :: Ord a => a -> a -> a

min x y = if x < y then x else y

maximum :: Ord a => [a] -> a

maximum [x] = x

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

minimum :: Ord a => [a] -> a

minimum [x] = x

minimum (x:xs) = min x (minimum xs)

Функцию нахождения максимума из списка можно было написать и по-другому:

maximum [x] = x

maximum (x:y:xs) =

if x > y then maximum (x:xs) else maximum (y:xs)

Логические функции and и or принимают список значений типа Bool и возвращают True, в случае если все (and) или одно (or) значение из списка равно True. Реализация этих функций для вас теперь тоже, надеюсь, тривиальна:

and :: [Bool] -> Bool

and [] = True

and (x:xs) = x && and xs

or :: [Bool] -> Bool

or [] = True

or (x:xs) = x || or xs

Ну и напоследок, пара кортежных функций. Функция zip превращает два списка значений в список кортежей из элементов, стоящих на одной и той же позиции. Например, zip [1..5] ['a'..'z'] → [(1,'a'), (2,'b'), (3,'c'), (4,'d'), (5,'e')]. Обратите внимание, как функция zip работает, если списки разной длины:

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

zip (a:as) (b:bs) = (a,b) : zip as bs

zip _ _ = []

А вот обратную функцию unzip написать сложнее и поучительнее:

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

Функция должна принять список кортежей, разделить каждый кортеж на элементы, и сложить элементы в отдельные списки. Проблема тут в том, как вы понимаете, что никаких промежуточных переменных для складывания списков у нас нет. И, разумеется, это и есть подсказка – вместо таких переменных нужно использовать два дополнительных аккумулятора. Ну и reverse, чтобы избавиться от ненужных эффектов переворачивания списков (разберитесь сами, почему так происходит).

unzip list = unzip' list [] []

unzip' [] as bs = (reverse as, reverse bs)

unzip' ((a,b):list) as bs = unzip' list (a:as) (b:bs)

Обратили внимание, какой сложный образец был использован? Пришедший список кортежей был разложен на первый кортеж (a,b) и список остальных кортежей list, а первый кортеж был дополнительно разложен на его две составляющие a и b. Попробуйте представить, как выглядела бы эта функция без использования образцов и в виде одного определения? Фу, гадость:

unzip list as bs =

if null list then

(reverse as, reverse bs)

else

unzip (tail list)

(fst (head list) : as)

(snd (head list) : bs)

Если добавить побольше скобок, будет просто вылитый Лисп, правда?