Учебник по Haskell

смотрим на определение:

fix f = let x = f x

in

x

Если вы запутались, то посмыслу это определение равносильно такому:

fix f = f (fix f)

Функция fix берёт функцию и начинает бесконечно нанизывать её саму на себя. Так мы получаем, что-то

вроде:

f (f (f (f (... ))))

Зачем нам такая функция? Помните в самом конце четвёртой главы в упражнениях мы составляли бес-

конечные потоки. Мы делали это так:

data Stream a = a :& Stream a

constStream :: a -> Stream a

constStream a = a :& constStream a

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

Если смотреть на функцию constStream очень долго, то рано или поздно в ней проглянет функция fix. Я

нарошно не буду выписывать, а вы мысленно обозначьте (a :& ) за f и constStream a за fix f. Получилось?

Через fix можно очень просто определить бесконечность для Nat, бесконечность это цепочка Succ, ко-

торая никогда не заканчивается Zero. Оказывается, что в Haskell мы можем составлять выражения с такими

значениями (как это получается мы обудим попозже):

ghci Nat

*Nat> m + Data.Function

*Nat Data.Function> let infinity = fix Succ

*Nat Data.Function> infinity < Succ Zero

False

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

функции foldNat, у нас есть рекурсивное определение:

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

foldNat z

s

Zero

= z

foldNat z

s

(Succ n)

= s (foldNat z s n)

Необходимо привести его к виду:

x = f x

Слева и справа мы видим повторяются выражения foldNat z s, обозначим их за x:

x :: Nat -> a

x Zero

= z

x (Succ n)

= s (x n)

Теперь перенесём первый аргумент в правую часть, сопоставление с образцом превратится в case-

выражение:

x :: Nat -> a

x = \nat -> case nat of

Zero

-> z

Succ n

-> s (x n)

В правой части вынесем x из выражения с помощью лямбда функции:

x :: Nat -> a

x = (\t -> \nat -> case nat of

Zero

-> z

Succ n

-> s (t n)) x

Смотрите мы обозначили вхождение x в выражении справа за t и создали лямбда-функцию с таким ар-

гументом. Так мы вынесли x из выражения.

Получилось, мы пришли к виду комбинатора неподвижной точки:

x :: Nat -> a

x = f x

where f = \t -> \nat -> case nat of

Zero

-> z

Succ n

-> s (t n)

Приведём в более человеческий вид:

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

foldNat z s = fix f

where f t = \nat -> case nat of

Zero

-> z

Succ n

-> s (t n)

Комбинатор неподвижной точки | 83

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

Основные функции высшего порядка

Мы познакомились с функциями из модуля Data.Function. Их можно разбить на несколько типов:

• Примитивные функции (генераторы функций).

id

= \x -> x

const a = \_ -> a

• Функции, которые комбинируют функции или функции и значения:

f . g

= \x -> f (g x)

f $ x

= f x

(.*. ) ‘on‘ f = \x y -> f x .*. f y

• Преобразователи функций, принимают функцию и возвращают функцию:

flip f = \x y -> f y x

• Комбинатор неподвижной точки:

fix f = let x = f x

in

x

Приоритет инфиксных операций

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

infixl 3 #

infixr 6 ‘op‘

Приоритет складывается из двух частей: старшинства (от 1 до 9) и ассоциативности (бывает левая и

правая). Старшинство определяет распределение скобок между разными функциями:

infixl 6 +

infixl 7 *

1 + 2 * 3 == 1 + (2 * 3)

А ассоциативность – между одинаковыми:

infixl 6 +

infixr 8 ^

1 + 2 + 3 == (1 + 2) + 3

1 ^ 2 ^ 3 ==

1 ^ (2 ^ 3)

Мы узнали, что функции ($) и (. ) стоят на разных концах шкалы приоритетов функций и как этим

пользоваться.

5.7 Упражнения

• Просмотрите написанные вами функции, или функции из примеров. Можно ли их переписать с по-

мощью основных функций высшего порядка? Если да, то перепишите. Попробуйте определить их в

бесточечном стиле.

• В прошлой главе у нас было упражнение о потоках. Сделайте поток экземпляром класса Num. Для этого

поток должен содержать значения из класса Num. Методы из класса Num применяются поэлементно. Так

сложение двух потоков будет выглядеть так:

(a1 :& a2 :& a3 :& ... ) + (b1 :& b2 :& b3) ==

==

(a1 + b1 :& a2 + b2 :& a3 + b3 :& ... )

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

• Определите приоритет инфиксной операции (:& )

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

• Рассмотрим такой тип:

data St a b = St (a -> (b, St a b))

Этот тип хранит функцию, которая позволяет преобразовывать потоки значений. Определите функцию

применения:

ap :: St a b -> [a] -> [b]

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

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

модулем Data.Function мы не будем его импортировать. Вместо него мы импортируем модуль

Control.Category. Он содержит класс:

class Category cat where

id

:: cat a a

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