суббота, 17 сентября 2011 г.

Изучай Хаскель ради добра! Моноиды

Вводное инфо на Хабре: http://habrahabr.ru/blogs/Haskell/128586/

В этой главе представлен еще один полезный и веселый класс типов: Monoid. Этот класс типов существует для типов, чьи значения могут быть объединены вместе с помощью бинарной операции. Мы рассмотрим, что именно представляют из себя моноиды и что утверждают их законы. Затем мы рассмотрим некоторые моноиды в Хаскеле и то, как они могут быть полезны.

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

Оборачивание существующего типа в новый тип



Пока что вы научились создавать свои алгебраические типы данных, используя ключевое слово data. Вы также увидели, как можно давать синонимы имеющимся типам, с применением ключевого слова type. В этом разделе мы рассмотрим, как создаются новые типы на основе имеющихся типов данных, используя ключевое слово newtype. Мы также, в первую очередь, поговорим о том, зачем бы нам это было нужно.

В главе 11 вы увидели пару способов для спискового типа быть аппликативным функтором. Один из них состоит в том, чтобы заставить <*> брать каждую функцию из списка, являющегося ее левым параметром, и применяет ее к каждому значению в списке, который находится справа, что в результате возвращает все возможные комбинации применения функции из левого списка к значению в правом списке:

ghci> [(+1),(*100),(*5)] <*> [1,2,3]
[2,3,4,100,200,300,5,10,15]

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

Но списки уже являются экземпляром Applicative, поэтому как нам сделать списки также экземпляром Applicative вторым способом? Как вы узнали, для этой цели был введен тип ZipList a. Этот тип имеет один конструктор значения, ZipList, который имеет только одно поле. Мы помещаем оборачиваемый нами список в это поле. Далее ZipList делается экземпляром Applicative, чтобы когда нам нужно использовать списки в качестве аппликативных функторов для застегивания, мы просто оборачиваем их с помощью конструктора ZipList. Как только мы закончили, мы разворачивать их с помощью getZipList:

ghci> getZipList $ ZipList [(+1),(*100),(*5)] <*> ZipList [1,2,3] $
[2,200,15]

Итак, какое отношение это имеет к ключевому слову newtype? Хорошо, подумайте, как бы мы могли написать объявление data для нашего типа ZipList a. Вот один из способов:

data ZipList a = ZipList [a]

Это тип, который обладает лишь одним конструктором значения, и этот конструктор значения имеет только одно поле, которое является списком сущностей. Мы также могли бы использовать синтаксис записей, чтобы автоматически получать функцию, извлекающую список из ZipList:

data ZipList a = ZipList { getZipList :: [a] }

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

Ключевое слово newtype в Хаскеле создано специально для тех случаев, когда мы хотим просто взять один тип и обернуть его во что-либо, чтобы представить его как другой тип. В существующих сейчас библиотеках ZipList a определен вот так:

newtype ZipList a = ZipList { getZipList :: [a] }

Вместо ключевого слова data используется ключевое слово newtype. Теперь разберемся, почему. Ну, к примеру, newtype быстрее. Если вы используете ключевое слово data для оборачивания типа, появляются накладные расходы на все это оборачивание и разворачивание, когда ваша программа выполняется. Но если вы используете newtype, Хаскель знает, что вы просто используете его для оборачивания существующего типа в новый тип (отсюда название), т. к. вы хотите чтобы внутренне он остался тем же, но имел иной тип. По этой причине Хаскель может избавиться от оборачивания и разворачивания как только он решит, какое значение какого типа.

Так почему бы не использовать просто newtype вместо data всегда? Когда вы создаете новый тип из имеющегося типа, используя ключевое слово newtype, у вас может быть только один конструктор значения, и этот конструктор значения может иметь только одно поле. Но с помощью data вы можете создавать типы данных, которые имеют несколько конструкторов значения, и каждый конструктор может иметь ноль или более полей:

data Profession = Fighter | Archer | Accountant

data Race = Human | Elf | Orc | Goblin

data PlayerCharacter = PlayerCharacter Race Profession

При использовании newtype мы также можем использовать ключевое слово deriving, так же, как мы делали бы это с data. Мы можем порождать экземпляры для Eq, Ord, Enum, Bounded, Show, и Read. Если мы породим экземпляр для класса типа, оборачиваемый нами тип уже должен быть в этом классе типов. Это логично, поскольку newtype всего лишь оборачивает существующий тип. Поэтому теперь если мы сделаем следующее, мы можем печатать и сравнивать значения нашего нового типа:

newtype CharList = CharList { getCharList :: [Char] } deriving (Eq, Show)

Давайте попробуем:
ghci> CharList "this will be shown!"
CharList {getCharList = "this will be shown!"}
ghci> CharList "benny" == CharList "benny"
True
ghci> CharList "benny" == CharList "oisters"
False

В данном конкретном случае использования newtype конструктор значения имеет следующий тип:

CharList :: [Char] -> CharList

Он берет значение типа [Char], например "my sharona" и возвращает значение типа CharList. Из предыдущих примеров, где мы использовали конструктор значения CharList, видно, что действительно так оно и есть. И наоборот, функция getCharList, которая была генерирована за нас, потому как мы использовали синтаксис записей в нашем newtype, имеет следующий тип:

getCharList :: CharList -> [Char]

Она берет значение CharList и преобразует его в значение [Char]. Вы можете воспринимать это как оборачивание и разворачивание, но вы также можете воспринимать это как преобразование значений из одного типа в другой.

Использование newtype для создания экземпляров классов типов

Часто мы хотим сделать наши типы экземплярами определенных классов типов, но параметры типа просто не соответствуют тому, что мы хотим сделать. Сделать Maybe экземпляром Functor просто, потому что класс типов Functor определен вот так:

class Functor f where
    fmap :: (a -> b) -> f a -> f b

Поэтому мы просто начинаем с этого:

instance Functor Maybe where

А потом реализуем fmap.

Все параметры типа согласуются, потому что Maybe занимает место f в определении класса типов Functor. Если взглянуть на fmap, как если бы она работала только с Maybe, в итоге она ведет себя вот так:

fmap :: (a -> b) -> Maybe a -> Maybe b


Разве это не замечательно? Теперь, что если мы захотели бы сделать кортеж экземпляром Functor так, чтобы когда мы отражаем кортеж с помощью функции, используя fmap, она применяется к первому элементу кортежа? Таким образом, выполнение fmap (+3) (1,1) вернуло бы (4, 1). Оказывается, что написание экземпляра для этого отчасти затруднительно. При использовании Maybe мы просто можем сказать instance Functor Maybe where, так как только конструкторы типа, принимающие ровно один параметр, могут быть сделаны экземплярами Functor. Но, похоже, нет способа сделать что-либо подобное при использовании (a, b) так, чтобы в итоге изменялся только параметр a, когда мы используем fmap. Чтобы обойти эту проблему, мы можем сделать новый тип из нашего кортежа с помощью newtype так, чтобы второй параметр типа представлял тип первого компонента в кортеже:

newtype Pair b a = Pair { getPair :: (a, b) }

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

instance Functor (Pair c) where
    fmap f (Pair (x, y)) = Pair (f x, y)

Как вы можете видеть, мы можем производить сопоставление типов, объявленных через newtype, с образцом. Мы производим сопоставление, чтобы получить лежащий в основе кортеж, применяем функцию f к первому компоненту в кортеже, а потом используем конструктор значения Pair, чтобы преобразовать кортеж обратно в наш Pair b a. Если мы представим, какого типа была бы fmap, если бы она работала только с нашими новыми парами, она выглядела бы вот так:

fmap :: (a -> b) -> Pair c a -> Pair c b

Опять-таки, мы сказали instance Functor (Pair c) where, и поэтому Pair c заняло место f в определении класса типов для Functor:

class Functor f where
    fmap :: (a -> b) -> f a -> f b

Теперь, если мы преобразуем кортеж в Pair b a, мы можем использовать с ним fmap, и функция будет отображать первый компонент:

ghci> getPair $ fmap (*100) (Pair (2, 3))
(200,3)
ghci> getPair $ fmap reverse (Pair ("london calling", 3))
("gnillac nodnol",3)

О лености newtype

Единственное, что можно сделать с помощью newtype, – это превратить имеющийся тип в новый тип, поэтому внутренне Хаскель может представлять значения типов, определенных с помощью newtype, точно так же, как и первоначальные, зная в то же время, что их типы теперь различаются. Это означает, что newtype не только обычно быстрее, чем data, его механизм сопоставления с образцом ленивее. Давайте посмотрим, что это значит.

Как вы знаете, Хаскель по умолчанию ленив, что означает, что какие-либо вычисления будут иметь место только тогда, когда мы пытаемся фактически напечатать результаты выполнения наших функций. Более того, будут произведены только те вычисления, которые необходимы для того, чтобы наша функция вернула нам результаты. Значение undefined в Хаскеле представляет ошибочное вычисление. Если мы попытаемся его вычислить (т. е. заставить Хаскель на самом деле произвести вычисление), напечатав его на экране, Хаскель разразится детским приступом гнева (технически это называют исключением):

ghci> undefined
*** Exception: Prelude.undefined

Однако если мы создадим список, содержащий в себе несколько значений undefined, но запросим только голову списка, которая не равна undefined, все пройдет гладко. Это потому что Хаскелю не нужно вычислять какие-либо из остальных элементов в списке если мы хотим посмотреть только первый элемент. Вот пример:

ghci> head [3,4,5,undefined,2,undefined]
3

Теперь рассмотрите следующий тип:

data CoolBool = CoolBool { getCoolBool :: Bool }

Это ваш обыкновенный алгебраический тип данных, который был объявлен с использованием ключевого слова data. Он имеет один конструктор значения, который содержит одно поле, чей тип Bool. Давайте создадим функцию, которая сопоставляет с образцом значение CoolBool и возвращает значение "hello" вне зависимости от того, было ли значение Bool в CoolBool равно True или False:

helloMe :: CoolBool -> String
helloMe (CoolBool _) = "hello"

Вместо применения этой функции к обычному CoolBool, давайте сделаем ей обманный бросок, и применим ее к undefined!

ghci> helloMe undefined
"*** Exception: Prelude.undefined

Чёрт! Исключение! Почему возникло это исключение? Типы, определенные с помощью ключевого слова data, могут иметь много конструкторов значения (хотя CoolBool имеет только один конструктор). Поэтому для того чтобы понять, согласуется ли значение, переданное нашей функции, с образцом (CoolBool _), Хаскель должен вычислить значение ровно настолько, чтобы понять, какой конструктор значения был использован, когда мы создавали значение. И когда мы пытаемся вычислить значение undefined, будь оно даже небольшим, возникает исключение.

Вместо использования ключевого слова data для CoolBool, давайте попробуем использовать newtype:

newtype CoolBool = CoolBool { getCoolBool :: Bool }

Нам не нужно изменять нашу функцию helloMe, поскольку синтаксис сопоставления с образцом одинаков независимо от того, использовалось ли newtype или data для объявления вашего типа. Давайте сделаем здесь то же самое и применим helloMe к значению undefined:

ghci> helloMe undefined
"hello"

Сработало! Хммм, почему? Ну, как вы уже узнали, когда вы используете newtype, Хаскель внутренне может представлять значения нового типа таким же образом, как и первоначальные значения. Ему не нужно помещать их еще в одну коробку; он просто должен быть в курсе, что значения имеют разные типы. И поскольку Хаскель знает, что типы, созданные с помощью ключевого слова newtype, могут иметь лишь один конструктор, ему не нужно вычислять значение, переданное функции, чтобы быть убедиться, что значение соответствует образцу (CoolBool _), потому что типы, созданные с помощью newtype, могут иметь только один возможный конструктор значения и одно поле!
Это различие в поведении может казаться незначительным, но на самом деле оно очень важно. Оно показывает, что хотя типы, определенные с помощью data и newtype, ведут себя одинаково с точки зрения программиста (т. к. оба имеют конструкторы значения и поля), это фактически два различных механизма. Тогда как data может использовать для создания ваших новых типов с нуля, newtype предназначен просто для создания совершенно нового типа из существующего типа. Сравнение значений newtype с образцом не похоже на вынимание чего-то из коробки (что характерно для data), это скорее представляет собой прямое преобразование из одного типа в другой.

type против newtype против data

К этому моменту вы могли запутаться относительно разницы между type, data и newtype, поэтому давайте повторим пройденный материал об их использовании.

Ключевое слово type предназначено для создания синонимов типов. Мы просто даем другое имя уже существующему типу, чтобы на этот тип было проще сослаться. Скажем, мы сделали следующее:
type IntList = [Int]

Все, что оно делает, – это дает нам возможность сослаться на тип [Int] как IntList. Их можно использовать взаимозаменяемо. Мы не получаем конструктор значения IntList или что-либо в этом роде. Поскольку [Int] и IntList являются лишь двумя способами сослаться на один и тот же тип, не важно, какое имя мы используем в наших аннотациях типов:

ghci> ([1,2,3] :: IntList) ++ ([1,2,3] :: [Int])
[1,2,3,1,2,3]

Мы используем синонимы типов, когда хотим сделать наши сигнатуры типов более наглядными. Мы даем типам имена, которые говорят нам что-либо об их предназначении в контексте функций, где они используются. Например, когда мы использовали ассоциативный список типа [(String,String)] для представления телефонной книги в главе 7, мы дали ему синоним типа PhoneBook, чтобы сигнатуры типов наших функций были легко читаемыми.

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

newtype CharList = CharList { getCharList :: [Char] }

Мы не можем использовать ++, чтобы соединить вместе CharList и список типа [Char]. Мы даже не можем использовать ++, чтобы соединить два значения CharList, потому что ++ работает только со списками, а тип CharList не является списком, хотя можно сказать, что CharList содержит список. Мы можем, однако, преобразовать два значения CharList в списки, соединить их с помощью ++, а затем преобразовать получившееся обратно в CharList.

Когда в наших объявлениях newtype мы используем синтаксис записей, мы получаем функции для преобразования между новым типом и изначальным типом – а именно конструктор значения нашего newtype и функцию для извлечения значения из его поля. Новый тип также не делается автоматически экземпляром классов типов, к которым принадлежит исходный тип, поэтому нам необходимо породить (ключевое слово deriving), либо записать его вручную.

На деле, вы можете воспринимать объявления newtype как объявления data, которые могут иметь только один конструктор и одно поле. Если вы поймаете себя на написании такого объявления, рассмотрите использование newtype.

Ключевое слово data предназначено для создания ваших собственных типов данных. Вы можете войти с ними в раж. Они могут иметь столько конструкторов и полей, сколько вы пожелаете, и могут использоваться для реализации любого алгебраического типа данных – всего, начиная со списков и Maybe-подобных типов, заканчивая деревьями.

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

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

Об этих моноидах

Классы типов в Хаскеле используются для представления интерфейса к типам, которые обладают каким-то схожим поведением. Мы начали с простых классов типов вроде Eq, который предназначен для типов, чьи значения можно сравнить, и Ord – для сущностей, которые можно упорядочить. Затем мы перешли к более интересным классам типов, как Functor и Applicative.
Когда мы создаем тип, мы думаем о том, какие поведения он поддерживает (как он может действовать), а затем решаем, экземпляром каких классов типов его сделать, основываясь на необходимом нам поведении. Если разумно чтобы значения нашего типа были сравниваемыми, мы делаем наш тип экземпляром класса типов Eq. Если мы видим, что наш тип является чем-то вроде функтора, мы делаем его экземпляром Functor, и т. д.

Теперь рассмотрите следующее: * – это функция, которая принимает два числа и перемножает их. Если мы умножим какое-нибудь число на 1, результат всегда равен этому числу. Не важно, выполним ли мы 1 * x или x * 1 – результат всегда равен x. Подобным образом, ++ – это функция, которая принимает две сущности и возвращает третью. Но вместо того чтобы перемножать числа, она принимает два списка и конкатенирует их. И так же, как *, она тоже имеет определенное значение, которое не изменяет другое значение при использовании с ++. Этим значением является пустой список: [].

ghci> 4 * 1
4
ghci> 1 * 9
9
ghci> [1,2,3] ++ []
[1,2,3]
ghci> [] ++ [0.5, 2.5]
[0.5,2.5]

Похоже, что * вместе с 1 и ++ наряду с [] разделяют некоторые общие свойства:

  • Функция принимает два параметра.
  • Параметры и возвращаемое значение имеют одинаковый тип.
  • Существует такое значение, которое не изменяет другие значения, когда оно используется с бинарной функцией.
Есть еще одно общее между двумя этими операциями, что может быть не столь очевидным, как наши предыдущие наблюдения: когда у нас есть три и более значения, и нам необходимо использовать бинарную функцию для превращения их в один результат, порядок, в котором мы применяем бинарную функцию к значениям, не имеет значения. Например, выполним ли мы (3 * 4) * 5 или 3 * (4 * 5), результат равен 60. То же справедливо для ++:

ghci> (3 * 2) * (8 * 5)
240
ghci> 3 * (2 * (8 * 5))
240
ghci> "la" ++ ("di" ++ "da")
"ladida"
ghci> ("la" ++ "di") ++ "da"
"ladida"

Мы называем это свойство ассоциативностью. * ассоциативна, ++ тоже. Однако, -, например, неассоциативна; выражения (5 - 3) - 4 и 5 - (3 - 4) возвращают в результате разные числа.

Зная об этих свойствах, мы наткнулись на моноиды!

Класс типов Monoid

Моноид состоит из ассоциативной бинарной функции и значения, которое действует как тождество по отношению к этой функции. Когда что-то действует как тождество по отношению к функции, это означает, что при вызове с этой функцией и каким-то другим значением результат всегда равен этому другому значению. 1 является тождеством по отношению к *, а [] является тождеством по отношению к ++. В мире Хаскель есть множество других моноидов, поэтому существует класс типов Monoid. Он предназначен для типов, которые могут действовать как моноиды. Давайте посмотрим, как определен этот класс типов:

class Monoid m where
    mempty :: m
    mappend :: m -> m -> m
    mconcat :: [m] -> m
    mconcat = foldr mappend mempty

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

Прежде всего, нам видно, что экземплярами Monoid могут быть сделаны только конкретные типы, потому что m в определении класса типов не принимает никаких параметров типа. Это отличается от Functor и Applicative, которые требуют, чтобы их экземплярами были конструкторы типа, которые принимают один параметр.
Первой функцией является mempty. На самом деле это не функция, поскольку это не принимает параметров. Это полиморфная константа вроде minBound из Bounded. mempty представляет тождественное значение для конкретного моноида.

Далее, у нас есть mappend, которая, как вы уже, наверное, догадались, является бинарной функцией. Она принимает два значения одного типа и возвращает еще одно значение того же самого типа. Решение назвать функцию mappend так было отчасти неудачным, поскольку это подразумевает, что мы в некотором роде присоединяем два значения. Тогда как ++ действительно принимает два списка и присоединяет один в конец другого, * на самом деле не делает какого-либо присоединения, она просто перемножает два числа. Когда вы встретите другие экземпляры Monoid, вы поймете, что большинство из них тоже не присоединяют значения. Поэтому избегайте мыслить в терминах присоединения и просто думайте о mappend как о бинарной функции, которая принимает два моноидных значения и возвращает третье.

Последней функцией в определении этого класса типов является mconcat. Она принимает список моноидных значений и сокращает их до одного значения, применяя mappend между элементами списка. Она имеет реализацию по умолчанию, которая просто принимает mempty в качестве начального значения и сворачивает список справа с помощью mappend. Поскольку реализация по умолчанию хорошо подходит для большинства экземпляров, мы не будем сильно переживать по поводу mconcat. Когда какой-то тип делают экземпляром Monoid, достаточно реализовать всего лишь mempty и mappend. Хотя для некоторых экземпляров mconcat можно реализовать более эффективно, в большинстве случаев реализация по умолчанию подходит идеально.

Законы моноидов

Прежде чем перейти к более конкретным экземплярам Monoid, давайте кратко рассмотрим законы моноидов.

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

  • mempty `mappend` x = x
  • x `mappend` mempty = x
  • (x `mappend` y) `mappend` z = x `mappend` (y `mappend` z)
Первые два закона утверждают, что mempty должна вести себя как тождество по отношению к mappend, а третий – говорит, что mappend должна быть ассоциативна (порядок, в котором мы используем mappend для сокращения нескольких моноидных значений в одно, не имеет значения). Хаскель не приводит эти законы в исполнение, поэтому мы должны быть внимательными, чтобы наши экземпляры действительно подчинялись им.

Знакомьтесь с некоторыми моноидами

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

Списки являются моноидами

Да, списки являются моноидами! Как вы уже увидели, функция ++ и пустой список [] вместе образуют моноид. Экземпляр очень прост:

instance Monoid [a] where
    mempty = []
    mappend = (++)

Списки являются экземплярами класса типов Monoid независимо от типа элементов, которые они содержат. Обратите внимание, что мы написали instance Monoid [a], а не instance Monoid [], поскольку Monoid требует конкретный тип для экземпляра.

Тестируя это, мы не встречаем сюрпризов:

ghci> [1,2,3] `mappend` [4,5,6]
[1,2,3,4,5,6]
ghci> ("one" `mappend` "two") `mappend` "tree"
"onetwotree"
ghci> "one" `mappend` ("two" `mappend` "tree")
"onetwotree"
ghci> "one" `mappend` "two" `mappend` "tree"
"onetwotree"
ghci> "pang" `mappend` mempty
"pang"
ghci> mconcat [[1,2],[3,6],[9]]
[1,2,3,6,9]
ghci> mempty :: [a]
[]

Обратите внимание, что в последней строке мы написали явную аннотацию типа. Если бы мы написали просто mempty, GHCi не знал бы, какой экземпляр использовать, поэтому мы должны были сказать, что нам нужен списковый экземпляр. Мы могли использовать общий тип [a] (в отличие от указания [Int] или [String]), потому что пустой список может действовать так, будто он содержит любой тип.
Поскольку mconcat имеет реализацию по умолчанию, мы получаем ее просто так, когда делаем что-либо экземпляром Monoid. В случае со списокм mconcat соответствует просто concat. Она принимает список списков и разглаживает его, потому что это равнозначно вызову ++ между всеми смежными списками, содержащимися в списке.

Законы моноидов действительно выполняются для экземпляра списка. Когда у нас есть несколько списков и мы соединяем их вместе с помощью mappend (или ++), не имеет значения, какие списки мы соединяем первыми, поскольку так или иначе они соединяются на концах. Кроме того, пустой список действует как тождество, поэтому все хорошо.

Обратите внимание, что моноиды не требуют, чтобы a `mappend` b было равно b `mappend` a. В случае со списками они очевидно не равны:

ghci> "one" `mappend` "two"
"onetwo"
ghci> "two" `mappend` "one"
"twoone"

И это нормально. Тот факт, что при умножении выражения 3 * 5 и 5 * 3 дают один и тот же результат – это просто свойство умножения, но оно не выполняется для всех (в действительности, для большинства) моноидов.

Product и Sum

Мы уже изучили один из способов рассматривать числа как моноиды: просто позволить бинарной функции быть *, а тождественному значению – быть 1. Еще один способ для чисел быть моноидами состоит в том, чтобы бинарной функцией была +, а тождественным значением было 0:

ghci> 0 + 4
4
ghci> 5 + 0
5
ghci> (1 + 3) + 5
9
ghci> 1 + (3 + 5)
9

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

Имея два одинаково правомерных способа для чисел быть моноидами, какой способ нам выбрать? Ладно, мы не обязаны выбирать. Вспомните, что когда имеется несколько способов для какого-то типа быть экземпляром одного и того же класса типов, мы можем обернуть этот тип в newtype, а затем сделать новый тип экземпляром класса типов по-другому. Можно совместить несовместимое.

Модуль Data.Monoid экспортирует для этого два типа: Product и Sum.

Product определен вот так:

newtype Product a = Product { getProduct :: a }
    deriving (Eq, Ord, Read, Show, Bounded)

Это просто – всего лишь обертка newtype с одним параметром типа наряду с некоторыми порожденными экземплярами. Его экземпляр для Monoid выглядит примерно так:

instance Num a => Monoid (Product a) where
    mempty = Product 1
    Product x `mappend` Product y = Product (x * y)

mempty – это просто 1, обернутое в конструктор Product. mappend производит сопоставление конструктора Product с образцом, умножает два числа, а затем оборачивает результирующее число. Как вы можете видеть, имеется ограничение класса Num a. Это значит, что Product a является экземпляром Monoid для всех значений a, которые уже являются экземпляром Num. Для того чтобы использовать Product a в качестве моноида, мы должны произвести некоторое оборачивание и разворачивание newtype:

ghci> getProduct $ Product 3 `mappend` Product 9
27
ghci> getProduct $ Product 3 `mappend` mempty
3
ghci> getProduct $ Product 3 `mappend` Product 4 `mappend` Product 2
24
ghci> getProduct . mconcat . map Product $ [3,4,2]
24

Sum определен в том же духе, что и Product, и экземпляр тоже похож. Мы используем его точно так же:

ghci> getSum $ Sum 2 `mappend` Sum 9
11
ghci> getSum $ mempty `mappend` Sum 3
3
ghci> getSum . mconcat . map Sum $ [1,2,3]
6

Any и All

Еще одним типом, который может действовать как моноид двумя разными, но одинаково допустимыми способами, является Bool. Первый способ состоит в том, чтобы заставить функцию ||, которая представляет логическое ИЛИ, действовать как бинарную функцию наряду с False в качестве тождественного значения. При использовании логического ИЛИ, если какой-либо из параметров равен True, она возвращает True; в противном случае она возвращает False. Поэтому если мы используем False в качестве тождественного значения, ИЛИ вернет False при использовании с False и – True при использовании с True. Конструктор newtype Any является экземпляром Monoid подобным образом. Он определен вот так:

newtype Any = Any { getAny :: Bool }
    deriving (Eq, Ord, Read, Show, Bounded)

Его экземпляр выглядит вот так:
instance Monoid Any where
    mempty = Any False
    Any x `mappend` Any y = Any (x || y)

Он называется Any, потому что x `mappend` y будет равно True, если любое из этих двух значений равно True. Даже если три или более значений Bool, обернутых в Any, объединяются с помощью mappend вместе, результат будет содержать True, если любое из них равно True.

ghci> getAny $ Any True `mappend` Any False
True
ghci> getAny $ mempty `mappend` Any True
True
ghci> getAny . mconcat . map Any $ [False, False, False, True]
True
ghci> getAny $ mempty `mappend` mempty
False

Другой способ для Bool быть экземпляром Monoid состоит в том, чтобы сделать это как бы наоборот: заставить && быть бинарной функцией, а затем сделать True тождественным значением. Логическое И вернет True только если оба его параметра равны True.

Это объявление newtype:
newtype All = All { getAll :: Bool }
    deriving (Eq, Ord, Read, Show, Bounded)

А это экземпляр:

instance Monoid All where
    mempty = All True
    All x `mappend` All y = All (x && y)

Когда мы объединяем значения типа All с помощью mappend, результатом будет Ture только если все значения, использованные в операции mappend, равны True:

ghci> getAll $ mempty `mappend` All True
True
ghci> getAll $ mempty `mappend` All False
False
ghci> getAll . mconcat . map All $ [True, True, True]
True
ghci> getAll . mconcat . map All $ [True, True, False]
False

Так же, как при использовании умножения и сложения, мы обычно явно указываем бинарные функции вместо оборачивания их в значения newtype и последующего использования mappend и mempty. mconcat кажется полезной для Any и All, но обычно проще использовать функции or и and. or принимает списки значений Bool и возвращает True, если какое-либо из них равно True. and принимает те же значения и возвращает True, если все из них равны True.

Моноид Ordering

Помните тип Ordering? Он используется в качестве результата при сравнении сущностей и может иметь три значения: LT, EQ и GT, которые соответственно означают "меньше, чем", "равно" и "больше, чем".

ghci> 1 `compare` 2
LT
ghci> 2 `compare` 2
EQ
ghci> 3 `compare` 2
GT

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

instance Monoid Ordering where
    mempty = EQ
    LT `mappend` _ = LT
    EQ `mappend` y = y
    GT `mappend` _ = GT

Экземпляр определяется следующим образом: когда мы объединяем два значения Ordered с помощью mappend, сохраняется значение слева, если значение слева не равно EQ. Если значение слева равно EQ, результатом будет значение справа. Тождественным значением является EQ. На первый взгляд такой выбор может показаться несколько случайным, но он на самом деле имеет сходство с тем, как мы сравниваем слова в алфавитном порядке. Мы смотрим на первые две буквы и если они отличаются, мы уже можем решить, какое слово шло бы первым в словаре. Однако, если первые две буквы равны, тогда мы переходим к сравнению следующей пары букв, повторяя процесс.
Например, когда мы сравниваем слова ox и on по алфавиту, мы видим, что первые две буквы каждого слова равны, а затем продолжаем сравнивать вторые буквы. Поскольку x по алфавиту больше, чем n, мы знаем, как сравниваются эти слова. Чтобы лучше понять, как EQ является тождественным значением, обратите внимание, что если бы мы втиснули одну и ту же букву в одну и ту же позицию в обоих словах, это не изменило бы их алфавитный порядок; к примеру, oix по-прежнему больше в алфавитном порядке, чем oin.

Важно отметить, что в экземпляре класса типов Monoid для Ordering выражение x `mappend` y не равно выражению y `mappend` x. Поскольку первый параметр сохраняется, если он не равен EQ, LT `mappend` GT в результате вернет LT, тогда как GT `mappend` LT в результате вернет GT:

ghci> LT `mappend` GT
LT
ghci> GT `mappend` LT
GT
ghci> mempty `mappend` LT
LT
ghci> mempty `mappend` GT
GT

Хорошо, так чем же этот моноид полезен? Предположим, мы пишем функцию, которая принимает две строки, сравнивает их длину, и возвращает Ordering. Но если строки имеют одинаковую длину, тогда вместо того, чтобы сразу вернуть EQ, мы хотим сравнить их по алфавиту.

Вот один из способов записать это:

lengthCompare :: String -> String -> Ordering
lengthCompare x y = let a = length x `compare` length y
                        b = x `compare` y
                    in if a == EQ then b else a

Результат сравнения длин мы присваиваем a, а результат сравнения по алфавиту – b, а затем если оказывается, что длины равны, мы возвращаем их порядок по алфавиту.

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

import Data.Monoid

lengthCompare :: String -> String -> Ordering
lengthCompare x y = (length x `compare` length y) `mappend`
                    (x `compare` y)

Давайте опробуем это:

ghci> lengthCompare "zen" "ants"
LT
ghci> lengthCompare "zen" "ant"
GT

Вспомните, что когда мы используем mappend, сохраняется ее левый параметр, если он не равен EQ; если он равен EQ, сохраняется правый. Вот почему мы поместили сравнение, которое мы считаем первым, более важным критерием, в качестве первого параметра. Теперь предположим, что мы хотим расширить эту функцию, чтобы она также сравнивала количество гласных звуков, и установить это вторым по важности критерием для сравнения. Мы изменяем ее вот так:

import Data.Monoid

lengthCompare :: String -> String -> Ordering
lengthCompare x y = (length x `compare` length y) `mappend`
                    (vowels x `compare` vowels y) `mappend`
                    (x `compare` y)
    where vowels = length . filter (`elem` "aeiou")

Мы создали вспомогательную функцию, которая принимает строку и сообщает нам, сколько она содержит гласных звуков, сначала отфильтровывая в ней только буквы, находящиеся в строке "aeiou", а затем применяя к этому функцию length.

ghci> lengthCompare "zen" "anna"
LT
ghci> lengthCompare "zen" "ana"
LT
ghci> lengthCompare "zen" "ann"
GT

В первом примере длины оказались различными, и поэтому вернулось LT, так как длина "zen" меньше длины "anna". Во втором примере длины равны, но вторая строка содержит больше гласных звуков, поэтому опять возвращается LT. В третьем примере они обе имеют одинаковую длину и одинаковое количество гласных звуков, поэтому они сравниваются по алфавиту, и "zen" выигрывает.

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

Моноид Maybe

Давайте рассмотрим несколько способов, которыми Maybe a может быть сделан экземпляром Monoid, и как эти экземпляры полезны.

Один из способов состоит в том, чтобы обрабатывать Maybe a как моноид только если его параметр типа a тоже является моноидом, а потом реализовать mappend так, чтобы она использовала операцию mappend для значений, обернутых в Just. Мы используем Nothing как тождественное значение, и поэтому если одно из двух значений, которые мы объединяем с помощью mappend, равно Nothing, мы оставляем другое значение. Вот объявление экземпляра:

instance Monoid a => Monoid (Maybe a) where
    mempty = Nothing
    Nothing `mappend` m = m
    m `mappend` Nothing = m
    Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)

Обратите внимание на ограничение класса. Оно говорит, что Maybe является экземпляром Monoid только если a является экземпляром Monoid. Если мы объединяем что-то с Nothing, используя mappend, результатом является это что-то. Если мы объединяем два значения Just с помощью mappend, то содержимые значений Just объединяются с помощью mappend, а затем оборачиваются обратно в Just. Мы можем делать это, поскольку ограничение класса гарантирует, что тип значения, которое находится внутри Just, является экземпляром Monoid.

ghci> Nothing `mappend` Just "andy"
Just "andy"
ghci> Just LT `mappend` Nothing
Just LT
ghci> Just (Sum 3) `mappend` Just (Sum 4)
Just (Sum {getSum = 7})

Это полезно, когда мы имеем дело с моноидами как с результатами вычислений, которые могли окончиться неуспешно. Из-за наличия этого экземпляра нам не нужно проверять, окончились ли вычисления неуспешно, определяя, вернули они значение Nothing или Just; мы можем просто продолжить обрабатывать их как обычные моноиды.

Но что если тип содержимого Maybe не является экземпляром Monoid? Обратите внимание, что в предыдущем объявлении экземпляра единственным случаем, где мы должны полагаться на то, что содержимые являются моноидами, – это когда оба параметра mappend являются значениями Just. Когда мы не знаем, являются ли содержимые моноидами, мы не можем использовать mappend между ними, так что же нам делать? Ну, единственное, что мы можем сделать, – это отвергнуть второе значение и оставить первое. Для этой цели существует тип First a. Вот его определение:

newtype First a = First { getFirst :: Maybe a }
    deriving (Eq, Ord, Read, Show)

Мы берем Maybe a и оборачиваем его с помощью newtype. Экземпляр Monoid выглядит следующим образом:

instance Monoid (First a) where
    mempty = First Nothing
    First (Just x) `mappend` _ = First (Just x)
    First Nothing `mappend` x = x

mempty – это просто Nothing, обернутое с помощью конструктора newtype First. Если первый параметр mappend является значением Just, мы игнорируем второй. Если первый параметр – Nothing, тогда мы возвращаем второй параметр в качестве результата независимо от того, является ли он Just или Nothing:

ghci> getFirst $ First (Just 'a') `mappend` First (Just 'b')
Just 'a'
ghci> getFirst $ First Nothing `mappend` First (Just 'b')
Just 'b'
ghci> getFirst $ First (Just 'a') `mappend` First Nothing
Just 'a'

First полезен, когда у нас есть множество значений Maybe, и мы хотим знать, является ли какое-либо из них значением Just. Для этого годится функция mconcat:

ghci> getFirst . mconcat . map First $ [Nothing, Just 9, Just 10]
Just 9

Если нам нужен моноид на значениях Maybe a такой, чтобы оставался второй параметр, когда оба параметра mappend являются значениями Just, Data.Monoid предоставляет тип Last a, который работает, как First a, но при объединении с помощью mappend и использовании mconcat сохраняется последнее не-Nothing значение:

ghci> getLast . mconcat . map Last $ [Nothing, Just 9, Just 10]
Just 10
ghci> getLast $ Last (Just "one") `mappend` Last (Just "two")
Just "two"

Свертывание с помощью моноидов

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

Поскольку существует так много структур данных, которые хорошо работают со свертками, был введен класс типов Foldable. Так же, как Functor предназначен для сущностей, которые можно отображать, Foldable предназначен для вещей, которые могут быть сворачивать! Он может быть найден в Data.Foldable, и поскольку он экспортирует функции, чьи имена конфликтуют с именами функций из Prelude, его лучше импортировать квалифицируя (и подавая с базиликом):

import qualified Data.Foldable as F

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

Так какие из некоторых функций определяет этот класс типов? Ладно, среди них есть foldr, foldl, foldr1 и foldl1. Чего? Мы уже знакомы с этими функциями. Что в этом нового? Давайте сравним типы foldr из Foldable и foldr из Prelude, чтобы узнать, чем они отличаются:

ghci> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
ghci> :t F.foldr
F.foldr :: (F.Foldable t) => (a -> b -> b) -> b -> t a -> b

Аа! Значит, тогда как foldr принимает список и сворачивает его, foldr из Data.Foldable принимает любой тип, который можно свернуть, не только списки! Как и ожидалось, обе функции foldr делают со списками одно и то же:

ghci> foldr (*) 1 [1,2,3]
6
ghci> F.foldr (*) 1 [1,2,3]
6

Другой структурой данных, поддерживающей свертку, является Maybe, которую мы все знаем и любим!

ghci> F.foldl (+) 2 (Just 9)
11
ghci> F.foldr (||) False (Just True)
True

Но сворачивание значения Maybe не очень уж интересно. Оно действует просто как список с одним элементом, если это значение Just, и – как пустой список, если это значение Nothing. Давайте рассмотрим чуть более сложную структуру данных.

Помните древовидную структуру данных из главы 7? Мы определили ее вот так:

Вы узнали, что дерево – это либо пустое дерево, которое не содержит никаких значений, либо это узел, который содержит одно значение, а также два других дерева. После того, как мы его определили, мы сделали его экземпляром Functor, и это дало нам возможность отображать его с помощью функций, используя fmap. Теперь мы сделаем его экземпляром Foldable, чтобы у нас появилась возможность производить его свертку.

Один из способов сделать конструктор типа экземпляром Foldable состоит в том, чтобы просто напрямую реализовать для него foldr. Но другой, часто более простой способ, состоит в том, чтобы реализовать функцию foldMap, которая также является частью класса типов Foldable. Функция foldMap имеет следующий тип:

foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m

Ее первым параметром является функция, принимающая значение того типа, который содержит наша сворачиваемая структура (обозначен здесь как a), и возвращающая моноидное значение. Ее вторым параметром является сворачиваемая структура, которая содержит значения типа a. Эта функция отображает структуру с помощью данной функции, таким образом производя сворачиваемую структуру, которая содержит моноидные значения. Затем, объединяя эти моноидные значения с помощью mappend, она соединяет их все в одно моноидное значение. Эта функция на данный момент может показаться несколько странной, но вы увидите, что ее очень просто реализовать. И реализация этой функции – это все, что требуется, чтобы сделать наш тип экземпляром Foldable! Поэтому если мы просто реализуем foldMap для какого-либо типа, мы получаем foldr и foldl для этого типа даром!

Вот как мы делаем Tree экземпляром Foldable:

instance F.Foldable Tree where
    foldMap f EmptyTree = mempty
    foldMap f (Node x l r) = F.foldMap f l `mappend`
                             f x `mappend`
                             F.foldMap f r
Если нам предоставлена функция, которая принимает элемент нашего дерева и возвращает моноидное значение, как нам превратить наше целое дерево в одно моноидное значение? Когда мы использовали fmap с нашим деревом, мы применяли функцию, отображая с ее помощью узел, а затем рекурсивно отображали с помощью этой функции левое поддерево, а также правое поддерево. Здесь наша задача состоит не только в отображении с помощью функции, но также и в соединении значений в одно моноидное значение, используя mappend. Сначала мы рассматриваем случай с пустым деревом – печальным и одиноким деревцем, у которого нет никаких значений или поддеревьев. Оно не содержит никаких значений, которые мы можем предоставить нашей функции, создающей моноид, поэтому мы просто говорим, что если наше дерево пусто, то моноидное значение, в которое оно будет превращено, равно mempty.

Случай с непустым узлом чуть более интересен. Он содержит два поддерева, а также значение. В этом случае мы рекурсивно отображаем левое и правое поддеревья с помощью одной и той же функции f, используя foldMap. Вспомните, что наша foldMap возвращает в результате одно моноидное значение. Мы также применяем нашу функцию f к значению в узле. Теперь у нас есть три моноидных значения (два – из наших поддеревьев, и одно – после применения f к значению в узле), и нам просто нужно соединить их вместе в одно значение. Для этой цели мы используем mappend, и естественным образом левое поддерево идет первым, затем – значение узла, а потом – правое поддерево. Обратите внимание, что нам не нужно было предоставлять функцию, которая принимает значение и возвращает моноидное значение. Мы принимаем эту функцию как параметр к foldMap, и все, что нам нужно решить, – это где применить эту функцию и как соединить результирующие моноиды, которые она возвращает.

Теперь, когда у нас есть экземпляр Foldable для нашего типа, представляющего дерево, мы получаем foldr и foldl даром! Рассмотрите вот это дерево:

testTree = Node 5
            (Node 3
                (Node 1 EmptyTree EmptyTree)
                (Node 6 EmptyTree EmptyTree)
            )
     (Node 9
         (Node 8 EmptyTree EmptyTree)
         (Node 10 EmptyTree EmptyTree)
     )

У него 5 в качестве его корня, а его левый узел содержит 3 с 1 слева и 6 справа. Правый узел корня содержит 9, а затем 8 слева от него и 10 в самой дальней части справа. Используя экземпляр Foldable, мы можем производить все те же свертки, что мы можем производить над списками:

ghci> F.foldl (+) 0 testTree
42
ghci> F.foldl (*) 1 testTree
64800

foldMap полезна не только для создания новых экземпляров Foldable. Она также очень удобна для превращения нашей структуры в одно моноидное значение. Например, если мы хотим узнать, равно ли какое-либо из чисел нашего дерева 3, мы можем сделать следующее:

ghci> getAny $ F.foldMap (\x -> Any $ x == 3) testTree
True

Здесь \x -> Any $ x == 3 – это функция, которая принимает число и возвращает моноидное значение: значение Bool, обернутое в Any. foldMap применяет эту функцию к каждому элементу нашего дерева, а затем превращает получившиеся моноиды в один моноид с помощью mappend. Предположим, мы выполняем следующее:

ghci> getAny $ F.foldMap (\x -> Any $ x > 15) testTree
False

Все узлы нашего дерева будут содержать значение Any False после того, как к ним будет применена лямбда-функция. Но чтобы получить в итоге True, реализация mappend для Any должна принять по крайней мере одно значение True в качестве параметра. Поэтому окончательным результатом будет False, что логично, поскольку все значения в нашем дереве не превышают 15.

Мы также можем легко превратить наше дерево в список, просто используя foldMap с лямбда-функцией \x -> [x]. Проецируя сначала эту функцию на наше дерево, каждый элемент становится одноэелементным списком. Действие mappend, которое имеет место между всеми этими одноэлементными списками, возвращает в результате один список, содержащий все элементы нашего дерева:

ghci> F.foldMap (\x -> [x]) testTree
[1,3,6,5,8,9,10]

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

3 комментария:

  1. Ясир, а может стоить добавить метку fprog к этому постингу?

    Мне интересно - кто будет издавать перевод? Нужна ли помощь с версткой/вычиткой?

    ОтветитьУдалить
  2. Alex, в предыдущих постах я добавлял метку fprog, и когда я правил опубликованные посты, агрегатор fprog.ru воспринимал изменения как новые сообщения и помещал их в самом верху http://fprog.ru/planet, поэтому здесь я не добавлял метку.

    Если имеет смысл, я добавлю метку fprog, просто материалы и так агрегируются с Хабра (в данном случае по тэгу [haskell], я подозреваю), и я их вижу на fprog.ru

    Второй вопрос обсудим в личке.

    ОтветитьУдалить
  3. Возможно, для верстки самым простым будет перевести все на гитхаб. Структура Markdown отлично подходит.

    ОтветитьУдалить