Unknown - haskell-notes

psi >>phi =phi .(fmap $hylo phi psi) .psi

Теперь давайте скроем одноимённую функцию из Preludeи определим несколько рекурсивных функций

с помощью гиломорфизма. Начнём с функции вычисления суммы чисел от нуля до данного числа:

sumInt :: Int -> Int

sumInt =range >>sum

sum x = casex of

Nil

->0

Consa b ->a +b

range n

|n ==0

= Nil

|otherwise = Consn (n -1)

Сначала мы создаём в функции range список всех чисел от данного числа до нуля. А затем в функции

sum складываем значения. Теперь мы можем легко определить функцию вычисления факториала:

fact :: Int -> Int

fact =range >>prod

prod x = casex of

Nil

->1

Consa b ->a *b

Напишем функцию, которая извлекает из потока n-тый элемент. Сначала определим тип для потока:

type Streama = Fix( Sa)

data Sa b =a :&b

deriving( Show, Eq)

instance Functor( Sa) where

fmap f (a :&b) =a :&f b

headS :: Streama ->a

headS x = caseunFix x of

(a :& _) ->a

tailS :: Streama -> Streama

tailS x = caseunFix x of

( _ :&b) ->b

Теперь функцию извлечения элемента:

getElem :: Int -> Streama ->a

getElem =curry (enum >>elem)

whereelem ((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

fibs =ana (\(a, b) ->a :&(b, a +b)) (0, 1)

Теперь просто извлечём n-тый элемент из потока чисел Фибоначчи:

fib :: Int -> Int

fib =flip getElem fibs

Вычислим поток всех простых чисел. Мы будем вычислять его по алгоритму “решето Эратосфена”. В

начале алгоритма у нас есть поток целых чисел и известно, что первое число является простым.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 …

В процессе этого алгоритма мы вычёркиваем все не простые числа. Сначала мы ищем первое не зачёркну-

тое число и помещаем его в результирующий поток, а на следующий шаг алгоритма мы передаём исходный,

поток в котором зачёркнуты все числа кратные тому, что мы положили последним:

2

3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, …

Теперь мы ищем первое незачёркнутое число и помещаем его в результат. А на следующий шаг рекусии

передаём поток, в котором зачёркнуты все числа кратные новому простому числу:

2, 3

4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, …

И так далее, на каждом шаге мы будем получать одно простое число. Зачёркивание мы будем имитиро-

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

nums :: Stream( Maybe Int)

nums =mapS Just $iterateS ( +1) 2

mapS ::(a ->b) -> Streama -> Streamb

mapS f =ana $\xs ->(f $headS xs) :&tailS xs

iterateS ::(a ->a) ->a -> Streama

iterateS f =ana $\x ->x :&f x

В силу ограничений системы типов Haskell мы не можем определить экземпляр Functorдля типа Stream,

поскольку Streamявляется не самостоятельным типом а типом-синонимом. Поэтому нам приходится опре-

делить функцию mapS. Определим шаг рекурсии:

primes :: Stream Int

primes =ana erato nums

erato xs =n :&erase n ys

wheren

=fromJust $headS xs

ys =dropWhileS isNothing xs

Переменная n содержит первое не зачёркнутое число на данном шаге. Переменная ys указывает на спи-

сок чисел, из начала которого удалены все зачёркнутые числа. Функции isNothing и fromJust взяты из стан-