Unknown - haskell-notes

дартного модуля Data.Maybe. Нам осталось определить лишь две функции. Это аналог функции dropWhile

на списках. Эта функция удаляет из начала списка все элементы, которые удовлетворяют некоторому пре-

дикату. Вторая функция erase вычёркивает все числа в потоке кратные данному.

dropWhileS ::(a -> Bool) -> Streama -> Streama

dropWhileS p =psi >>phi

wherephi ((b, xs) :&next) = ifb thennext elsexs

psi xs =(p $headS xs, xs) :&tailS xs

В этой функции мы сначала генерируем список пар, который содержит значения предиката и остатки

списка, а затем находим в этом списке первый такой элемент, значение которого равно False.

erase :: Int -> Stream( Maybea) -> Stream( Maybea)

erase n xs =ana phi (0, xs)

wherephi (a, xs)

|a ==0

= Nothing

:&(a’, tailS xs)

|otherwise =headS xs :&(a’, tailS xs)

wherea’ = ifa ==n -1 then0 else(a +1)

Гиломорфизм | 249

В функции erase мы заменяем на Nothingкаждый элемент, порядок следования которого кратен аргу-

менту n. Проверим, что у нас получилось:

*Fix>primes

(2 :&(3 :&(5 :&(7 :&(11 :&(13 :&(17 :&(19 :&(23 :&(29 :&(31 :&(37 :&(41 :&(43 :&(47 :&(53 :&(59 :&

(61 :&(67 :&(71 :&(73 :&(79 :&(83 :&(89 :&(97 :&

(101 :&(103 :&(107 :&(109 :&(113 :&(127 :&(131 :&

...

16.4 Краткое содержание

В этой главе мы узнали, что любая рекурсивная функция может быть выражена через структурную ре-

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

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

гласит:

Управляющие структуры определяются структурой типов.

Определив тип, мы получаем вместе с ним две функции структурной рекурсии, это катаморфизм (для

начальных объектов) и анаморфизм (для конечных объектов). С помощью катаморфизма мы можем свора-

чивать значение данного типа в значения любого другого типа, а с помощью анаморфизма мы можем раз-

ворачивать значения данного типа из значений любого другого типа. Также мы узнали, что категория Hask

является категорией CPO, категорией полных частично упорядоченных множеств.

16.5 Упражнения

• Потренируйтесь в определении рекурсивных функций через гиломорфизм. Попробуйте переписать как

можно больше определений из главы о структурной рекурсии в терминах типа Fixи функций cata, ana

и hylo. Также потренируйтесь на стандартных функциях из модуля Prelude. Определите новые типы

через Fixнапример деревья из модуля Data.Tree. Попробуйте свои силы на функциях по-сложнее

например алгоритме эвристического поиска.

• Определите монадные версии рекурсивных функций:

cataM ::( Monadm, Traversablet) =>(t a ->m a) -> Fixt ->m a

anaM

::( Monadm, Traversablet) =>(a ->m (t a)) ->(a ->m ( Fixt))

hyloM ::( Monadm, Traversablet) =>(t b ->m b) ->(a ->m (t a)) ->(a ->m b) С помощью этих функций мы, например, можем преобразовывать дерево выражения и при этом обнов-

лять какое-нибудь состояние или читать из общего окружения.

В этом определении стоит новый класс Traversable. Разберитесь с ним самостоятельно. Немного под-

скажу. Этот класс появился вместе с классом Applicative. Когда разработчики поняли о существова-

нии полезной абстракции, которая ослабляет класс Monad, они также обратили внимание на функцию

sequence:

sequence :: Monadm =>[m a] ->m [a]

sequence =foldr (liftM2 ( :)) (return [])

Эту функцию можно записать с помощью одних лишь методов класса Applicative. Поэтому ограниче-

ние в контексте функции избыточно. Класс Traversableпредназначени для устранения этой неточно-

сти. Посмотрим на основной метод класса:

class( Functort, Foldablet) => Traversablet where