Теперь давайте скроем одноимённую функцию из Prelude и определим несколько рекурсивных функций
с помощью гиломорфизма. Начнём с функции вычисления суммы чисел от нуля до данного числа:
sumInt :: Int -> Int
sumInt = range >> sum
sum x = case x of
Nil
-> 0
Cons a b -> a + b
range n
| n == 0
= Nil
| otherwise = Cons n (n-1)
Сначала мы создаём в функции range список всех чисел от данного числа до нуля. А затем в функции
sum складываем значения. Теперь мы можем легко определить функцию вычисления факториала:
fact :: Int -> Int
fact = range >> prod
prod x = case x of
Nil
-> 1
Cons a b -> a * b
Напишем функцию, которая извлекает из потока n-тый элемент. Сначала определим тип для потока:
type Stream a = Fix (S a)
data S a b = a :& b
deriving (Show, Eq)
instance Functor (S a) where
fmap f (a :& b) = a :& f b
headS :: Stream a -> a
headS x = case unFix x of
(a :& _) -> a
tailS :: Stream a -> Stream a
tailS x = case unFix x of
(_ :& b) -> b
Теперь функцию извлечения элемента:
getElem :: Int -> Stream a -> a
getElem = curry (enum >> elem)
where elem ((n, a) :& next)
| n == 0
= a
| otherwise = next
enum (a, st) = (a, headS st) :& (a-1, tailS st)
В функции enum мы добавляем к элементам потока убывающую последовательность чисел, она стартует
из данного числа. Элемент, который нам нужен, будет содержать в этой последовательности число ноль. В
функции elem мы как раз и извлекаем тот элемент рядом с которым хранится число ноль. Обратите внима-
ние на то, что рекурсия встроена в этот алгоритм, если данное число не равно нулю, мы просто извлекаем
следующий элемент.
С помощью этой функции мы можем вычислить n-тое число из ряда чисел Фибоначчи. Сначала создадим
поток чисел Фибоначчи:
248 | Глава 16: Категориальные типы
fibs :: Stream Int