Unknown - haskell-notes

( &&) :: Bool -> Bool -> Bool

( &&) a = ifa thenid else(const False)

Также мы можем определить и логическое “или”:

( ||) :: Bool -> Bool -> Bool

( ||) a = ifa then(const True) elseid

Функция композиции

Функция композиции принимает две функции и составляет из них последовательное применение функ-

ций:

( .) ::(b ->c) ->(a ->b) ->a ->c

( .) f g =\x ->f (g x)

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

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

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

Prelude> :m +Data.Char

Prelude Data.Char>(map toUpper .reverse) ”abracadabra”

”ARBADACARBA”

Приведём пример посложнее:

add :: Nat -> Nat -> Nat

add

a

Zero

=a

add

a

( Succb) = Succ(add a b)

Если мы определим функцию свёртки для Nat, которая будет заменять в значении типа Natконструкторы

на соответствующие по типу функции:

foldNat ::a ->(a ->a) -> Nat ->a

foldNat zero succ Zero

=zero

foldNat zero succ ( Succb) =succ (foldNat zero succ b)

То мы можем переписать с помощью функции композиции эту функцию так:

add :: Nat -> Nat -> Nat

add =foldNat

id

( Succ .)

Куда делись аргументы? Они выражаются через функции id и ( .). Поведение этой функции лучше про-

иллюстрировать на примере. Пусть у нас есть два числа типа Nat:

two

= Succ( Succ Zero)

three

= Succ( Succ( Succ Zero))

Вычислим

add two three

Вспомним о частичном применении:

Обобщённые функции | 73

add two three

=>

(add two) three

=>

(foldNat id ( Succ .) ( Succ( Succ Zero))) three

Теперь функция свёртки заменит все конструкторы Succна ( Succ .), а конструкторы Zeroна id:

=>

(( Succ .) (( Succ .) id)) three

Что это за монстр?

(( Succ .) (( Succ .) id))

Функция ( Succ .) это левое сечение операции ( .). Эта функция, которая принимает функции и возвра-

щает функции. Она принимает функцию и навешивает на её выход конструктор Succ. Давайте упростим это

большое выражение с помощью определений функций ( .) и id:

(( Succ .) (( Succ .) id))

=>

( Succ .) (\x -> Succ(id x))

=>

( Succ .) (\x -> Succx)

=>

\x -> Succ( Succx)

Теперь нам осталось применить к этой функции наше второе значение:

(\x -> Succ( Succx)) three

=>

Succ( Succthree)

=>

Succ( Succ( Succ( Succ( Succx))))

Так мы получили, что и ожидалось от сложения. За каждый конструктор Succв первом аргументе мы

добавляем применение Succк результату, а вместо Zeroпротаскиваем через id второй аргумент.

Аналогия с числами

С помощью функции композиции мы можем нанизывать друг на друга списки функций. Попробуем в

интерпретаторе:

Prelude> letf =foldr ( .) id [sin, cos, sin, cos, exp, ( +1), tan]

Prelude>f 2

0.6330525927559899

Prelude>f 15

0.7978497904127007

Функция foldr заменит в списке каждый конструктор ( :) на функцию композиции, а пустой список на

функцию id. В результате получается композиция из всех функций в списке.

Это очень похоже на сложение или умножение чисел в списке. При этом в качестве нуля (для сложения)

или единицы (для умножения) мы используем функцию id. Мы пользуемся тем, что по определению для

любой функции f выполнены тождества:

f

.id

==

f

id .f

==

f

Поэтому мы можем использовать id в качестве накопителя результата композиции, как в случае:

Prelude>foldr ( *) 1 [1,2,3,4]

24

Если сравнить ( .) с умножением, то id похоже на единицу, а (const a) на ноль. В самом деле для любой

функции f и любого значения a выполнено тождество:

const a

.

f

==const a

Мы словно умножаем функцию на ноль, делая её вычисление бессмысленным.

74 | Глава 5: Функции высшего порядка