Unknown - haskell-notes

но собирать результат в обратном порядке, например так в Preludeопределена функция reverse, которая

переворачивает список:

reverse ::[a] ->[a]

reverse =foldl (flip ( :)) []

Деревья

Мы можем определить свёртку и для деревьев. Вспомним тип:

data Treea = Nodea [ Treea]

Запишем в виде класса:

data Treea b where

node ::a ->[b] ->b

В этом случае есть одна тонкость. У нас два рекурсивных типа: само дерево и внутри него – список. Для

преобразования списка мы воспользуемся функцией map:

196 | Глава 12: Структурная рекурсия

foldTree ::(a ->[b] ->b) -> Treea ->b

foldTree node =\x -> casex of

Nodea as ->node a (map (foldTree node) as)

Найдём список всех меток:

labels :: Treea ->[a]

labels =foldTree $\a bs ->a :concat bs

Мы объединяем все метки из поддеревьев в один список и присоединяем к нему метку из текущего узла.

Сделаем дерево экземпляром класса Functor:

instance Functor Tree where

fmap f =foldTree ( Node .f)

Очень похоже на map для списков. Вычислим глубину дерева:

depth :: Treea -> Int

depth =foldTree $\a bs ->1 +foldr max 0 bs

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

среди всех поддеревьев.

12.2 Развёртка

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

другого типа. Этот процесс очень похож на процесс вычисления по имени. Сначала у нас есть отложенное

вычисление или thunk. Затем мы применяем к нему функцию редукции и у нас появляется корневой кон-

структор. А в аргументах конструктора снова сидят thunk’и. Мы применяем редукцию к ним. И так пока не

“развернём” всё значение.

Списки

Для разворачивания списков в Data.Listесть специальная функция unfoldr. Присмотримся сначала к

её типу:

unfoldr ::(b -> Maybe(a, b)) ->b ->[a]

Функция развёртки принимает стартовый элемент, а возвращает значение типа пары от Maybe. Типом

Maybeмы кодируем конструкторы списка:

data[a] b where

( :)

::a ->b ->b

-- Maybe (a, b)

[]

::b

-- Nothing

Конструктор пустого списка не нуждается в аргументах, поэтому его мы кодируем константой Nothing.

Объединение принимает два аргумента голову и хвост, поэтому Maybeсодержит пару из головы и следующего

элемента для разворачивания. Закодируем это определение:

unfoldr ::(b -> Maybe(a, b)) ->b ->[a]

unfoldr f =\b -> case(f b) of

Just(a, b’) ->a :unfoldr f b’

Nothing

-> []

Или мы можем записать это более кратко с помощью свёртки maybe:

unfoldr ::(b -> Maybe(a, b)) ->b ->[a]

unfoldr f =maybe [](\(a, b) ->a :unfoldr f b)

Смотрите, перед нами коробочка (типа b) с подарком (типа a), мы разворачиваем, а там пара: подарок

(типа a) и ещё одна коробочка. Тогда мы начинаем разворачивать следующую коробочку и так далее по

цепочке, пока мы не развернём не обнаружим Nothing, это означает что подарки кончились.

Типичный пример развёртки это функция iterate. У нас есть стартовое значение типа a и функция по-

лучения следующего элемента a ->a

Развёртка | 197

iterate ::(a ->a) ->a ->[a]

iterate f =unfoldr $\s -> Just(s, f s)

Поскольку Nothingне используется цепочка подарков никогда не оборвётся. Если только нам не будет

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

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

zip =curry $unfoldr $\x -> casex of

( []

, _)

-> Nothing

( _

, [])

-> Nothing

(a :as

, b :bs)

-> Just((a, b), (as, bs))

Если один из списков обрывается, то прекращаем разворачивать. А если оба содержат голову и хвост, то

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

Потоки

Для развёртки хорошо подходят типы у которых, всего один конструктор. Тогда нам не нужно кодировать