Unknown - haskell-notes

Zero

->zero

Succm

->succ (foldNat zero succ m)

Обратите внимание на рекурсивный вызов функции foldNat мы обходим всё дерево значения, заменяя

каждый конструктор. Определим знакомые функции через свёртку:

isZero :: Nat -> Bool

isZero =foldNat True(const False)

Посмотрим как вычисляется эта функция:

isZero Zero

=>

True

-- заменили конструктор Zero

isZero ( Succ( Succ( Succ Zero)))

=>

const False(const False(const False True))

-- заменили и Zero и Succ

=>

False

Что интересно за счёт ленивых вычислений на самом деле во втором выражении произойдёт лишь одна

замена. Мы не обходим всё дерево, нам это и не нужно, а смотрим лишь на первый конструктор, если там

Succ, то произойдёт замена на постоянную функцию, которая игнорирует свой второй аргумент и рекурсив-

ного вызова функции свёртки не произойдёт, совсем как в исходном определении!

even, odd :: Nat -> Bool

even

=foldNat True

not

odd

=foldNat Falsenot

Эти функции определяют чётность числа, сдесь мы пользуемся тем свойством, что not (not a) ==a.

Определим сложение и умножение:

add, mul :: Nat -> Nat -> Nat

add a

=foldNat a

Succ

mul a

=foldNat Zero

(add a)

Свёртка | 193

Maybe

Вспомним определение типа для результата частично определённых функций:

data Maybea = Nothing | Justa

Перепишем словно это класс:

data Maybea b where

Nothing ::b

Just

::a ->b

Этот класс принимает два параметра, поскольку исходный тип Maybeпринимает один. Теперь несложно

догадаться как будет выглядеть функция свёртки, мы просто получим стандартную функцию maybe. Дадим

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

instance Functor Maybe where

fmap f =maybe Nothing( Just .f)

instance Monad Maybe where

return

= Just

ma >>=mf

=maybe Nothingmf ma

Списки

Функция свёртки для списков это функция foldr. Выведем её из определения типа:

data[a] =a :[a] | []

Представим, что это класс:

class[a] b where

cons

::a ->b ->b

nil

::b

Теперь получить определение для foldr совсем просто:

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

foldr cons nil =\x -> casex of

a :as

->a ‘cons‘ foldr cons nil as

[]

->nil

Мы обходим дерево значения, заменяя конструкторы методами нашего воображаемого класса. Опреде-

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

Первый элемент списка:

head ::[a] ->a

head =foldr const ( error”empty list”)

Объединение списков:

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

a ++b =foldr ( :) b a

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

хвосте a на второй аргумент, так и получается объединение списков. Обратите внимание на эту особенность,

скорость выполнения операции ( ++) зависит от длины первого списка. Поэтому между двумя выражениями

((a ++b) ++c) ++d

a ++(b ++(c ++d))

Нет разницы в итоговом результате, но есть огромная разница по скорости вычисления! Второй гораздо

быстрее. Убедитесь в этом! Реализуем объединение списка списков в один список:

concat ::[[a]] ->[a]

concat =foldr ( ++) []

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

Через свёртку можно реализовать и функцию преобразования списков:

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

map f =foldr (( :) .f) []

Если смысл выражения (( :) .f) не совсем понятен, давайте распишем его типы:

f

( :)

a

------->

b

------->

([b] -> [b])

Напишем функцию фильтрации:

filter ::(a -> Bool) ->[a] ->[a]

filter p =foldr (\a as ->foldBool (a :as) as (p a)) []

Тут у нас целых две функции свёртки. Если значение предиката p истинно, то мы вернём все элементы

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