Функция >reverse обращает список, выстраивая элементы в обратном порядке. И снова пустой список оказывается базовым случаем, потому что если обратить пустой список, получим тот же пустой список. Хорошо… А что насчёт всего остального? Ну, можно сказать, что если разбить список на «голову» и «хвост», то обращённый список – это обращённый «хвост» плюс «голова» списка в конце.
>reverse' :: [a] –> [a]
>reverse' [] = []
>reverse' (x:xs) = reverse' xs ++ [x]
Готово!
Функция >repeat принимает на вход некоторый элемент и возвращает бесконечный список, содержащий этот элемент. Рекурсивное определение такой функции довольно просто – судите сами:
>repeat' :: a –> [a]
>repeat' x = x:repeat' x
Вызов >repeat 3 даст нам список, который начинается с тройки и содержит бесконечное количество троек в хвостовой части. Вызов будет вычислен как >3:repeat 3, затем как >3:(3:repeat 3), >3:(3:(3: repeat 3)) и т. д. Вычисление >repeat 3 не закончится никогда, а вот >take 5 (repeat 3) выдаст нам список из пяти троек. Это то же самое, что вызвать >replicate 5 3.
Функция >repeat наглядно показывает, что рекурсия может вообще не иметь базового случая, если она создаёт бесконечные списки – нам нужно только вовремя их где-нибудь обрезать.
Функция >zip берёт два списка и стыкует их, образуя список пар (по аналогии с тем, как застёгивается замок-молния). Так, например, >zip [1,2,3] ['a','b'] вернёт список >[(1,'a'),(2,'b')]. При этом более длинный список, как видите, обрезается до длины короткого. Ну а если мы состыкуем что-либо с пустым списком? Получим пустой список! Это базовый случай. Но так как функция принимает на вход два списка, то на самом деле это два базовых случая.
>zip' :: [a] –> [b] –> [(a,b)]
>zip' _ [] = []
>zip' [] _ = []
>zip' (x:xs) (y:ys) = (x,y):zip' xs ys
Первые два образца соответствуют базовым случаям: если первый или второй список пустые, возвращается пустой список. В третьем образце говорится, что склеивание двух списков эквивалентно созданию пары из их «голов» и присоединению этой пары к результату склеивания «хвостов».
Например, если мы вызовем >zip' со списками >[1,2,3] и >['a','b'], то первым элементом результирующего списка станет пара >(1,>'a'), и останется склеить списки >[2,3] и >['b']. После ещё одного рекурсивного вызова функция попытается склеить >[3] и >[], что будет сопоставлено с первым образцом. Окончательным результатом теперь будет список >(1,'a'):((2,'b'):[])