Учебник по Haskell - читать бесплатно онлайн полную версию книги автора Unknown (ч. 2)

объектами или связей. При этом объекты и связи можно изобразить графически.

Граф состоит из узлов и рёбер, которые соединяют узлы. Приведём пример графа:

Рис. 3.1: Граф

В этом графе восемь узлов, они пронумерованы, и восемь рёбер, они обозначены буквами. Теорию графов

придумал Леонард Эйлер, когда решал задачу о кёнингсбергских мостах. Он решал задачу о том, можно ли

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

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

А что такое дерево? Дерево это такой связанный граф, у которого нет циклов. Несвязанный граф образует

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

вательности рёбер. Например граф на рисунке выше не является деревом, но если мы сотрём ребро e, то у

нас получится дерево.

Ориентированный граф – это такой граф, у которого все рёбра являются стрелками, они ориентированы,

отсюда и название. При этом теперь каждое ребро не просто связывает узлы, но имеет начало и конец. В ори-

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

в том, что все стрелки в ориентированном дереве как бы “разбегаются” от корня или сбегаются к корню. Ко-

рень определяет все стрелки в дереве. Ориентированное дерево похоже на иерархию. У нас есть корневой

элемент и набор его дочерних поддеревьев, каждое из поддеревьев в свою очередь является ориентирован-

ным деревом и так далее. Проиллюстрируем на картинке, давайте сотрём ребро e и назначим первый узел

корнем. Все наши стрелки будут идти от корня. Сначала мы проведём стрелки к узлам связанным с корнем:

Затем представим, что каждый из этих узлов сам является корнем в своём дереве и повторим эту процеду-

ру. На этом шаге мы дорисовываем стрелки в поддеревьях, которые находятся в узлах 3 и 6. Узел 5 является

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

А невырожденные поддеревья мы будем называть узлами. Корневой узел в данном поддереве называют ро-

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

узлами. На предыдущем шаге у нас появился один родительский узел 1, у которого три дочерних узла: 3, 6,

и 5. А на этом шаге у нас появились ещё два родительских узла 3 и 6. У узла 3 один дочерний узел (4), а у

узла 6 – три дочерних узла (2, 8, 7).

Отметим, что положение узлов и рёбер на картинке не важно, главное это то, какие рёбра какие узлы

соединяют. Мы можем перерисовать это дерево в более привычном виде (рис. 3.4).

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

держат примитивные конструкторы, а узлы – составные. Это происходит из-за того, что каждый конструктор

содержит метку и набор подтипов. В этой аналогии метки становятся узлами, а подтипы-аргументы стано-

вятся поддеревьями.

42 | Глава 3: Типы

Рис. 3.2: Превращаем в дерево

Рис. 3.3: Превращаем в дерево...

Но есть одна тонкость, в которой заключается отличие констант Haskell от деревьев из теории графов. В

теории графов порядок поддеревьев не важен, мы могли бы нарисовать поддеревья в любом порядке, главное

сохранить связи. А в Haskell порядок следования аргументов в конструкторе важен.

На следующем рисунке (рис. 3.5) изображены две константы:

Succ (Succ Zero) :: Nat и Neg (Add One (Mul Six Ten)) :: Expr. Но они изображены немного по-другому.

Я перевернул стрелки и добавил корнем ещё один узел, это тип константы.

Стрелки перевёрнуты так, чтобы стрелки на картинке соответствовали стрелкам в типе конструктора.

Например по виду узла Succ :: Nat -> Nat, можно понять, что это функция от одного аргумента, в неё

впадает одна стрелка-аргумент и вытекает одна стрелка-значение. В конструктор Mul впадает две стрелки,

значит это конструктор-функция от двух аргументов.

Константы похожи на деревья за счёт структуры операции произведения типов. В произведении типов

мы пишем:

data Tnew = Name T1 T2 ... Tn

Структура констант | 43

Рис. 3.4: Ориентированное дерево

Expr

Nat

Neg

Succ

Add

Succ

One

Mul

Zero

Six

Ten

Рис. 3.5: Константы

Так и получается, что у нашего узла New одна вытекающая стрелка, которая символизирует значение типа

Tnew и несколько впадающих стрелок T1, T2, …, Tn, они символизируют аргументы конструктора.

Потренируйтесь изображать константы в виде деревьев, вспомните константы из предыдущей главы, или

придумайте какие-нибудь новые.

Строчная запись деревьев

Итак все константы в Haskell за счёт особой структуры построения типов являются деревьями, но мы

программируем в текстовом редакторе, а не в редакторе векторной графики, поэтому нам нужен удобный

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

Мы сидим на корне дерева и спускаемся по его вершинам. Нам могут встретиться вершины двух типов

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

встречается невырожденный узел мы заключаем его в скобки. Давайте последовательно запишем в строчной

записи дерево из первого примера:

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

которые нам ещё предстоит дописать:

)

(3 . )

(6 . . . ))

(3 4)

(6 2 7 8))

44 | Глава 3: Типы

Рис. 3.6: Ориентированное дерево

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

ровнены. Так мы можем закодировать исходное дерево строкой. Часто самые внешние скобки опускаются. В

итоге получилась такая запись:

tree = 1 (3 4) 5 (6 2 7 8)

По этой записи мы можем понять, что у нас есть два конструктора трёх аргументов 1 и 6, один конструктор

одного аргумента 3 и пять примитивных конструкторов. Точно так же мы строим и все другие константы в

Haskell:

Succ (Succ (Succ Zero))

Time (Hour 13) (Minute 10) (Second 0)

Mul (Add One Ten) (Neg (Mul Six Zero))

За одним исключением, если конструктор бинарный, символьный (начинается с двоеточия), мы помеща-

ем его между аргументов:

(One :+ Ten) :* (Neg (Six :* Zero))

3.3 Структура функций

Функции описывают одни значения в терминах других. При этом важно понимать, что функция это лишь

новое имя, пусть и составное. Мы можем написать 5, или 2+3, это лишь два разных имени для одной кон-

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

других. Как они это делают? Для этого этого в Haskell есть две операции: это композиция и декомпозиция де-

ревьев. С помощью композиции мы строим из простых деревьев сложные, а с помощью декомпозиции разбиваем

составные деревья на простейшие.

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

определения синонима. Давайте вспомним какое-нибудь объявление функции:

(+) a

Zero

= a

(+) a

(Succ b)

= Succ (a + b)

Смотрите в этой функции слева от знака равно мы проводим декомпозицию второго аргумента, а в правой

части мы составляем новое дерево из тех значений, что были нами получены слева от знака равно. Или

посмотрим на другой пример:

show (Time h m s) = show h ++ ”:” ++ show m ++ ”:” ++ show s

Слева от знака равно мы также выделили из составного дерева (Time h m s) три его дочерних для корня

узла и связали их с переменными h, m и s. А справа от знака равно мы составили из этих переменных новое

выражение.

Итак операцию объявления синонима можно представить в таком виде:

name

декомпозиция

композиция

В каждом уравнении у нас три части: новое имя, декомпозиция, поступающих на вход аргументов, и

композиция нового значения. Теперь давайте остановимся поподробнее на каждой из этих операций.

Структура функций | 45

Композиция и частичное применение

Композиция строится по очень простому правилу, если у нас есть значение f типа a -> b и значение x

типа a, мы можем получить новое значение (f x) типа b. Это основное правило построения новых значений,

поэтому давайте запишем его отдельно:

f :: a -> b,

x :: a

--------------------------

(f x) :: b

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

применением или аппликацией.

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

торую мы обошли стороной. В случае деревьев мы строили только константы, и конструктор получал столько

аргументов, сколько у него было дочерних узлов (или подтипов). Так мы строили константы. Но в Haskell мы

можем с помощью применения строить функции на лету, передавая меньшее число аргументов, этот процесс

называется частичным применением или каррированием (currying). Поясним на примере, предположим у нас

есть функция двух аргументов:

add :: Nat -> Nat -> Nat

add a b = ...

На самом деле компилятор воспринимает эту запись так:

add :: Nat -> (Nat -> Nat)

add a b = ...

Функция add является функцией одного аргумента, которая в свою очередь возвращает функцию одного

аргумента (Nat -> Nat). Когда мы пишем в где-нибудь в правой части функции:

... =

... (add Zero (Succ Zero)) ...

Компилятор воспринимает эту запись так:

... =

... ((add Zero) (Succ Zero)) ...

Присмотримся к этому выражению, что изменилось? У нас появились новые скобки, вокруг выражения

(add Zero). Давайте посмотрим как происходит применение:

add :: Nat -> (Nat -> Nat),

Zero :: Nat

----------------------------------------------

(add Zero) :: Nat -> Nat

Итак применение функции add к Zero возвращает новую функцию (add Zero), которая зависит от одного

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

(add Zero) :: Nat -> Nat,

(Succ Zero) :: Nat

----------------------------------------------

((add Zero) (Succ Zero)) :: Nat

И только теперь мы получили константу. Обратите внимание на то, что получившаяся константа не может

принять ещё один аргумент. Поскольку в правиле для применения функция f должна содержать стрелку, а

у нас есть лишь Nat, это значение может участвовать в других выражениях лишь на месте аргумента.

Тоже самое работает и для функций от большего числа аргументов, если мы пишем

fun :: a1 -> a2 -> a3 -> a4 -> res

... = fun a b c d

На самом деле мы пишем

fun :: a1 -> (a2 -> (a3 -> (a4 -> res)))

... = (((fun a) b) c) d

46 | Глава 3: Типы

Это очень удобно. Так, определив лишь одну функцию fun, мы получили в подарок ещё три функции

(fun a), (fun a b) и (fun a b c). С ростом числа аргументов растёт и число подарков. Если смотреть на

функцию fun, как на функцию одного аргумента, то она представляется таким генератором функций типа

a2 -> a3 -> a4 -> res, который зависит от параметра. Применение функций через пробел значительно

упрощает процесс комбинирования функций.

Поэтому в Haskell аргументы функций, которые играют роль параметров или специфических флагов, то

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

process :: Param1 -> Param2 -> Arg1 -> Arg2 -> Result

Два первых аргумента функции process выступают в роли параметров для генерации функций с типом

Arg1 -> Arg2 -> Result.

Давайте потренируемся с частичным применением в интерпретаторе. Для этого загрузим модуль Nat из

предыдущей главы:

Prelude> :l Nat

[1 of 1] Compiling Nat

( Nat. hs, interpreted )

Ok, modules loaded: Nat.

*Nat> let add = (+) :: Nat -> Nat -> Nat

*Nat> let addTwo = add (Succ (Succ Zero))

*Nat> :t addTwo

addTwo :: Nat -> Nat

*Nat> addTwo (Succ Zero)

Succ (Succ (Succ Zero))

*Nat> addTwo (addTwo Zero)

Succ (Succ (Succ (Succ Zero)))

Сначала мы ввели локальную переменную add, и присвоили ей метод (+) из класса Num для Nat. Нам

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

синоним. В данном случае мы подсказали ему, что это Nat. Затем с помощью частичного применения мы

объявили новый синоним addTwo, как мы видим из следующей строки это функция оного аргумента. Она

принимает любое значение типа Nat и прибавляет к нему двойку. Мы видим, что этой функцией можно

пользоваться также как и обычной функцией.

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

*Nat> let add2 = (+) (Succ (Succ Zero))

*Nat> add2 Zero

Succ (Succ Zero)

Мы рассмотрели частичное применение для функций в префиксной форме записи. В префиксной фор-

ме записи функция пишется первой, затем следуют аргументы. Для функций в инфиксной форме записи

существует два правила применения.

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

(*) :: a -> (b -> c),

x :: a

-----------------------------

(x *) :: b -> c

И применение справа:

(*) :: a -> (b -> c),

x :: b

-----------------------------

(* x) :: a -> c

Обратите внимание на типы аргумента и возвращаемого значения. Скобки в выражениях (x*) и (*x)

обязательны. Применением слева мы фиксируем в бинарной операции первый аргумент, а применением

справа – второй.

Поясним на примере, для этого давайте возьмём функцию минус (-). Если мы напишем (2-) 1 то мы

получим 1, а если мы напишем (-2) 1, то мы получим -1. Проверим в интерпретаторе:

*Nat> (2-) 1

*Nat> (-2) 1

< interactive>:4:2:

Структура функций | 47

No instance for (Num (a0 -> t0))

arising from a use of syntactic negation

Possible fix: add an instance declaration for (Num (a0 -> t0))

In the expression: - 2

In the expression: (- 2) 1

In an equation for ‘it’: it = (- 2) 1

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

пишем -2, компилятор воспринимает минус как унарную операцию, и думает, что мы написали константу

минус два. Это сделано для удобства, но иногда это мешает. Это единственное такое исключение в Haskell.

Давайте введём новый синоним для операции минус:

*Nat> let (#) = (-)

*Nat> (2#) 1

*Nat> (#2) 1

-1

Эти правила левого и правого применения работают и для буквенных имён в инфиксной форме записи:

*Nat> let minus = (-)

*Nat> (2 ‘minus‘ ) 1

*Nat> ( ‘minus‘ 2) 1

-1

Так если мы хотим на лету получить новую функцию, связав в функции второй аргумент мы можем

написать:

... = ... ( ‘fun‘ x) ...

Частичное применение для функций в инфиксной форме записи называют сечением (section), они бывают

соответственно левыми и правыми.

Связь с логикой

Отметим связь основного правила применения с Modus Ponens, известным правилом вывода в логике:

a -> b,

-------------

Оно говорит о том, что если у нас есть выражение из a следует b и мы знаем, что a истинно, мы смело

можем утверждать, что b тоже истинно. Если перевести это правило на Haskell, то мы получим: Если у нас

определена функция типа a -> b и у нас есть значение типа a, то мы можем получить значение типа b.

Декомпозиция и сопоставление с образцом

Декомпозиция применяется слева от знака равно, при этом наша задача состоит в том, чтобы опознать

дерево определённого вида и выделить из него некоторые поддеревья. Мы уже пользовались декомпозицией

много раз в предыдущих главах, давайте выпишем примеры декомпозиции:

not :: Bool -> Bool

not True

= ...

not False

= ...

xor :: Bool -> Bool -> Bool

xor a b = ...

show :: Show a => a -> String

show (Time h m s) = ...

addZero :: String -> String

addZero (a:[])

= ...

addZero as

= ...

(*)

Zero

= ...

(*)

(Succ b)

= ...

48 | Глава 3: Типы

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

стоят конструкторы (начинаются с большой буквы), переменные (с маленькой буквы) или символ безразлич-

ной переменой (подчёркивание).

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

ного уравнения. Так уравнение

not True

= ...

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

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

is7 :: Nat -> Bool

is7

(Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))

= True

is7

= False

С помощью переменных мы даём синонимы поддеревьям. Этими синонимами мы можем пользоваться в

правой части функции. Так в уравнении

addZero (a:[])

мы извлекаем первый элемент из списка, и одновременно говорим о том, что список может содержать

только один элемент. Отметим, что если мы хотим дать синоним всему дереву а не какой-то части, мы просто

пишем на месте аргумента переменную, как в случае функции xor:

xor a b = ...

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

Уравнения в определении синонима обходятся сверху вниз, поэтому часто безразличной переменной поль-

зуются в смысле “а во всех остальных случаях”, как в:

instance Eq Nat where

(==) Zero

Zero

= True

(==) (Succ a) (Succ b) = a == b

(==) _

= False

Переменные и безразличные переменные также могут уходить вглубь дерева сколь угодно далеко (или

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

lessThan7 :: Nat -> Bool

lessThan7

(Succ (Succ (Succ (Succ (Succ (Succ (Succ _)))))))

= False

lessThan7

= True

Декомпозицию можно применять только к значениям-константам. Проявляется интересная закономер-

ность: если для композиции необходимым элементом было значение со стрелочным типом (функция), то в

случае декомпозиции нам нужно значение с типом без стрелок (константа). Это говорит о том, что все функ-

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

ожидаем на входе функцию, то мы можем только дать ей синоним с помощью с помощью переменной или

проигнорировать её безразличной переменной.

Как в

name

(Succ (Succ Zero))

= ...

name

(Zero : Succ Zero : [])

= ...

Но не

name

Succ

= ...

name

(Zero :)

= ...

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

втором это функция типа [Nat] -> [Nat].

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

только “настоящими” значениями, то есть конструкторами, объявленными в типах. В случае композиции мы

могли пользоваться как конструкторами, так и синонимами.

Например мы не можем написать в декомпозиции:

name

(add Zero Zero)

= ...

name

(or (xor a b) True)

= ...

В Haskell декомпозицию принято называть сопоставлением с образцом (pattern matching). Термин намекает

на то, что в аргументе мы выписываем шаблон (или заготовку) для целого набора значений. Наборы значений

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

вид ожидаемого на вход дерева.

Структура функций | 49

3.4 Проверка типов

В этом разделе мы поговорим об ошибках проверки типов. Почти все ошибки, которые происходят в

Haskell, связаны с проверкой типов. Проверка типов происходит согласно правилам применения, которые

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

записи, правила для сечений работают аналогично. Давайте вспомним основное правило:

f :: a -> b,

x :: a

--------------------------

(f x) :: b

Что может привести к ошибке? В этом правиле есть два источника ошибки.

• Тип f не содержит стрелок, или f не является функцией.

• Типы x и аргумента для f не совпадают.

Вот и все ошибки. Универсальное представление всех функций в виде функций одного аргумента, значи-

тельно сокращает число различных видов ошибок. Итак мы можем ошибиться применяя значение к константе

и передав в функцию не то, что она ожидает.

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

*Nat> Zero Zero

< interactive>:1:1:

The function ‘Zero’ is applied to one argument,

but its type ‘Nat’ has none

In the expression: Zero Zero

In an equation for ‘it’: it = Zero Zero

Если перевести на русский интерпретатор говорит:

*Nat> Zero Zero

< interactive>:1:1:

Функция ’Zero’ применяется к одному аргументу,

но её тип ’Nat’ не имеет аргументов

В выражении: Zero Zero

В уравнении для ‘it’: it = Zero Zero

Компилятор увидел применение функции f x, далее он посмотрел, что x = Zero, из этого на основе

правила применения он сделал вывод о том, что f имеет тип Nat -> t, тогда он заглянул в f и нашёл там

Zero :: Nat, что и привело к несовпадению типов.

Составим ещё одно выражение с такой же ошибкой:

*Nat> True Succ

< interactive>:6:1:

The function ‘True’ is applied to one argument,

but its type ‘Bool’ has none

In the expression: True Succ

In an equation for ‘it’: it = True Succ

В этом выражении аргумент Succ имеет тип Nat -> Nat, значит по правилу вывода тип True равен (Nat

-> Nat) -> t, где t некоторый произвольный тип, но мы знаем, что True имеет тип Bool.

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

*Nat> :m +Prelude

*Nat Prelude> not (Succ Zero)

< interactive>:9:6:

Couldn’t match expected type ‘Bool’ with actual type ‘Nat’

In the return type of a call of ‘Succ’

In the first argument of ‘not’, namely ‘(Succ Zero)’

In the expression: not (Succ Zero)

50 | Глава 3: Типы

Опишем действия компилятора в терминах правила применения. В этом выражении у нас есть три зна-

чения: not, Succ и Zero. Нам нужно узнать тип выражения и проверить правильно ли оно построено.

not (Succ Zero) - ?

not :: Bool -> Bool,

Succ :: Nat -> Nat,

Zero :: Nat

----------------------------------------------------------

f x, f = not и x = (Succ Zero)

------------------------------------------------------------

f :: Bool -> Bool следовательно x :: Bool

-------------------------------------------------------------

(Succ Zero) :: Bool

Воспользовавшись правилом применения мы узнали, что тип выражения Succ Zero должен быть равен

Bool. Проверим, так ли это?

(Succ Zero) - ?

Succ :: Nat -> Nat,

Zero :: Nat

----------------------------------------------------------

f x, f = Succ, x = Zero следовательно (f x) :: Nat

----------------------------------------------------------

(Succ Zero) :: Nat

Из этой цепочки следует, что (Succ Zero) имеет тип Nat. Мы пришли к противоречию и сообщаем об

этом пользователю.

< interactive>:1:5:

Не могу сопоставить ожидаемый тип ’Bool’ с выведенным ’Nat’

В типе результата вызова ‘Succ’

В первом аргументе ‘not’, а именно ‘(Succ Zero)’

В выражении: not (Succ Zero)

Потренируйтесь в составлении неправильных выражений и посмотрите почему они не правильные. Мыс-

ленно сверьтесь с правилом применения в каждом из слагаемых.

Специализация типов при подстановке

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

на самом деле есть и другая возможность. Тип аргумента или тип значения могут быть полиморфными. В

этом случае происходит специализация общего типа. Например, при выполнении выражения:

*Nat> Succ Zero + Zero

Succ (Succ Zero)

Происходит специализация общей функции (+) :: Num a => a -> a -> a до функции (+) :: Nat ->

Nat -> Nat, которая определена в экземпляре Num для Nat.

Проверка типов с контекстом

Предположим, что у функции f есть контекст, который говорит о том, что первый аргумент принадлежит

некоторому классу f :: C a => a -> b, тогда значение, которое мы подставляем в функцию, должно быть

экземпляром класса C.

Для иллюстрации давайте попробуем сложить логические значения:

*Nat Prelude> True + False

< interactive>:11:6:

No instance for (Num Bool)

arising from a use of ‘+’

Possible fix: add an instance declaration for (Num Bool)

In the expression: True + False

In an equation for ‘it’: it = True + False

Компилятор говорит о том, что для типа Bool не

определён экземпляр для класса Num.

Проверка типов | 51

No instance for (Num Bool)

Запишем это в виде правила:

f :: C a => a -> b,

x :: T, instance C T

-----------------------------------------

(f x) :: b

Важно отметить, что x имеет конкретный тип T. Если x – значение, у которого тип с параметром, компиля-

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

такую ситуацию неопределённостью:

x :: T a => a

f :: C a => a -> b

f x :: ??

-- неопределённость

Мы видим, что тип x, это какой-то тип, одновременно принадлежащий и классу T и классу C. Но мы не

можем сказать какой это тип. У этого поведения есть исключение: по умолчанию числа приводятся к Integer,

если они не содержат знаков после точки, и к Double – если содержат.

*Nat Prelude> let f = (1.5 + )

*Nat Prelude> :t f

f :: Double -> Double

*Nat Prelude> let x = 5 + 0

*Nat Prelude> :t x

x :: Integer

*Nat Prelude> let x = 5 + Zero

*Nat Prelude> :t x

x :: Nat

Умолчания определены только для класса Num. Для этого есть специальное ключевое слово default. В

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

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

default (Integer, Double)

Работает правило: если произошла неопределённость и один из участвующих классов является Num, а все

остальные классы – это стандартные классы, определённые в Prelude, то компилятор начинает последова-

тельно пробовать все типы, перечисленые за ключевым словом default, пока один из них не подойдёт. Если

такого типа не окажется, компилятор скажет об ошибке.

Ограничение мономорфизма

С выводом типов в классах связана одна тонкость. Мы говорили, что не обязательно выписывать типы

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

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

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

мента. Эта особенность позволяет записывать выражения очень кратко. Но иногда они получаются чересчур

краткими, и вводят компилятор в заблуждение. Зайдём в интерпретатор:

Prelude> let add = (+)

Prelude> :t add

add :: Integer -> Integer -> Integer

Мы хотели определить синоним для метода плюс из класса Num, но вместо ожидаемого общего типа

получили более частный. Сработало умолчание для численного типа. Но зачем оно сработало? Если мы

попробуем дать синоним методу из класса Eq, ситуация станет ещё более странной:

Prelude> let eq = (==)

Prelude> :t eq

eq :: () -> () -> Bool

Мы получили какую-то ерунду. Если мы попытаемся загрузить модуль с этими определениями:

52 | Глава 3: Типы

module MR where

add = (+)

= (==)

то получим:

*MR> :l MR

[1 of 1] Compiling MR

( MR. hs, interpreted )

MR. hs:4:7:

Ambiguous type variable ‘a0’ in the constraint:

(Eq a0) arising from a use of ‘==’

Possible cause: the monomorphism restriction applied to the following:

eq :: a0 -> a0 -> Bool (bound at MR.hs:4:1)

Probable fix: give these definition(s) an explicit type signature

or use -XNoMonomorphismRestriction

In the expression: (==)

In an equation for ‘eq’: eq = (==)

Failed, modules loaded: none.

Компилятор жалуется о том, что в определении для eq ему встретилась неопределённость и он не смог

вывести тип. Если же мы допишем недостающие типы:

module MR where

add :: Num a => a -> a -> a

add = (+)

eq :: Eq a => a -> a -> Bool

= (==)

то всё пройдёт гладко:

Prelude> :l MR

[1 of 1] Compiling MR

( MR. hs, interpreted )

Ok, modules loaded: MR.

*MR> eq 2 3

False

Но оказывается, что если мы допишем аргументы у функций и сотрём объявления, компилятор сможет

вывести тип, и тип окажется общим. Это можно проверить в интерпретаторе. Для этого начнём новую сессию:

Prelude> let eq a b = (==) a b

Prelude> :t eq

eq :: Eq a => a -> a -> Bool

Prelude> let add a = (+) a

Prelude> :t add

add :: Num a => a -> a -> a

Запишите эти выражения в модуле без типов и попробуйте загрузить. Почему так происходит? По смыслу

определения

add a b = (+) a b

add

= (+)

ничем не отличаются друг от друга, но второе сбивает компилятор столку. Компилятор путается из-

за того, что второй вариант похож на определение константы. Мы с вами знаем, что выражение справа от

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

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

имя, они называются константными аппликативными формами (constant applicative form или сокращённо

CAF). Константы можно вычислять один раз, на то они и константы. Но если тип константы перегружен,

и мы не знаем что это за тип (если пользователь не подсказал нам об этом в объявлении типа), то нам

приходится вычислять его каждый раз заново. Посмотрим на пример:

Проверка типов | 53

res = s + s

s = someLongLongComputation 10

someLongLongComputation :: Num a => a -> a

Здесь значение s содержит результат вычисления какой-то большой-пребольшой функции. Перед компи-

лятором стоит задача вывода типов. По тексту можно определить, что у s и res некоторый числовой тип.

Проблема в том, что поскольку компилятор не знает какой тип у s конкретно в выражении s + s, он вы-

нужден вычислить s дважды. Это привело разработчиков Haskell к мысли о том, что все выражения, которые

выглядят как константы должны вычисляться как константы, то есть лишь один раз. Это ограничение называ-

ют ограничением мономорфизма. По умолчанию все константы должны иметь конкретный тип, если только

пользователь не укажет обратное в типе или не подскажет компилятору косвенно, подставив неопределённое

значение в другое значение, тип которого определён. Например, такой модуль загрузится без ошибок:

eqToOne = eq one

eq = (==)

one :: Int

one = 1

Только в этом случае мы не получим общего типа для eq: компилятор постарается вывести значение,

которое не содержит контекста. Поэтому получится, что функция eq определена на Int. Эта очень спорная

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

гораздо чаще. Немного забегая вперёд, отметим, что это поведение компилятора по умолчанию, и его можно

изменить. Компилятор даже подсказал нам как это сделать в сообщении об ошибке:

Probable fix: give these definition(s) an explicit type signature

or use -XNoMonomorphismRestriction

Мы можем активировать расширение языка, которое отменяет это ограничение. Сделать это можно

несколькими способами. Мы можем запустить интерпретатор с флагом -XNoMonomorphismRestriction:

Prelude> :q

Leaving GHCi.

$ ghci -XNoMonomorphismRestriction

Prelude> let eq = (==)

Prelude> :t eq

eq :: Eq a => a -> a -> Bool

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

{-# Language NoMonomorphismRestriction #-}

Расширение будет действовать только в рамках данного модуля.

3.5 Рекурсивные типы

Обсудим ещё одну особенность системы типов Haskell. Типы могут быть рекурсивными, то есть одним из

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

для Nat

data Nat = Zero | Succ Nat

Видите, во второй альтернативе участвует сам тип Nat. Это приводит к бесконечному числу значений. Та-

ким простым и коротким определением мы описываем все положительные числа. Рекурсивные определения

типов приводят к рекурсивным функциям. Помните, мы определяли сложение и умножение:

(+) a Zero

= a

(+) a (Succ b) = Succ (a + b)

(*) a Zero

= Zero

(*) a (Succ b) = a + (a * b)

54 | Глава 3: Типы

И та и другая функция получились рекурсивными. Они следуют по одному сценарию: сначала определяем

базу рекурсии~– тот случай, в котором мы заканчиваем вычисление функции, и затем определяем путь к

базе~– цепочку рекурсивных вызовов.

Рассмотрим тип по-сложнее. Списки:

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

Деревья значений для Nat напоминают цепочку конструкторов Succ, которая венчается конструктором

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

сток, который содержит значение неокоторого типа a. Значение заканчивается пустым списком [].

Мы можем предположить, что функции для списков также будут рекурсивными. Это и правда так. Помот-

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

всех элементов списка:

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

Посмотрим как она работает:

Prelude> map (+100) [1,2,3]

[101,102,103]

Prelude> map not [True, True, False, False, False]

[False, False, True, True, True]

Prelude> :m +Data.Char

Prelude Data.Char> map toUpper ”Hello World”

”HELLO WORLD”

Теперь опишем эту функцию. Базой рекурсии будет случай для пустого списка. В нём мы говорим, что

если элементы закончились, нам нечего больше преобразовывать, и возвращаем пустой список. Во втором

уравнении нам встретится узел дерева, который содержит конструктор :, а в дочерних узлах сидят элемент

списка a и оставшаяся часть списка as. В этом случае мы составляем новый список, элемент которого со-

держит преобразованный элемент (f a) исходного списка и оставшуюся часть списка, которую мы также

преобразуем с помощью функции map:

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

map f []

= []

map f (a:as) = f a : map f as

Какое длинное объяснение для такой короткой функции! Надеюсь, что мне не удалось сбить вас с толку.

Обратите внимание на то, что поскольку конструктор символьный (начинается с двоеточия) мы пишем его

между дочерними поддеревьями, а не сначала. Немного отвлекитесь и поэкспериментируйте с этой функци-

ей в интерпретаторе, она очень важная. Составляйте самые разные списки. Чтобы не перенабирать каждый

раз списки водите синонимы с помощью let.

Перейдём к следующей функции. Это функция фильтрации:

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

Она принимает предикат и список, угдайте что она делает:

Prelude Data.Char> filter isUpper ”Hello World”

”HW”

Prelude Data.Char> filter even [1,2,3,4,5]

[2,4]

Prelude Data.Char> filter (> 10) [1,2,3,4,5]

[]

Да, она оставляет лишь те элементы, на которых предикат вернёт истину. Потренируйтесь и с этой функ-

цией.

Теперь определение:

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

filter p []

= []

filter p (x:xs) = if p x then x : filter p xs else filter p xs

Попробуйте разобраться с ним самостоятельно, по аналогии с map. Оно может показаться немного гро-

моздким, но это ничего, совсем скоро мы узнаем как записать его гораздо проще.

Рассмотрим ещё одну функцию для списков, она называется функцией свёртки:

Рекурсивные типы | 55

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

foldr f z []

= z

foldr f z (a:as) = f a (foldr f z as)

Визуально её действие можно представить как замену всех конструкторов в дереве значения на подхо-

дящие по типу функции. В этой маленькой функции кроется невероятная сила. Посмотрим на несколько

примеров:

Prelude Data.Char> :m -Data.Char

Prelude> let xs = [1,2,3,4,5]

Prelude> foldr (:) [] xs

[1,2,3,4,5]

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

нибудь более конструктивное. Например вычислим сумму всех элементов или произведение:

Prelude> foldr (+) 0 xs

Prelude> foldr (*) 1 xs

120

Prelude> foldr max (head xs) xs

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

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

на структуре значений. Мы узнали, что константы в Haskell очень похожи на деревья, а запись констант

– на строчную запись дерева. Также мы присмотрелись к функциям и узнали, что операция определения

синонима состоит из композиции и декомпозиции значений.

name

декомпозиция

композиция

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

• Одно для функций в префиксной форме записи:

f :: a -> b,

x :: a

-------------------------------

(f x) :: b

• И два для функций в инфиксной форме записи:

Это левое сечение:

(*) :: a -> (b -> c),

x :: a

---------------------------------

(x *) :: b -> c

И правое сечение:

(*) :: a -> (b -> c),

x :: b

---------------------------------

(* x) :: a -> c

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

константы-дерева какую-нибудь часть или указать на какие константы мы реагируем в данном уравнении.

Ещё мы узнали о частичном применении. О том, что все функции в Haskell являются функциями одного

аргумента, которые возвращают константы или другие функции одного аргумента.

Мы потренировались в составлении неправильных выражений и посмотрели как компилятор на основе

правил применения узнаёт что они неправильные. Мы узнали, что такое ограничение мономорфизма и как

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

56 | Глава 3: Типы

Succ

not

Рис. 3.7: Конструкторы и синонимы

3.7 Упражнения

• Составьте в интерпретаторе как можно больше неправильных выражений и посмотрите на сообще-

ния об ошибках. Разберитесь почему выражение оказалось неправильным. Для этого проверьте типы с

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

мономорфизма.

• Потренируйтесь в интерпретаторе с функциями map, filter и foldr. Попробуйте их с самыми разными

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

упражнениях.

• В этой главе было много картинок и графических аналогий, попробуйте попрограммировать в картин-

ках. Нарисуйте определённые нами функции или какие-нибудь новые в виде деревьев. Например, это

можно сделать так. Мы будем отличать конструкторы от синонимов. Конструкторы будем рисовать в

одинарном кружке, а синонимы в двойном.

one

Nat

Succ

Zero

Рис. 3.8: Синоним-константа

Мы будем все функции писать также как и прежде, но вместо аргументов слева от знака равно и выра-

жений справа от знака равно, будем рисовать деревья.

Например, объявим простой синоним-константу (рис. 3.8). Мы будем дорисовывать сверху типы зна-

чений вместо объявления типа функции.

Несколько функций для списков. Извлечение первого элемента (рис. 3.9) и функция преобразования

всех элементов списка (рис. 3.10). Попробуйте в таком же духе определить несколько функций.

Упражнения | 57

head

[a]

Рис. 3.9: Функция извлечения первого элемента списка

map

a->b

[a]

[b]

[]

map

a->b

[a]

[b]

map

Рис. 3.10: Функция преобразования элементов списка

58 | Глава 3: Типы

Глава 4

Декларативный и композиционный

стиль

В Haskell существует несколько встроенных выражений, которые облегчают построение функций и дела-

ют код более наглядным. Их можно разделить на два вида: выражения, которые поддерживают декларативный

стиль (declarative style) определения функций, и выражения которые поддерживают композиционный стиль

(expression style).

Что это за стили? В декларативном стиле определения функций больше похожи на математическую но-

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

сложные, применяем к этим выражениям другие выражения и строим ещё большие.

В Haskell есть полноценная поддержка и того и другого стиля, поэтому конструкции которые мы рас-

смотрим в этой главе будут по смыслу дублировать друг друга. Выбор стиля скорее дело вкуса, существуют

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

4.1 Локальные переменные

Вспомним формулу вычисления площади треугольника по трём сторонам:

√

S =

p · ( p − a) · ( p − b) · ( p − c)

Где a, b и c – длины сторон треугольника, а p это полупериметр.

Как бы мы определили эту функцию теми средствами, что у нас есть? Наверное, мы бы написали так:

square a b c = sqrt (p a b c * (p a b c - a) * (p a b c - b) * (p a b c - c))

p a b c = (a + b + c) / 2

Согласитесь это не многим лучше чем решение в лоб:

square a b c = sqrt ((a+b+c)/2 * ((a+b+c)/2 - a) * ((a+b+c)/2 - b) * ((a+b+c)/2 - c)) И в том и в другом случае нам приходится дублировать выражения, нам бы хотелось чтобы определение

выглядело так же, как и обычное математическое определение:

square a b c = sqrt (p * (p - a) * (p - b) * (p - c))

p = (a + b + c) / 2

Нам нужно, чтобы p знало, что a, b и c берутся из аргументов функции square. В этом нам помогут

локальные переменные.

where-выражения

В декларативном стиле для этого предусмотрены where-выражения. Они пишутся так:

square a b c = sqrt (p * (p - a) * (p - b) * (p - c))

where p = (a + b + c) / 2

| 59

Или так:

square a b c = sqrt (p * (p - a) * (p - b) * (p - c)) where

p = (a + b + c) / 2

За определением функции следует специальное слово where, которое вводит локальные имена-

синонимы. При этом аргументы функции включены в область видимости имён. Синонимов может быть

несколько:

square a b c = sqrt (p * pa * pb * pc)

where p

= (a + b + c) / 2

pa = p - a

pb = p - b

pc = p - c

Отметим, что отступы обязательны. Haskell по отступам понимает, что эти выражения относятся к where.

Как и в случае объявления функций порядок следования локальных переменных в where-выражении не

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

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

той функции, в которой они вводятся.

Что интересно, слева от знака равно в where-выражениях можно проводить декомпозицию значений, так-

же как и в аргументах функции:

pred :: Nat -> Nat

pred x = y

where (Succ y) = x

Эта функция делает тоже самое что и функция

pred :: Nat -> Nat

pred (Succ y) = y

В where-выражениях можно определять новые функции а также выписывать их типы:

add2 x = succ (succ x)

where succ :: Int -> Int

succ x = x + 1

А можно и не выписывать, компилятор догадается:

add2 x = succ (succ x)

where succ x = x + 1

Но иногда это бывает полезно, при использовании классов типов, для избежания неопределённости при-

менения.

Приведём ещё один пример. Посмотрим на функцию фильтрации списков, она определена в Prelude:

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

filter

[]

= []

filter

(x:xs) = if p x then x : rest else rest

where rest = filter p xs

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

шейся части списка.

where-выражения определяются для каждого уравнения в определении функции:

even :: Nat -> Bool

even Zero

= res

where res = True

even (Succ Zero) = res

where res = False

even x = even res

where (Succ (Succ res)) = x

Конечно в этом примере where не нужны, но здесь они приведены для иллюстрации привязки where-

выражения к данному уравнению. Мы определили три локальных переменных с одним и тем же именем.

where-выражения могут быть и у значений, которые определяются внутри where-выражений. Но лучше

избегать сильно вложенных выражений.

60 | Глава 4: Декларативный и композиционный стиль

let-выражения

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

square a b c = let p = (a + b + c) / 2

sqrt (p * (p - a) * (p - b) * (p - c))

Слова let и in – ключевые. Выгодным отличием let-выражений является то, что они являются обычными

выражениями и не привязаны к определённому месту как where-выражения. Они могут участвовать в любой

части обычного выражения:

square a b c = let p = (a + b + c) / 2

sqrt ((let pa = p - a in p * pa) *

(let pb = p - b

pc = p - c

pb * pc))

В этом проявляется их принадлежность композиционному стилю. let-выражения могут участвовать в

любом подвыражении, они также группируются скобками. А where-выражения привязаны к уравнениям в

определении функции.

Также как и в where-выражениях, в let-выражениях слева от знака равно можно проводить декомпозицию

значений.

pred :: Nat -> Nat

pred x = let (Succ y) = x

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

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

filter

[]

= []

filter

(x:xs) =

let rest = filter p xs

if p x then x : rest else rest

4.2 Декомпозиция

Декомпозиция или сопоставление с образцом позволяет выделять из составных значений, простейшие

значения с помощью которых они были построены

pred (Succ x) = x

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

not True

= False

not False = True

Сопоставление с образцом

Декомпозицию в декларативном стиле мы уже изучили, это обычный случай разбора значений в аргу-

ментах функции. Рассмотрим одну полезную возможность при декомпозиции. Иногда нам хочется провести

декомпозицию и дать псевдоним всему значению. Это можно сделать с помощью специального символа @.

Например определим функцию, которая возвращает соседние числа для данного числа Пеано:

beside :: Nat -> (Nat, Nat)

beside

Zero

= error ”undefined”

beside

x@(Succ y) = (y, Succ x)

В выражении x“(Succ y)@ мы одновременно проводим разбор и даём имя всему значению.

Декомпозиция | 61

case-выражения

Оказывается декомпозицию можно проводить в любом выражении, для этого существуют case-

выражения:

data AnotherNat = None | One | Two | Many

deriving (Show, Eq)

toAnother :: Nat -> AnotherNat

toAnother x =

case x of

Zero

-> None

Succ Zero

-> One

Succ (Succ Zero)

-> Two

-> Many

fromAnother :: AnotherNat -> Nat

fromAnother None

= Zero

fromAnother One

= Succ Zero

fromAnother Two

= Succ (Succ Zero)

fromAnother Many

= error ”undefined”

Слова case и of – ключевые. Выгодным отличием case-выражений является то, что нам не приходит-

ся каждый раз выписывать имя функции. Обратите внимание на то, что в case-выражениях также можно

пользоваться обычными переменными и безымянными переменными.

Для проведения декомпозиции по нескольким переменным можно воспользоваться кортежами. Например

определим знакомую функцию равенства для Nat:

instance Eq Nat where

(==) a b =

case (a, b) of

(Zero,

Zero)

-> True

(Succ a’, Succ b’)

-> a’ == b’

-> False

Мы проводим сопоставление с образцом по кортежу (a, b), соответственно слева от знака -> мы прове-

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

Давайте определим функцию filter в ещё более композиционном стиле. Для этого мы заменим в исход-

ном определении where на let и декомпозицию в аргументах на case-выражение:

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

filter

a =

case a of

[]

-> []

x:xs

let rest = filter p xs

if (p x)

then (x:rest)

else rest

4.3 Условные выражения

С условными выражениями мы уже сталкивались в сопоставлении с образцом. Например в определении

функции not:

not True

= False

not False = True

В зависимости от поступающего значения мы выбираем одну из двух альтернатив. Условные выражении

в сопоставлении с образцом позволяют реагировать лишь на частичное (с учётом переменных) совпадение

дерева значения в аргументах функции.

Часто нам хочется определить более сложные условия для альтернатив. Например, если значение на

входе функции больше 2, но меньше 10, верни A, а если больше 10, верни B, а во всех остальных случаях

верни C. Или если на вход поступила строка состоящая только из букв латинского алфавита, верни A, а

в противном случае верни B. Нам бы хотелось реагировать лишь в том случае, если значение некоторого

типа a удовлетворяет некоторому предикату. Предикатами обычно называют функции типа a -> Bool. Мы

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

62 | Глава 4: Декларативный и композиционный стиль

Охранные выражения

В декларативном стиле условные выражения представлены охранными выражениями (guards). Предполо-

жим у нас есть тип:

data HowMany = Little | Enough | Many

И мы хотим написать функцию, которая принимает число людей, которые хотят посетить выставку, а

возвращает значение типа HowMany. Эта функция оценивает вместительность выставочного зала. С помощью

охранных выражений мы можем написать её так:

hallCapacity :: Int -> HowMany

hallCapacity n

| n < 10

= Little

| n < 30

= Enough

| True

= Many

Специальный символ | уже встречался нам в определении типов. Там он играл роль разделителя аль-

тернатив в сумме типов. Здесь же он разделяет альтернативы в условных выражениях. Сначала мы пишем

| затем выражение-предикат, которое возвращает значение типа Bool, затем равно и после равно – возвра-

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

вниз, до тех пор пока в одной из альтернатив предикат не вернёт значение True. Обратите внимание на то,

что нам не нужно писать во второй альтернативе:

| 10 <= n && n < 30

= Enough

Если вычислитель дошёл до этой альтернативы, значит значение точно больше либо равно 10. Поскольку

в предыдущей альтернативе предикат вернул False.

Предикат в последней альтернативе является константой True, он пройдёт сопоставление с любым зна-

чением n. В данном случае, если учесть предыдущие альтернативы мы знаем, что если вычислитель дошёл

до последней альтернативы , значение n больше либо равно 30. Для повышения наглядности кода в Prelude

определена специальная константа-синоним значению True под именем otherwise.

Определим функцию filter для списков в более декларативном стиле, для этого заменим if-выражение

в исходной версии на охранные выражения:

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

filter

[]

= []

filter

(x:xs)

| p x

= x : rest

| otherwise

= rest

where rest = filter p xs

Или мы можем разместить охранные выражения по-другому:

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

filter

[]

= []

filter

(x:xs)

| p x

= x : rest

| otherwise = rest

where rest = filter p xs

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

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

Определим с помощью охранных выражений функцию all, она принимает предикат и список, и проверяет

удовлетворяют ли все элементы списка данному предикату.

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

all p []

= True

all p (x:xs)

| p x

= all p xs

| otherwise = False

С помощью охранных выражений можно очень наглядно описывать условные выражения. Но иногда мож-

но обойтись и простыми логическими операциями. Например функцию all можно было бы определить так:

Условные выражения | 63

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

all

[]

= True

all

(x:xs)

= p x && all p xs

Или так:

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

all

xs = null (filter notP xs)

where notP x = not (p x)

Или даже так:

import Prelude(all)

Функция null определена в Prelude она возвращает True только если список пуст.

if-выражения

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

Вспомним как они выглядят:

a = if bool

then x1

else x2

Слова if, then и else – ключевые. Тип a, x1 и x2 совпадают.

Любое охранное выражение, в котором больше одной альтернативы, можно представить в виде if-

выражения и наоборот. Перепишем все функции их предыдущего подраздела с помощью if-выражений:

hallCapacity :: Int -> HowMany

hallCapacity n =

if (n < 10)

then Little

else (if n < 30

then Enough

else Many)

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

all p []

= True

all p (x:xs) = if (p x) then all p xs else False

4.4 Определение функций

Под функцией мы понимаем составной синоним, который принимает аргументы, возможно разбирает их

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

в каждом из стилей.

Уравнения

В декларативном стиле функции определяются с помощью уравнений. Пока мы видели лишь этот способ

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

определяется набором уравнений вида:

name декомпозиция1 = композиция1

name декомпозиция2 = композиция2

...

name декомпозицияN = композицияN

Где name – имя функции. В декомпозиции происходит разбор поступающих на вход значений, а в компо-

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

пор пока он не найдёт такое уравнение, для которого переданные в функции значения не подойдут в указан-

ный в декомпозиции шаблон значений (если сопоставление с образцом аргументов пройдёт успешно). Как

только такое уравнение найдено, составляется выражение справа от знака равно (композиция). Это значение

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

К примеру попробуйте вычислить в интерпретаторе выражение notT False, для такой функции:

64 | Глава 4: Декларативный и композиционный стиль

notT :: Bool -> Bool

notT True = False

Что мы увидим?

Prelude> notT False

*** Exception: < interactive>:1:4-20: Non-exhaustive patterns in function notT

Интерпретатор сообщил нам о том, что он не нашёл уравнения для переданного в функцию значения.

Безымянные функции

В композиционном стиле функции определяются по-другому. Это необычный метод, он пришёл в

Haskell из лямбда-исчисления. Функции строятся с помощью специальных конструкций, которые называ-

ются лямбда-функциями. По сути лямбда-функции являются безымянными функциями. Давайте посмотрим

на лямбда функцию, которая прибавляет к аргументу единицу:

\x -> x + 1

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

noName, а стрелку на знак равно:

noName x = x + 1

Мы получили обычную функцию Haskell, с такими мы уже много раз встречались. Зачем специальный

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

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

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

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

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

“на лету”. Предположим, что мы хотим профильтровать список чисел, мы хотим выбрать из них лишь те, что

меньше 10, но больше 2, и к тому же они должны быть чётными. Мы можем написать:

f :: [Int] -> [Int]

f = filter p

where p x = x > 2 && x < 10 && even x

При этом нам приходится давать какое-нибудь имя предикату, например p. С помощью безымянной функ-

ции мы могли бы написать так:

f :: [Int] -> [Int]

f = filter (\x -> x > 2 && x < 10 && even x)

Смотрите мы составили предикат сразу в аргументе функции filter. Выражение (\x -> x > 2 && x <

10 && even x) является обычным значением.

Возможно у вас появился вопрос, где аргумент функции? Где тот список по которому мы проводим филь-

трацию. Ответ на этот вопрос кроется в частичном применении. Давайте вычислим по правилу применения

тип функции filter:

f :: (a -> Bool) -> [a] -> [a],

x :: (Int -> Bool)

------------------------------------------------------

(f x) :: [Int] -> [Int]

После применения параметр a связывается с типом Int, поскольку при применении происходит сопостав-

ление более общего предиката a -> Bool из функции filter с тем, который мы передали первым аргументом

Int -> Bool. После этого мы получаем тип (f x) :: [Int] -> [Int] это как раз тип функции, которая прини-

мает список целых чисел и возвращает список целых чисел. Частичное применение позволяет нам не писать

в таких выражениях:

f xs = filter p xs

where p x = ...

последний аргумент xs.

К примеру вместо

Определение функций | 65

add a b = (+) a b

мы можем просто написать:

add = (+)

Такой стиль определения функций называют бесточечным (point-free).

Давайте выразим функцию filter с помощью лямбда-функций:

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

filter = \p -> \xs -> case xs of

[]

-> []

(x:xs) -> let rest = filter p xs

p x

then x : rest

else rest

Мы определили функцию filter пользуясь только элементами композиционного стиля. Обратите внима-

ние на скобки в объявлении типа функции. Я хотел напомнить вам о том, что все функции в Haskell являются

функциями одного аргумента. Это определение функции filter как нельзя лучше подчёркивает этот факт.

Мы говорим, что функция filter является функцией одного аргумента p в выражении \p -> , которая возвра-

щает также функцию одного аргумента. Мы выписываем это в явном виде в выражении \xs -> . Далее идёт

выражение, которое содержит определение функции.

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

могли бы написать:

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

filter = \p xs -> case xs of

...

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

Для тренировки определим несколько стандартных функций для работы с кортежами с помощью лямбда-

функций (все они определены в Prelude):

fst :: (a, b) -> a

fst = \(a, _) -> a

snd :: (a, b) -> b

snd = \(_, b) -> b

swap :: (a, b) -> (b, a)

swap = \(a, b) -> (b, a)

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

Аргументы мы “пристраиваем” с помощью безымянных функций.

Определим функции преобразования первого и второго элемента кортежа (эти функции определены в

модуле Control.Arrow)

first :: (a -> a’) -> (a, b) -> (a’, b)

first = \f (a, b) -> (f a, b)

second :: (b -> b’) -> (a, b) -> (a, b’)

second = \f (a, b) -> (a, f b)

Также в Prelude есть полезные функции, которые превращают функции с частичным применением в

обычны функции и наоборот:

curry :: ((a, b) -> c) -> a -> b -> c

curry = \f -> \a -> \b -> f (a, b)

uncurry :: (a -> b -> c) -> ((a, b) -> c)

uncurry = \f -> \(a, b) -> f a b

66 | Глава 4: Декларативный и композиционный стиль

Функция curry принимает функцию двух аргументов для которой частичное применение невозможно.

Это имитируется с помощью кортежей. Функция принимает кортеж из двух элементов. Функция curry (от

слова каррирование, частичное применение) превращает такую функцию в обычную функцию Haskell. А

функция uncurry выполняет обратное преобразование.

С помощью лямбда-функций можно имитировать локальные переменные. Так например можно перепи-

сать формулу для вычисления площади треугольника:

square a b c =

(\p -> sqrt (p * (p - a) * (p - b) * (p - c)))

((a + b + c) / 2)

Смотрите мы определили функцию, которая принимает параметром полупериметр p и передали в неё

значение ((a + b + c) / 2). Если в нашей функции несколько локальных переменных, то мы можем

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

4.5 Какой стиль лучше?

Основной критерий выбора заключается в том, сделает ли этот элемент код более ясным. Наглядность

кода станет залогом успешной поддержки. Его будет легче понять и улучшить при необходимости.

Далее мы рассмотрим несколько примеров определений из Prelude и подумаем, почему был выбран тот

или иной стиль. Начнём с класса Ord и посмотрим на определения по умолчанию:

-- Тип упорядочивания

data

Ordering

LT | EQ | GT

deriving (Eq, Ord, Enum, Read, Show, Bounded)

class

(Eq a) => Ord a

where

compare

:: a -> a -> Ordering

(< ), (<=), (>=), (> ) :: a -> a -> Bool

max, min

:: a -> a -> a

-- Минимальное полное определение:

(<=) или compare

-- Использование compare может оказаться более

-- эффективным для сложных типов.

compare x y

| x == y

| x <= y

| otherwise =

x <= y

compare x y /= GT

x <

compare x y == LT

x >= y

compare x y /= LT

x >

compare x y == GT

max x y

| x <= y

| otherwise =

min x y

| x <= y

| otherwise =

Все функции определены в декларативном стиле. Тип Ordering кодирует результат операции сравнения.

Два числа могут быть либо равны (значение EQ), либо первое меньше второго (значение LT), либо первое

больше второго (значение GT).

Обратите внимание на функцию compare. Мы не пишем дословное определение значений типа Ordering:

compare x y

| x == y

| x <

| x >

Какой стиль лучше? | 67

В этом случае функция compare была бы определена через две других функции класса Ord, а именно

больше > и меньше < . Мы же хотим минимизировать число функций в этом определении. Поэтому вместо

этого определения мы полагаемся на очерёдность обхода альтернатив в охранном выражении.

Если первый случай не прошёл, то во втором случае нет разницы между функциями < и <=. А если не

прошёл и этот случай, то остаётся только вернуть значение GT. Так мы определили функцию compare через

одну функцию класса Ord.

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

для списков, одна из них возможно вам уже порядком поднадоела:

-- Преобразование списка

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

map f []

= []

map f (x:xs) = f x : map f xs

-- Фильтрация списка

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

filter p []

= []

filter p (x:xs) | p x

= x : filter p xs

| otherwise = filter p xs

-- Свёртка списка

foldr

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

foldr f z []

foldr f z (x:xs) =

f x (foldr f z xs)

Приведём несколько примеров для функции foldr:

and, or :: [Bool] -> Bool

and = foldr (&& ) True

= foldr (||) False

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

[]

++ ys = ys

(x:xs) ++ ys = x : (xs ++ ys)

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

concat = foldr (++) []

Функции and и or выполняют логические операции на списках. Так каждый конструктор (:) заменяется

на соответствующую логическую операцию, а пустой список заменяется на значение, которое не влияет на

результат выполнения данной логической операции. Имеется ввиду, что функции (&& True) и (|| False)

дают тот же результат, что и функция id x = x. Функция (++) объединяет два списка, а функция concat

выполняет ту же операцию, но на списке списков.

Функция zip принимает два списка и смешивает их в список пар. Как только один из списков оборвётся

оборвётся и список-результат. Эта функция является частным случаем более общей функции zipWith, кото-

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

-- zip-ы

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

zip = zipWith (,)

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

zipWith z (a:as) (b:bs) =

z a b : zipWith z as bs

zipWith _ _ _

[]

Посмотрим как работают эти функции в интерпретаторе:

Prelude> zip [1,2,3] ”hello”

[(1,’h’),(2,’e’),(3,’l’)]

Prelude> zipWith (+) [1,2,3] [3,2,1]

[4,4,4]

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

[5,8,9]

Отметим, что в Prelude также определена обратная функция unzip:

68 | Глава 4: Декларативный и композиционный стиль

unzip

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

Она берёт список пар и разбивает его на два списка.

Пока по этим определениям кажется, что композиционный стиль совсем нигде не применяется. Он встре-

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

lines

:: String -> [String]

lines ””

[]

lines s

let (l, s’) = break (== ’\n’) s

l : case s’ of

[]

-> []

(_:s’’) -> lines s’’

Функция line разбивает строку на список строк. Эти строки были разделены в исходной строке символом

переноса ’\n’.

Функция break принимает предикат и список и возвращает два списка. В первом все элементы от начала

списка, которые не удовлетворяют предикату, а во втором все остальные. Наш предикат (== ’\n’) выделяет

все символы кроме переноса каретки. В строке

let (l, s’) = break (== ’\n’) s

Мы сохраняем все символы до ’\n’ от начала строки в переменной l. Затем мы рекурсивно вызываем

функцию lines на оставшейся части списка:

l : case s’ of

[]

-> []

(_:s’’) -> lines s’’

При этом мы пропускаем в s’ первый элемент, поскольку он содержит символ переноса каретки.

Посмотрим на ещё одну функцию для работы со строками.

words

:: String -> [String]

words s

case dropWhile Char. isSpace s of

”” -> []

s’ -> w : words s’’

where (w, s’’) = break Char. isSpace s’

Функция words делает тоже самое, что и lines, только теперь в качестве разделителя выступает пробел.

Функция dropWhile отбрасывает от начала списка все элементы, которые удовлетворяют предикату. В строке

case dropWhile Char. isSpace s of

Мы одновременно отбрасываем все первые пробелы и готовим значение для декомпозиции. Дальше мы

рассматриваем два возможных случая для строк.

”” -> []

s’ -> w : words s’’

where (w, s’’) = break Char. isSpace s’

Если строка пуста, то делать больше нечего. Если – нет, мы также как и в предыдущей функции приме-

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

функцию words на оставшейся части списка.

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

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

появлялись парами. Сведём их в таблицу:

Элемент

Декларативный стиль

Композиционный

Локальные переменные

where-выражения

let-выражения

Декомпозиция

Сопоставление с образцом

case-выражения

Условные выражения

Охранные выражения

if-выражения

Определение функций

Уравнения

лямбда-функции

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

Особенности синтаксиса

Нам встретилась новая конструкция в сопоставлении с образцом:

beside :: Nat -> (Nat, Nat)

beside

Zero

= error ”undefined”

beside

x@(Succ y) = (y, Succ x)

Она позволяет проводить декомпозицию и давать имя всему значению одновременно. Такие выражения

x(...)@ в англоязычной литературе принято называть as-patterns.

4.7 Упражнения

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

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

• Попробуйте определить функции из предыдущих глав в чисто композиционном стиле.

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

на выворот. Если вы видите, что элемент написан композиционном стиле перепишите его в деклара-

тивном и наоборот. Получившиеся функции могут показаться монстрами, но это упражнение может

помочь вам в закреплении новых конструкций и почувствовать сильные и слабые стороны того или

иного стиля.

• Определите модуль, который будет вычислять площади простых фигур, треугольника, окружности,

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

• Поток это бесконечный список, или список, у которого нет конструктора пустого списка:

data Stream a = a :& Stream a

Так например мы можем составить поток из всех чисел Пеано:

nats :: Nat -> Stream Nat

nats a = a :& nats (Succ a)

Или поток, который содержит один и тот же элемент:

constStream :: a -> Stream a

constStream a = a :& constStream a

Напишите модуль для потоков. В первую очередь нам понадобятся функции выделения частей потока,

поскольку мы не сможем распечатать поток целиком (ведь он бесконечный):

-- Первый элемент потока

head :: Stream a -> a

-- Хвост потока, всё кроме первого элемента

tail :: Stream a -> Stream a

-- n-тый элемент потока

(!! ) :: Stream a -> Int -> a

-- Берёт из потока несколько первых элементов:

take :: Int -> Stream a -> [a]

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

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

import qualified Prelude as P( определения )

Слова qualified и as – ключевые. Теперь для использования функций из модуля Prelude мы будем писать

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

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

70 | Глава 4: Декларативный и композиционный стиль

import qualified Prelude as P

import Prelude

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

Для удобства тестирования можно определить такую функцию печати потоков:

instance Show a => Show (Stream a) where

show xs =

showInfinity (show (take 5 xs))

where showInfinity x = P. init x

P.++ ”...”

Функция P. init выделяет все элементы списка кроме последнего. В данном случае она откусит от строки

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

Функции преобразования потоков:

-- Преобразование потока

map :: (a -> b) -> Stream a -> Stream b

-- Фильтрация потока

filter :: (a -> Bool) -> Stream a -> Stream a

-- zip-ы для потоков:

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

zipWith :: (a -> b -> c) -> Stream a -> Stream b -> Stream c

Функция генерации потока:

iterate :: (a -> a) -> a -> Stream a

Эта функция принимает два аргумента: функцию следующего элемента потока и значение первого эле-

мента потока и возвращает поток:

iterate f a = a :& f a :& f (f a) :& f (f (f a)) :& ...

Так с помощью этой функции можно создать поток всех чисел Пеано от нуля или постоянный поток:

nats

= iterate Succ Zero

constStream a

= iterate (\x -> x) a

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

пока мы не будем вдаваться в детали того как это работает, просто попробуйте определить этот модуль и

посмотрите в интерпретаторе, что получится.

Упражнения | 71

Глава 5

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

Функцией высшего порядка называют функцию, которая может принимать на вход функции или возвращать

функции в качестве результата. За счёт частичного применения в Haskell все функции, которые принимают

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

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

язык. В Haskell функции являются очень гибким объектом, они позволяют выделять сложные способы ком-

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

определяет лишь базовые функции, получая остальные “на лету” применением двух-трёх операций, это вы-

глядит примерно как (2+3)*5, где вместо чисел стоят базовые функции, а операции + и * составляют новые

функции из простейших.

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

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

ляют по ним другие. Эти функции используются в Haskell очень часто. Все они живут в модуле Data.Function.

Модуль Prelude экспортирует их из этого модуля.

Функция тождества

Начнём с самой простой функции. Это функция id. Она ничего не делает с аргументом, просто возвращает

его:

id :: a -> a

id x = x

Зачем нам может понадобиться такая функция? Сама по себе она бесполезна. Она приобретает ценность

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

Константная функция

Следующая функция const принимает значение и возвращает постоянную функцию. Эта функция будет

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

const :: a -> b -> a

const a _ = a

Функция const является конструктором постоянных функций, так например мы получаем пятёрки на

любой аргумент:

Prelude> let onlyFive = const 5

Prelude> :t onlyFive

onlyFive :: b -> Integer

Prelude> onlyFive ”Hi”

Prelude> onlyFive (1,2,3)

Prelude> map onlyFive ”abracadabra”

[5,5,5,5,5,5,5,5,5,5,5]

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

С её помощью мы можем легко построить и постоянную функцию двух аргументов:

const2 a = const (const a)

Вспомним определение для && :

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

(&& ) True

= x

(&& ) False

= False

С помощью функций id и const мы можем сократить число аргументов и уравнений:

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

(&& ) a = if a then id else (const False)

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

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

(||) a = if a then (const True) else id

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

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

ций:

(. ) :: (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

Zero

= a

add

(Succ b) = Succ (add a b)

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

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

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

foldNat zero succ Zero

= zero

foldNat zero succ (Succ b) = succ (foldNat zero succ b)

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

add :: Nat -> Nat -> Nat

add = foldNat

(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 -> Succ x)

\x -> Succ (Succ x)

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

(\x -> Succ (Succ x)) three

Succ (Succ three)

Succ (Succ (Succ (Succ (Succ x))))

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

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

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

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

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

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

Prelude> f 2

0.6330525927559899

Prelude> f 15

0.7978497904127007

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

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

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

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

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

. id

id . f

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

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

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

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

const a

== const a

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

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

Функция перестановки

Функция перестановки flip принимает функцию двух аргументов и меняет аргументы местами:

flip

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

flip f x y = f y x

К примеру:

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

-2

Prelude> foldr (flip (-)) 0 [1,2,3,4]

-10

Иногда это бывает полезно.

Функция on

Функция on (от англ. на) перед применением бинарной функции пропускает аргументы через унарную

функцию:

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

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

Она часто используется в сочетании с функцией sortBy из модуля Data.List. Эта функция имеет тип:

sortBy :: (a -> a -> Ordering) -> [a] -> [a]

Она сортирует элементы списка согласно некоторой функции упорядочивания f :: (a -> a -> Ordering).

С помощью функции on мы можем легко составить такую функцию на лету:

let xs = [(3, ”John”), (2, ”Jack”), (34, ”Jim”), (100, ”Jenny”), (-3, ”Josh”)]

Prelude> :m +Data.List Data.Function

Prelude Data.List Data.Function>

Prelude Data.List Data.Function> sortBy (compare ‘on‘ fst) xs

[(-3,”Josh”),(2,”Jack”),(3,”John”),(34,”Jim”),(100,”Jenny”)]

Prelude Data.List Data.Function> map fst (sortBy (compare ‘on‘ fst) xs)

[-3,2,3,34,100]

Prelude Data.List Data.Function> map snd (sortBy (compare ‘on‘ fst) xs)

[”Josh”,”Jack”,”John”,”Jim”,”Jenny”]

Мы импортировали в интерпретатор модуль Data.List для функции sortBy а также модуль

Data.Function для функции on. Они не импортируются модулем Prelude.

Выражением (compare ‘on‘ fst) мы составили функцию

\a b -> compare (fst a) (fst b)

fst = \(a, b) -> a

Тем самым ввели функцию упорядочивания на парах, которая будет сравнивать пары по первому элемен-

ту. Отметим, что аналогичного эффекта можно добиться с помощью функции comparing из модуля Data.Ord.

Функция применения

Ещё одной очень полезной функцией является функция применения ($). Посмотрим на её определение:

($) :: (a -> b) -> a -> b

f $ x

f x

На первый взгляд её определение может показаться бессмысленным. Зачем нам специальный знак для

применения, если у нас уже есть пробел? Для ответа на этот вопрос нам придётся познакомиться с приори-

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

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

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

В Haskell очень часто используются бинарные операции для составления функций “на лету”. В этом по-

могает и частичное применение, мы можем в одном выражении применить к функции часть аргументов,

построить из неё новую функцию с помощью какой-нибудь такой бинарной операции и всё это передать в

другую функцию!

Для сокращения числа скобок нам понадобится разобраться в понятии приоритета операции. Так напри-

мер в выражении

> 2 + 3 * 10

Мы полагаем, что умножение имеет больший приоритет чем сложение и со скобками это выражение

будет выглядеть так:

> 2 + (3 * 10)

Фраза “больший приоритет” означает: сначала умножение потом сложение. Мы всегда можем изменить

поведение по умолчанию с помощью скобок:

> (2 + 3) * 10

В Haskell приоритет функций складывается из двух понятий: старшинство и ассоциативность. Старшин-

ство определяется числами, они могут быть от 0 до 9. Чем больше это число, тем выше приоритет функций.

Старшинство используется вычислителем для группировки разных операций, например (+) имеет стар-

шинство 6, а (*) имеет старшинство 7. Поэтому интерпретатор сначала ставит скобки вокруг выражения с

(*), а затем вокруг (+). Считается, что обычное префиксное применение имеет высший приоритет 10. Нельзя

задать приоритет выше применения, это значит, что операция “пробел” будет всегда выполняться первой.

Ассоциативность используется для группировки одинаковых операций, например мы видим:

1+2+3+4

Как нам быть? Мы можем группировать скобки слева направо:

((1+2)+3)+4

Или справа налево:

1+(2+(3+4))

Ответ на этот вопрос даёт ассоциативность, она бывает левая и правая. Например операции (+) (-) и (*)

являются лево-ассоциативными, а операция возведения в степень (^) является право-ассоциативной.

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

1 ^ 2 ^ 3 ==

1 ^ (2 ^ 3)

Приоритет функции можно узнать в интерпретаторе с помощью команды :i:

*FunNat> :m Prelude

Prelude> :i (+)

class (Eq a, Show a) => Num a where

(+) :: a -> a -> a

...

-- Defined in GHC.Num

infixl 6 +

Prelude> :i (*)

class (Eq a, Show a) => Num a where

...

(*) :: a -> a -> a

...

-- Defined in GHC.Num

infixl 7 *

Prelude> :i (^)

(^) :: (Num a, Integral b) => a -> b -> a

-- Defined in GHC.Real

infixr 8 ^

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

Приоритет указывается в строчках infixl 6 + и infixl 7 *. Цифра указывает на старшинство операции,

а суффикс l (от англ. left – левая) или r (от англ. right – правая) на ассоциативность.

Если мы создали свою функцию, мы можем определить для неё ассоциативность. Для этого мы пишем в

коде:

module Fixity where

import Prelude(Num(.. ))

infixl 4 ***

infixl 5 +++

infixr 5 ‘neg‘

(***) = (*)

(+++) = (+)

neg

= (-)

Мы ввели новые операции и поменяли старшинство операций сложения и умножения местами и изме-

нили ассоциативность у вычитания. Проверим в интерпретаторе:

Prelude> :l Fixity

[1 of 1] Compiling Fixity

( Fixity. hs, interpreted )

Ok, modules loaded: Fixity.

*Fixity> 1 + 2 * 3

*Fixity> 1 +++ 2 *** 3

*Fixity> 1 - 2 - 3

-4

*Fixity> 1 ‘neg‘ 2 ‘neg‘ 3

Посмотрим как это вычислялось:

+++

*** 3

+++

***

1 ‘neg‘ 2 ‘neg 3‘ ==

1 ‘neg‘ (2

‘neg‘ 3)

Также в Haskell есть директива infix это тоже самое, что и infixl.

Приоритет функции композиции

Посмотрим на приоритет функции композиции:

Prelude> :i (. )

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

-- Defined in GHC.Base

infixr 9 .

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

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

fun a = fun1 a . fun2 (x1 + x2) . fun3 . (+x1)

Приоритет функции применения

Теперь посмотрим на полное определение функции применения:

infixr 0 $

($) :: (a -> b) -> a -> b

f $ x

f x

Ответ на вопрос о полезности этой функции кроется в её приоритете. Ей назначен самый низкий прио-

ритет. Она будет исполняться в последнюю очередь. Очень часто возникают ситуации вроде:

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

foldNat zero succ (Succ b) = succ (foldNat zero succ b)

С помощью функции применения мы можем переписать это определение так:

foldNat zero succ (Succ b) = succ $ foldNat zero succ b

Если бы мы написали без скобок:

... = succ foldNat zero succ b

То выражение было бы сгруппировано так:

... = (((succ foldNat) zero) succ) b

Но поскольку мы поставили барьер в виде операции ($) с низким приоритетом, группировка скобок

произойдёт так:

... = (succ $ ((foldNat zero) succ) b)

Это как раз то, что нам нужно. Преимущество этого подхода проявляется особенно ярко если у нас

несколько вложенных функций на конце выражения:

xs :: [Int]

xs = reverse $ map ((+1) . (*10)) $ filter even $ ns 40

ns :: Int -> [Int]

ns 0

= []

ns n

= n : ns (n - 1)

В списке xs мы сначала создаём в функции ns убывающий список чисел, затем оставляем лишь чётные,

потом применяем два арифметических действия ко всем элементам списка, затем переворачиваем список.

Проверим работает ли это в интерпретаторе, заодно поупражняемся в композиционном стиле:

Prelude> let ns n = if (n == 0) then [] else n : ns (n - 1)

Prelude> let even x = 0 == mod x 2

Prelude> let xs = reverse $ map ((+1) . (*10)) $ filter even $ ns 20

Prelude> xs

[21,41,61,81,101,121,141,161,181,201]

Если бы не функция применения нам пришлось бы написать это выражение так:

xs = reverse (map ((+1) . (*10)) (filter even (ns 40)))

5.3 Функциональный калькулятор

Мне бы хотелось сделать акцент на одном из вступительных предложений этой главы:

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

базовые функции, получая остальные “на лету” применением двух-трёх операций, это выглядит

примерно как (2+3)*5, где вместо чисел стоят базовые функции, а операции + и * составляют

новые функции из простейших.

Такие обобщённые функции как id, const, (. ), map filter позволяют очень легко комбинировать различ-

ные функции. Бесточечный стиль записи функций превращает функции в простые значения или значения-

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

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

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

том, что теперь мы применяем обычные операции сложения умножения к функциям, аргумент которых сов-

падает по типу. Например для того чтобы умножить функции \t -> t+2 и \t -> t+3 мы составляем новую

функцию \t -> (t+2) * (t+3), которая получает на вход значение t применяет его к каждой из функций и

затем умножает результаты:

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

module FunNat where

import Prelude(Show(.. ), Eq(.. ), Num(.. ), error)

instance Show (t -> a) where

show _ = error ”Sorry, no show. It’s just for Num”

instance Eq (t -> a) where

(==) _ _ = error ”Sorry, no Eq. It’s just for Num”

instance Num a => Num (t -> a) where

(+) = fun2 (+)

(*) = fun2 (*)

(-) = fun2 (-)

abs

= fun1 abs

signum

= fun1 signum

fromInteger = const . fromInteger

fun1 :: (a -> b) -> ((t -> a) -> (t -> b))

fun1 = (. )

fun2 :: (a -> b -> c) -> ((t -> a) -> (t -> b) -> (t -> c))

fun2 op a b = \t -> a t ‘op‘ b t

Функции fun1 и fun2 превращают функции, которые принимают значения, в функции, которые прини-

мают другие функции.

Из-за контекста класса Num нам пришлось объявить два фиктивных экземпляра для классов Show и Eq.

Загрузим модуль FunNat в интерпретатор и посмотрим что же у нас получилось:

Prelude> :l FunNat. hs

[1 of 1] Compiling FunNat

( FunNat. hs, interpreted )

Ok, modules loaded: FunNat.

*FunNat> 2 2

*FunNat> 2 5

*FunNat> (2 + (+1)) 0

*FunNat> ((+2) * (+3)) 1

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

значение к константе. Но на самом деле 2 это не константа, а значение 2 :: Num a => a и подспудно к двойке

применяется функция fromInteger. Поскольку в нашем модуле мы определили экземпляр Num для функций,

второе число 2 было конкретизировано по умолчанию до Integer, а первое число 2 было конкретизировано

до Integer -> Integer. Компилятор вывел из контекста, что под 2 мы понимаем функцию. Функция была

создана с помощью метода fromInteger. Эта функция принимает любое значение и возвращает двойку.

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

составлять и такие выражения:

*FunNat> let f = ((+) - (*))

*FunNat> f 1 2

Как была вычислена эта функция? Мы определили экземпляр функций для значений типа Num a => t

-> a. Если мы вспомним, что функция двух аргументов на самом деле является функцией одного аргумента:

Num a => t1 -> (t2 -> a), мы заметим, что тип Num a => (t2 -> a) принадлежит Num, теперь если мы

обозначим его за a’, то мы получим тип Num a’ => t1 -> a’, это совпадает с нашим исходным экземпляром.

Получается, что за счёт механизма частичного применения мы одним махом определили экземпляры Num

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

Итак функция f имеет вид:

\t1 t2 -> (t1 + t2) - (t1 * t2)

Подставим значения:

Функциональный калькулятор | 79

(\t1 t2 -> (t1 + t2) - (t1 * t2)) 1 2

(\t2 -> (1 + t2) - (1 * t2) 2

(1 + 2) - (1 * 2)

3 - 2

Теперь давайте составим несколько выражений с обобщёнными функциями. Для этого добавим в модуль

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

для списков и класс Ord:

module FunNat where

import Prelude(Show(.. ), Eq(.. ), Ord(.. ), Num(.. ), error)

import Data.Function(id, const, (. ), ($), flip, on)

import Prelude(map, foldr, filter, zip, zipWith)

...

и загрузим модуль в интерпретатор:

Prelude> :load FunNat

[1 of 1] Compiling FunNat

( FunNat. hs, interpreted )

Ok, modules loaded: FunNat.

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

числа.

*FunNat> let f = abs $ id * 2 - 10

*FunNat> f 2

*FunNat> f 10

Давайте посмотрим как была составлена эта функция:

abs $ id * 2 - 10

abs $ (id * 2) - 10

-- приоритет умножения

abs $ (\x -> x * \x -> 2) - 10

-- развернём id и 2

abs $ (\x -> x * 2) - 10

-- по определению (*) для функций

abs $ (\x -> x * 2) - \x -> 10

-- развернём 10

abs $ \x -> (x * 2) - 10

-- по определению (-) для функций

\x -> abs x . \x -> (x * 2) - 10

-- по определению abs для функций

\x -> abs ((x * 2) - 10)

-- по определению (.)

\x -> abs ((x * 2) - 10)

Функция возведения в квадрат:

*FunNat> let f = id * id

*FunNat> map f [1,2,3,4,5]

[1,4,9,16,25]

*FunNat> map (id * id - 1) [1,2,3,4,5]

[0,3,8,15,24]

Обратите внимание на краткость записи. В этом выражении (id * id - 1) проявляется основное пре-

имущество бесточечного стиля, избавившись от аргументов, мы можем пользоваться функциями так, словно

это простые значения. Этот приём используется в Haskell очень активно. Пока нам встретились лишь две

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

столкнётесь с целым морем подобных операций. Все они служат одной цели, они прячут аргументы функции,

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

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

вида.

Возведём в четвёртую степень:

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

*FunNat> map (f . f) [1,2,3,4,5]

[1,16,81,256,625]

Составим функцию двух аргументов, которая будет вычислять сумму квадратов двух аргументов:

*FunNat> let x = const id

*FunNat> let y = flip $ const id

*FunNat> let d = x * x + y * y

*FunNat> d 1 2

*FunNat> d 3 2

Так мы составили функцию, ни прибегая к помощи аргументов. Эти выражения могут стать частью других

выражений:

*FunNat> filter

((< 10) . d 1) [1,2,3,4,5]

[1,2]

*FunNat> zipWith d [1,2,3] [3,2,1]

[10,8,10]

*FunNat> foldr (x*x - y*y) 0 [1,2,3,4]

3721610024

*FunNat> zipWith ((-) * (-) + const id) [1,2,3] [3,2,1]

[7,2,5]

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

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

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

других функций!

5.4 Функции, возвращающие несколько значений

Как было сказано ранее функции, которые возвращают несколько значений, реализованы в Haskell с по-

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

decons :: Stream a -> (a, Stream a)

decons (a :& as) = (a, as)

Здесь функция возвращает сразу два значения. Но всегда ли уместно пользоваться кортежами? Для ком-

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

с помощью сопоставления с образцом и затем использовать эти значения в других функциях. Посудите сами

если у нас есть функции:

f :: a

-> (b1, b2)

g :: b1 -> (c1, c2)

h :: b2 -> (c3, c4)

Мы уже не сможем комбинировать их так просто как если бы это были обычные функции без кортежей.

q x = (\(a, b) -> (g a, h b)) (f x)

В случае пар нам могут прийти на помощь функции first и second:

q = first g . second h . f

Если мы захотим составить какую-нибудь другую функцию из q, то ситуация заметно усложнится. Функ-

ции, возвращающие кортежи, сложнее комбинировать в бесточечном стиле. Здесь стоит вспомнить правило

Unix.

Пишите функции, которые делают одну вещь, но делают её хорошо.

Функции, возвращающие несколько значений | 81

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

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

Если функция возвращает несколько значений, попытайтесь разбить её на несколько, которые возвраща-

ют лишь одно значение. Часто бывает так, что эти значения тесно связаны между собой и такую функцию

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

задуматься о создании нового типа данных.

Например в качестве точки на плоскости можно использовать пару (Float, Float). В этом случае, если

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

возвращают точки:

rotate

:: Float -> (Float, Float) -> (Float, Float)

norm

:: (Float, Float) -> (Float, Float)

translate

:: (Float, Float) -> (Float, Float) -> (Float, Float)

...

Все они стараются делать несколько дел одновременно, возвращая кортежи. Но мы можем изменить

ситуацию определением новых типов:

data Point

= Point

Float Float

data Vector = Vector Float Float

data Angle

= Angle

Float

Объявления функций станут более краткими и наглядными.

rotate

:: Angle

-> Point -> Point

norm

:: Point

-> Point

translate

:: Vector -> Point -> Point

...

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

Познакомимся с функцией fix или комбинатором неподвижной точки. По хорошему об этой функции

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

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

она может показаться вам очень необычной. Для начала посмотрим на её тип:

Prelude> :m +Data.Function

Prelude Data.Function> :t fix

fix :: (a -> a) -> a

Странно fix принимает функцию и возвращает значение, обычно всё происходит наоборот. Теперь по-

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

fix f = let x = f 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

Zero

= z

foldNat z

(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. Их можно разбить на несколько типов:

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

= \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

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

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

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

:: cat a a

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

Если присмотреться к типам функций, можно понять, что тип-экземпляр cat принимает два параметра.

Совсем как тип функции (a -> b). Формально его можно записать в префиксной форме так (-> ) a b.

Получается, что тип cat это что-то вроде функции. Это некоторые сущности, у которых есть понятия

тождества и композиции.

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

необычные функции, функции которые преобразуют ленты значений. Функции id и (. ) мы определим,

сделав наш тип St экземпляром класса Category. Также определите постоянный преобразователь. Он

на любой вход возвращает одно и то же число, и преобразователь, который будет накапливать сумму

поступающих на вход значений, по-другому такой преобразователь называют интегратором:

const

:: a -> St b a

integral :: Num a => St a a

• Перепишите с помощью fix несколько стандартных функций для списков. Например map, foldr, foldl,

zip, repeat, cycle, iterate.

Старайтесь найти наиболее краткое выражение, пользуйтесь функциями высшего порядка и частичным

применением. Например рассмотрим функцию repeat:

repeat :: a -> [a]

repeat a = a : repeat a

Запишем с fix:

repeat a = fix $ \xs -> a : xs

Заметим, что мы можем избавиться от аргумента xs с помощью сечения:

repeat a = fix (a:)

Но мы можем пойти ещё дальше, если вспомним, что функция двух аргументов (:) является функцией

от одного аргумента (:) :: a -> ([a] -> [a]), которая возвращает функцию одного аргумента:

repeat = fix . (:)

Смотрите в этом выражении мы составили композицию двух функций. Функция (:) примет первый

аргумент и вернёт функцию, как раз то, что и нужно для fix.

Упражнения | 85

Глава 6

Функторы и монады: теория

Мы научились комбинировать функции наиболее общего типа a -> b. В этой главе мы посмотрим на

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

функции, результат которых имеет некоторую известную нам структуру. Среди них функции, которые могут

вычислить значение или упасть, или функции, которые возвращают сразу несколько вариантов значений.

Для составления таких функций из простейших в Haskell предусмотрено несколько классов типов. Это функ-

торы и монады. Их мы и рассмотрим в этой главе.

6.1 Композиция функций

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

общего типа:

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

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

Композиция двух функций f и g это такая функция, в которой мы сначала применяем g, а затем f. Для того

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

аргументы местами.

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

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

Мы будем изображать функции кружками, а значения – стрелками (рис. 6.1). Значения словно текут от

узла к узлу по стрелкам. Поскольку тип стрелки выходящей из f совпадает с типом стрелки входящей в g мы

можем соединить их и получить составную функцию (f>> g).

f>>g

Рис. 6.1: Композиция функций

86 | Глава 6: Функторы и монады: теория

Класс Category

С помощью операции композиции можно обобщить понятие функции. Для этого существует класс

Category:

class Category cat where

:: cat a a

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

Функция cat это тип с двумя параметрами, в котором выделено специальное значение id, которое остав-

ляет аргумент без изменений. Также мы можем составлять из простых функций сложные с помощью компо-

зиции, если функции совпадают по типу. Здесь мы для наглядности также заменили метод (. ) на (>> ), но

суть остаётся прежней. Для любого экземпляра класса должны выполняться свойства:

>> id

== f

id >> f

== f

f >> (g >> h) == (f >> g) >> h

Первые два свойства говорят о том, что id является нейтральным элементом для (>> ) слева и справа.

Третье свойство говорит о том, что нам не важно в каком порядке проводить композицию. Можно проверить,

что эти правила выполнены для функций.

Специальные функции

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

a -> m b

Смотрите вместо произвольного типа b функция возвращает m b. Единственное, что будет меняться от

раздела к разделу это тип m. Добавив этот тип к результату, мы сузили область значений функции. Простым

примером таких функций могут быть функции, которые возвращают списки:

a -> [b]

Если раньше наши функции могли возвращать произвольное значение b, то теперь мы знаем, что все

результирующие значения таких функций будут списками.

При этом для каждого такого m мы попытаемся построить свой замкнутый мир специальных функций a

-> m b. Он будет жить внутри вселенной всех произвольных функций типа a -> b. В этом нам поможет

специальный класс типов, который называется категорией Клейсли (эта конструкция носит имя математика

Хенрика Клейсли).

class Kleisli m where

idK

:: a -> m a

(*> ) :: (a -> m b) -> (b -> m c) -> (a -> m c)

Этот класс является классом Category в мире наших специальных функций. Если мы сотрём все буквы m,

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

*> idK

== f

idK *> f

== f

f *> (g *> h) == (f *> g) *> h

Взаимодействие с внешним миром

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

сможем комбинировать специальные функции с обычными?

Поскольку слева у нашей специальной функции обычный общий тип, то с этой стороны мы можем вос-

пользоваться обычной функцией композиции >> . Но как быть при композиции справа? Нам нужна функция

< Назад Далее >

Канал с обзорами, анонсами новинок и книжными подборками

Книжный Вестник

Бот для удобного поиска книг (если не нашлось на сайте)

Поиск книг

Свежие любовные романы в удобных форматах

Любовные романы

О психологии, саморазвитии и личностном росте

Саморазвитие

Детективы и триллеры, все новинки

Детективы

Фантастика и фэнтези, все новинки

Фантастика

Отборные классические книги

Классика

Библиотека с любовными романами, которая наверняка придётся по вкусу женской части аудитории

Любовные романы

Библиотека с фантастикой и фэнтези, а также смежных жанров

Фантастика

Самые популярные книги в формате фб2

Топ фб2 книги