Unknown - haskell-notes

альтернативы. Например рассмотрим потоки:

data Streama =a :& Streama

Они такие же как и списки, только без конструктора пустого списка. Функция развёртки для потоков

имеет вид:

unfoldStream ::(b ->(a, b)) ->b -> Streama

unfoldStream f

=\b -> casef b of

(a, b’) ->a :&unfoldStream f b’

И нам не нужно пользоваться Maybe. Напишем функции генерации потоков:

iterate ::(a ->a) ->a -> Streama

iterate f =unfoldStream $\a ->(a, f a)

repeat ::a -> Streama

repeat =unfoldStream $\a ->(a, a)

zip :: Streama -> Streamb -> Stream(a, b)

zip =curry $unfoldStream $\(a :&as, b :&bs) ->((a, b), (as, bs))

Натуральные числа

Если присмотреться к натуральным числам, то можно заметить, что они очень похожи на списки. Списки

без элементов. Это отражается на функции развёртки. Для натуральных чисел мы будем возвращать не пару

а просто слкедующий элемент для развёртки:

unfoldNat ::(a -> Maybea) ->a -> Nat

unfoldNat f =maybe Zero( Succ .unfoldNat f)

Напишем функцию преобразования из целых чисел в натуральные:

fromInt :: Int -> Nat

fromInt =unfoldNat f

wheref n

|n ==0

= Nothing

|n >

0

= Just(n -1)

|otherwise = error”negative number”

Обратите внимание на то, что в этом определении не участвуют конструкторы для Nat, хотя мы и строим

значение типа Nat. Конструкторы для Natкак и в случае списков кодируются типом Maybe. Развёртка ис-

пользуется гораздо реже свёртки. Возможно это объясняется необходимостью кодирования типа результата

некоторым промежуточным типом. Определения теряют в наглядности. Смотрим на функцию, а там Maybe

и не сразу понятно что мы строим: натуральные числа, списки или ещё что-то.

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

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

В этой главе мы познакомились с особым видом рекурсии. Мы познакомились со структурной рекурсией.

Типы определяют не только значения, но и способы их обработки. Структурная рекурсия может быть выведе-

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

структурной рекурсии в подарок. Есть языки, в которых структурная рекурсия является единственным воз-

можным способом составления рекурсивных функций.

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

лась лишь в определении для функции свёртки и развёртки. Все остальные функции не содержали рекурсии,

более того почти все они определялись в бесточечном стиле. Структурная рекурсия это своего рода комби-

натор неподвижной точки, но не общий, а специфический для данного рекурсивного типа.

Структурная рекурсия бывает свёрткой и развёрткой.

Cвёрткой (fold)мы получаем значение некоторого произвольного типа из данного рекурсивного типа. При

этом все конструкторы заменяются на функции, которые возвращают новый тип.

Развёрткой (unfold)мы получаем из произвольного типа значение данного рекурсивного типа. Мы словно

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

Мы узнали некоторые стандартные функции структурной рекурсии: cond или if-выражения, maybe, foldr,

unfoldr.

12.4 Упражнения

• Определите развёртку для деревьев из модуля Data.Tree.

• Определите с помощью свёртки следующие функции:

sum, prod

:: Numa =>[a] ->a

or,

and

::[ Bool] -> Bool

length

::[a] -> Int

cycle

::[a] ->[a]

unzip

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

unzip3

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

• Определите с помощью развёртки следующие функции:

infinity

:: Nat

map

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

iterateTree ::(a ->[a]) ->a -> Treea

zipTree

:: Treea -> Treeb -> Tree(a, b)

• Поэкспериментируйте в интерпретаторе с только что определёнными функциями и теми функциями,

что мы определяли в этой главе.

• Рассмотрим ещё один стандартный тип. Он определён в Prelude. Это тип Either(дословно – один из