Yasir Arsanukaev :: programming blog

2011-09-17T00:20:00.000+10:00

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

Вводное инфо на Хабре: 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!

Code-golf: Поиск в ширину и – в глубину с помощью Haskell

2011-02-07T15:47:00.009+11:00

Написал короткий код на Haskell для поиска в ширину и поиска в глубину.

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


data Node a = Node {value::a, children::[Node a]}

Сами тексты соответственно выглядят:


bfs :: Node a -> [a]
bfs (Node a b) = bfs' [a] b
  where bfs' res [] = res
        bfs' res n = bfs' (res ++ (map value n)) $ concatMap children n

dfs :: Node a -> [a]
dfs node = dfs' [node] []
  where dfs' [] result = result
        dfs' (x:xs) result = dfs' (children x ++ xs) (result ++ [value x])

Ну, и в сжатом виде:


data N a=N{v::a,c::[N a]}

b(N a b)=d[a]b
d r[]=r
d r n=d(r++(map v n))$concatMap c n

d n=f[n][]
f(x:y)=f(c x++y).(++[v x])
f _=id

Где функция b – поиск в ширину, а функция d – в глубину.

Поиск в глубину пытался сократить по-разному, в т. ч., как видно, с помощью композиции функций (HaskellWiki – Point-free Style). Хотя, если развернуть композицию, вернув назад аргумент, объем кода будет идентичным:


d n=f[n][]
f(x:y)r=f(c x++y)$r++[v x]
f[]r=r

Если у кого-то есть идеи по дальнейшему возможному сокращению кода, либо вы хотите попробовать реализовать сжатые алгоритмы на вашем любимом языке, прошу предлагать свои варианты на новом сайте для любителей программирования и программных головоломок Code Golf – Stack Exchange:

Tree traversal: Breadth-first search

Tree traversal: Depth-first search

Have fun()! ;-)

scheme-bert – библиотека сериализации BERT для R6RS Scheme

2010-10-21T00:03:00.004+11:00

Выпущена библиотека сериализации/десериализации BERT для реализаций языка программирования Scheme, соответствующих стандарту R6RS.

С ее помощью вы можете сериализовать и десериализовать следующие типы данных:

flonum?
integer?
symbol?
list?
string?
vector?
boolean?
hashtable?
time?

а также 'nil (в различных реализациях Scheme представлен по-разному, например, пустым списком '()) в двоичный формат BERT (Binary ERlang Term), разработанный Томом Престон-Вернером изначально для сервиса GitHub, одним из создателей которого он является.

Небольшой пример кода:


> (define (bytes)
   (bert-encode (list 'foo 13 42 (vector 666 '() 'bar))))
> (bytes)
#"\203l\0\0\0\4d\0\3fooa\ra*h\3b\0\0\2\232jd\0\3barj"
> (bert-decode (bytes))
{foo 13 42 #(666 () bar)}
>

Как видно, сериализации подвергались данные, которым в Erlang аналогичен следующий терм:


[foo, 13, 42, {666, [], bar}].

Работа кода протестирована на Racket 5.0 и Chez Scheme 8.0. Другие реализации Scheme, поддерживающие стандарт R6RS, не проверялись, однако работоспособность в основном зависит только от степени соответствия стандарту (Ikarus Scheme весьма близок к нему).

Поддержка регулярных выражений (пока) не реализована, поскольку мне не удалось найти такой библиотеки для работы с ними, которая была бы максимально портируемой, а также поддерживала возможность получения исходной строки скомпилированного регулярного выражения и опций, при которых оно было скомпилировано. Возможно, что-то сдвинется в этом отношении для Irregex, еще одной библиотеки регулярных выражений для Scheme, которая была бы неплохим вариантом для интеграции в сериализатор.

Спецификация BERT расположена тут – http://bert-rpc.org/
Библиотека сериализации размещена здесь – http://bitbucket.org/yasir/scheme-bert

Ваши патчи и отзывы приветствуются. Как форкнуть проект, выслать патч, сделать pull request, и прочие вещи, читайте в разделе помощи Bitbucket.

Regards, Yasir Arsanukaev.

UPD. Ура, проект теперь входит в экосистему BERT, он добавлен в список на сайте BERT!

Haskell и параллелизм: Триангуляция сферы параллельным рекуррентным разбиением тетраэдра с применением плоского затенения

2010-04-15T00:38:00.028+10:00

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

Введение

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

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

Вершины тетраэдра

Для определения координат вершин тетраэдра можно воспользоваться данными выкладками. Предположим, что после соответствующих вычислений мы имеем следующие координаты четырех вершин тетраэдра:
(0.0, 0.0, 1.0),
(0.0, 0.942809, -0.333333),
(-0.816497, -0.471405, -0.333333),
(0.816497, -0.471405, -0.333333)

Каркас приложения

Для визуализации используем OpenGL; Haskell имеет к ней соответствующую привязку. Теперь начнем создавать каркас приложения на Haskell с ее помощью:


main = do
     (progname, _) <- getArgsAndInitialize     
     initialDisplayMode $= [DoubleBuffered, WithDepthBuffer]
     initialWindowSize $= (Size 640 640)
     createWindow "Sphere approximation"     
     myInit
     displayCallback $= display
     reshapeCallback $= Just reshape
     mainLoop

myInit = do     
     ortho (-2.0) 2.0 (-2.0) 2.0 (-10.0) 10.0     
     depthFunc $= Just Less

display = do     
     clear [ColorBuffer, DepthBuffer]
     -- put your drawing code here
     swapBuffers 

reshape s@(Size w h) = do
     viewport $= (Position 0 0, s)
     postRedisplay NothingNothing

В этом наброске в функции main производится инициализация приложения, установка глобальных переменных состояния, и создается окно. В myInit устанавливается матрица ортогональности. В initialDisplayMode мы помещаем настройки, в данном случае мы указали, что хотим использовать двойную буферизацию, а также включить буфер глубины (Z-buffer); если этого не сделать, то едва ли изображение будет выглядеть так, как мы этого ожидаем. Пока ничего отображаться в окне не должно. В функции display перед началом рисования нужно очистить буферы цвета и глубины с помощью вызова clear, а после этого, поскольку мы использовали двойную буферизацию, переключить буфер с помощью swapBuffers.

Отображение тетраэдра

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


type Gf3 = (GLfloat, GLfloat, GLfloat)

figCoords :: [Gf3]
figCoords = [    (0.0, 0.0, 1.0),
                 (0.0, 0.942809, -0.333333),
                 (-0.816497, -0.471405, -0.333333),
                 (0.816497, -0.471405, -0.333333)
            ]

tetrahedron coords = do
     triangle (coords !! 0) (coords !! 1) (coords !! 2)
     triangle (coords !! 3) (coords !! 2) (coords !! 1)
     triangle (coords !! 0) (coords !! 3) (coords !! 1)
     triangle (coords !! 0) (coords !! 2) (coords !! 3)

triangle (x1, y1, z1) (x2, y2, z2) (x3, y3, z3) = do
     renderPrimitive Triangles $ do
          vertex $ Vertex3 x1 y1 z1
          vertex $ Vertex3 x2 y2 z2
          vertex $ Vertex3 x3 y3 z3

а функцию display приведем к следующему виду:


display = do
     clear [ColorBuffer, DepthBuffer]
     tetrahedron figCoords
     swapBuffers

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

Разбиение тетраэдра

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


          /\                  /\
         /  \                /  \
        /    \              /----\
       /      \            / \  / \
      /________\          /___\/___\

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


divideTriangle :: Gf3 -> Gf3 -> Gf3 -> Int -> IO ()
divideTriangle p1 p2 p3 0 = triangle p1 p2 p3
divideTriangle a@(x1, y1, z1) b@(x2, y2, z2) c@(x3, y3, z3) ndivisions = do
     divideTriangle a  v1  v2  (ndivisions - 1)
     divideTriangle c  v2  v3  (ndivisions - 1)
     divideTriangle b  v3  v1  (ndivisions - 1)
     divideTriangle v1 v3  v2  (ndivisions - 1)
     where v1 = normalizeCoords ((x1 + x2)/2, (y1 + y2)/2, (z1 + z2)/2)
           v2 = normalizeCoords ((x1 + x3)/2, (y1 + y3)/2, (z1 + z3)/2)
           v3 = normalizeCoords ((x2 + x3)/2, (y2 + y3)/2, (z2 + z3)/2)

normalizeCoords :: Gf3 -> Gf3
normalizeCoords c@(x, y, z)
     | len > 0   = (x/len, y/len, z/len)
     | otherwise = c
     where len   = sqrt (x*x + y*y + z*z)

а также модифицируем функции tetrahedron, display и main для учета количества рекуррентных разбиений следующим образом:


tetrahedron coords ndivisions = do
     divideTriangle (coords !! 0) (coords !! 1) (coords !! 2) ndivisions
     divideTriangle (coords !! 3) (coords !! 2) (coords !! 1) ndivisions
     divideTriangle (coords !! 0) (coords !! 3) (coords !! 1) ndivisions
     divideTriangle (coords !! 0) (coords !! 2) (coords !! 3) ndivisions

display nDivisions = do
     clear [ColorBuffer, DepthBuffer]
     tetrahedron figCoords nDivisions
     swapBuffers

main = do
     (progname, _) <- getArgsAndInitialize
     initialDisplayMode $= [DoubleBuffered, WithDepthBuffer]
     initialWindowSize $= (Size 640 640)
     createWindow "Sphere approximation"
     myInit
     let nDivisions = 3
     displayCallback $= (display nDivisions)
     reshapeCallback $= Just reshape
     mainLoop

После компиляции и запуска такой программы изображается что-то наподобие этого:

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

Затенение

Существует множество способов затенения. Одним из самых первых и распространенных был метод плоского затенения, где освещенность производится для полигона (треугольника) целиком. Этот метод хорошо подходит для затенения каких-либо объектов с прямыми гранями, но не совсем хорошо — для неровных поверхностей, поскольку при таком затенении на неровном объекте отчетливо становятся видны грани (Mach bands, статья "Как компьютер рисует изображения"). Тем не менее, нам не важна в данном случае фотореалистичность. Поэтому применим плоское затенение.

Для определения степени освещенности точки — в нашем случае освещается треугольник — нужно определить косинус угла между нормалью, идущей из этой точки, и вектором идущим из этой точки к точечному источнику света (статья в журнале Xakep "Освещение в играх")

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


crossProd :: (Num a) => (a, a, a) -> (a, a, a) -> (a, a, a) -> (a, a, a)
crossProd (x1, y1, z1) (x2, y2, z2) (x3, y3, z3) = (x, y, z)
     where x = (y2 - y1) * (z3 - z1) - (z2 - z1) * (y3 - y1)
           y = (z2 - z1) * (x3 - x1) - (x2 - x1) * (z3 - z1)
           z = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)

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


dotProd :: (Num a) => (a, a, a) -> (a, a, a) -> a
dotProd (x1, y1, z1) (x2, y2, z2) = x1*x2 + y1*y2 + z1*z2

Функцию triangle изменим следующим образом:


triangle :: Gf3 -> Gf3 -> Gf3 -> IO ()
triangle a@(x1, y1, z1) b@(x2, y2, z2) c@(x3, y3, z3) = do
     -- Detrmine a triangle normal
     -- (it's just a direction, not a vector)
     -- Normalized normals are happy normals ;)
     let normal     = normalizeCoords $ crossProd a b c
     let lightPos   = (1.0, 1.0, 1.0::GLfloat)
     let intensity  = 1.0 * dotProd normal lightPos

     renderPrimitive Triangles $ do
          color $ Color3 intensity intensity intensity
          vertex $ Vertex3 x1 y1 z1
          vertex $ Vertex3 x2 y2 z2
          vertex $ Vertex3 x3 y3 z3

Здесь координаты источника света (1.0, 1.0, 1.0), коэффициент отражающей способности установлен в 1.0, интенсивность отражения изменяется для всех цветовых каналов одинаково. Теперь, если вы запустите программу, то можно будет увидеть следующее изображение (48 треугольников):

По-моему, оно походит чем-то на подсвеченную сферу. А если увеличить число разбиений до 8-1, то получится очень реалистичная сфера (49 152 треугольника):

Полный код приложения на данном этапе.

Параллелизм

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

Для Haskell имеются разнообразные библиотеки, позволяющие сделать приложение многопоточным. Мы воспользуемся вызовом forkIO, и синхронизирующей переменной MVar, которые достаточно давно доступны в Glasgow Haskell Compiler. Импортируем их, добавив следующие строки в начало исходного кода:


import Control.Concurrent
import Control.Concurrent.MVar
import Control.Monad

К текущему моменту в нашей программе можно распараллелить вызовы функции divideTriangle, осуществляемые в функции tetrahedron:


tetrahedron :: [Gf3] -> Int -> IO ()
tetrahedron coords ndivisions = do
     child0 <- thread (coords !! 0) (coords !! 1) (coords !! 2) ndivisions
     child1 <- thread (coords !! 3) (coords !! 2) (coords !! 1) ndivisions
     child2 <- thread (coords !! 0) (coords !! 3) (coords !! 1) ndivisions
     child3 <- thread (coords !! 0) (coords !! 2) (coords !! 3) ndivisions
     ret <- mapM takeMVar [child0, child1, child2, child3]
     return ()

thread :: Gf3 -> Gf3 -> Gf3 -> Int -> IO (MVar (IO ()))
thread p1 p2 p3 ndivisions = do
     mvar <- newEmptyMVar
     forkIO $ do 
          let r = divideTriangle p1 p2 p3 ndivisions
          putMVar mvar r
     return mvar

Здесь создаются 4 нити, работающие параллельно. В функции thread перед созданием нити инициализируется синхронизирующая переменная с помощью вызова newEmptyMVar. Потом создается сама нить, которая осуществляет вызов divideTriangle и помещает в MVar результат, который был возвращен функцией divideTriangle.

Само по себе содержимое MVar нас не интересуит, оно лишь служит сигналом нити, выполняющей вызов функции takeMVar, к тому, что можно продолжать дальнейшие вычисления, т. е. функция takeMVar не вернет управление, пока в MVar не будет помещено какое-либо значение. Таким образом, в списке ret будут находиться значения, которые нити поместили с помощью вызова putMVar, и программа не продолжит работу, пока все нити не поместят эти значения. Вызов return () позволяет вернуть значение, которое соответствует типу функции tetrahedron :: [Gf3] -> Int -> IO (), т. е. пустой кортеж.

Но если вы скомпилируете и запустите эту программу, то прежней сферы вы не увидите! Предлагаю вам подумать, почему так происходит (вспомните свойства языка Haskell). Полный код программы на данном этапе.

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

Заключение

В статье была рассмотрена техника распараллеливания вычислений на языке Haskell, продемонстрировано использование привязки к OpenGL. Как говорит эта статья, Haskell производит паралельные вычисления очень быстро.

Надеюсь, вам понравилось.

Литература

Эйнджел, Эдвард. Интерактивная компьютерная графика. Вводный курс на базе OpenGL, 2 изд.: Пер. с англ. — М.: Издательский дом "Вильямс", 2001. — 592 с.: ил. — Парал. тит. англ. ISBN 5-8459-0209-6 (рус.)

P. S. Возможно, кто-то посоветует способ сокрытия под кат текста так, чтобы это действительно работало в т. ч. и на Russian Lambda Planet.

Распределенные математические вычисления на языке Erlang

2010-03-27T23:11:00.010+11:00

В статье иллюстрируется пример настройки окружения и серверов для возможности проведения распределенных вычислений на языке Erlang, а также их осуществление. В качестве примера предлагается перемножение матрицы на вектор с использованием пула pool(3) серверов Erlang. В данном случае пул состоит из 3 машин под управлением ОС FreeBSD.

Введение
Многие из вас, наверняка, уже использовали вызов spawn[_link] в своих приложениях, но немногие, как я заметил, знают о более лаконичном -- но также и более функциональном -- его аналоге pspawn[_link]. Попробуем заполнить этот пробел, решив простую математическую задачу.

Подготовка
Настройки серверов для хоста с двумя тюрьмами, расположенными на нем:

[root@conductor ~/crunching]# uname -prs
FreeBSD 7.1-RELEASE i386
[root@conductor ~/crunching]# grep '\.loc' /etc/hosts
192.168.32.40
192.168.32.201
192.168.32.202
[root@conductor ~/crunching]# jls
JID  IP Address      Hostname
 1  192.168.32.201  j1.loc
 2  192.168.32.202  j2.loc
[root@conductor ~/crunching]# ifconfig em0 | grep inet
inet 192.168.32.40 netmask 0xffffff00 broadcast 192.168.32.255
inet 192.168.32.201 netmask 0xffffff00 broadcast 192.168.32.201
inet 192.168.32.202 netmask 0xffffff00 broadcast 192.168.32.202
[root@conductor ~/crunching]# cat ~/.hosts.erlang
'j1.loc'
'j2.loc'
[root@conductor ~/crunching]# pkg_info -E erlang*
[root@conductor ~/crunching]#

Запуск мастер-ноды poolmaster@conductor Erlang на хосте, затем запуск пула ведомых нод (slaves) в тюрьмах. Возвращение списка адресов машин, составляющих пул:

[root@conductor ~/crunching]# erl -sname poolmaster -rsh ssh
Erlang R13B01 (erts-5.7.2) [source] [rq:1] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.7.2  (abort with ^G)
(poolmaster@conductor)1> c(pwnd).
{ok,pwnd}
(poolmaster@conductor)2> pool:start(crunchpool).
[crunchpool@j1,crunchpool@j2]
(poolmaster@conductor)3> pool:get_nodes().
[poolmaster@conductor,crunchpool@j1,crunchpool@j2]
(poolmaster@conductor)4>

Удаленное подключение к shell Erlang-ноды, находящейся на другой машине (в данном случае -- в тюрьме), и исполнение произвольного кода:

[root@conductor ~/crunching]# erl -sname client -remsh crunchpool@j1
Erlang R13B01 (erts-5.7.2) [source] [rq:1] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.7.2  (abort with ^G)
(crunchpool@j1)1> os:cmd("hostname").
"j1.loc\n"
(crunchpool@j1)2>

На всех узлах пула (в т. ч. на ведущем (master)) запускаются Erlang Port Mapper Daemon (epmd(1)) и beam(1):


[root@conductor ~] jexec 1 sockstat -4
USER    COMMAND   PID   FD    PROTO    LOCAL ADDRESS         FOREIGN ADDRESS
root    beam      2863  7     tcp4     192.168.32.201:63037  *:*
root    beam      2863  8     tcp4     192.168.32.201:50707  192.168.32.201:4369
root    beam      2863  10    tcp4     192.168.32.201:54136  192.168.32.40:61473
root    beam      2863  13    tcp4     192.168.32.201:63037  192.168.32.202:61991
root    epmd      1143  3     tcp4     192.168.32.201:4369   *:*
root    epmd      1143  4     tcp4     192.168.32.201:4369   192.168.32.201:50707
root    inetd     861   5     tcp4     192.168.32.201:22     *:*
root    sendmail  837   5     tcp4     192.168.32.201:25     *:*
root    syslogd   777   6     udp4     192.168.32.201:514    *:*
[root@conductor ~] jexec 2 sockstat -4
USER    COMMAND   PID   FD    PROTO    LOCAL ADDRESS         FOREIGN ADDRESS
root    beam      2880  7     tcp4     192.168.32.202:64315  *:*
root    beam      2880  8     tcp4     192.168.32.202:57386  192.168.32.202:4369
root    beam      2880  10    tcp4     192.168.32.202:50430  192.168.32.40:61473
root    beam      2880  11    tcp4     192.168.32.202:61991  192.168.32.201:63037
root    epmd      1160  3     tcp4     192.168.32.202:4369   *:*
root    epmd      1160  4     tcp4     192.168.32.202:4369   192.168.32.202:57386
root    inetd     1024  5     tcp4     192.168.32.202:22     *:*
root    sendmail  1002  4     tcp4     192.168.32.202:25     *:*
root    syslogd   942   6     udp4     192.168.32.202:514    *:*

Запуск процесса распределенного вычисления, оканчивающегося выдачей результатов. Получение списка присоединенных нод, остановка пула, выход из Erlang shell:

(poolmaster@conductor)13> pwnd:vStart[[1,4,-2,1]], [9,1,11,1], [3,-3,5,1], [1,1,1,1]], [1,5,1,-3]).
ResL = [{module,pwnd},{module,pwnd},{module,pwnd}]
PIDS = [<0.141.0>,<8877.51.0>,<8838.51.0>,<0.142.0>]
poolmaster@conductor: [<0.141.0>/1] V1=[1,4,-2,1] * V2=[1,5,1,-3] == [16,0,0,0]
poolmaster@conductor: [<0.142.0>/4] V1=[1,1,1,1] * V2=[1,5,1,-3] == [0,0,0,4]
crunchpool@j1: [<8838.51.0>/3] V1=[3,-3,5,1] * V2=[1,5,1,-3] == [0,0,-10,0]
crunchpool@j2: [<8877.51.0>/2] V1=[9,1,11,1] * V2=[1,5,1,-3] == [0,22,0,0]
[16,22,-10,4]
(poolmaster@conductor)14> nodes().
[crunchpool@j1,crunchpool@j2]
(poolmaster@conductor)15> pool:stop().
stopped
(poolmaster@conductor)16> nodes().
[]
(poolmaster@conductor)17> q().
ok
(poolmaster@conductor)18>
[root@conductor ~/crunching]#

В примере выше задан ключ -rsh ssh, сообщающий Erlang VM, что доступ к другим нодам должен осуществляться по протоколу SSH. В этой демонстрации доступ к узлам производится по SSH с применением аутентификации через публичный ключ. Можно также использовать другие методы аутентификации, например, Kerberos. Мастер-нода автоматически запускает Erlang VM удаленно на каждом из ведомых узлов пула. Т. о. налицо простота ввода новых мощностей в кластер. В идеале можно было бы свести к минимуму объем работы по конфигурированию окружения (ОС, VM etc.) и построить кластер на основе diskless узлов, загружающихся через LAN Boot, тем самым повысив надежность.

Исходя из последнего вывода на stdout смею предположить, что запуск (pspawn) процессов в пуле в отсутствие нагрузки происходит на разных серверах циклически (in a round-robin fashion), в противном случае учитывается загруженность каждого индивидуального вычислительного узла и производится балансировка нагрузки, т. е. запуск каждого нового процесса (именно Erlang процесса в Erlang VM, а не процесса ОС, aka "green process") на одном из наименее загруженных узлов пула.

Исходный код

-module(pwnd).

-export([startSay/0, say/2]).
-export([vSum/2, vMul/2, vVec/3, vStart/2, vSpawn/1,
       vReduce/2, vScatter/5, vWorker/1]).

-import(lists).

vSum([], []) ->
   [];
vSum([H1 | T1], [H2 | T2]) ->
   [H1 + H2] ++ vSum(T1, T2).

vMul([], []) ->
   [];
vMul([H1 | T1], [H2 | T2]) ->
   [H1 * H2] ++ vMul(T1, T2).

vVec(N, I, EL)->
   ZERO = lists:map(fun(X)->0*X end, lists:seq(1, N)),
   lists:sublist(ZERO, I - 1) ++
   [EL] ++ lists:sublist(ZERO, N - I).

vWorker(PID) ->
   receive
        {V1, V2, N} ->
             P = vVec(length(V1),N,lists:sum(vMul(V1,V2))),
             io:format("~w: [~w/~w] V1=~w * V2=~w == ~w~n",
             [node(), self(), N, V1, V2, P]),
             PID ! {vector, P}
   end.

vScatter([], _V, [], 0, _TOT) ->
   [];
vScatter([MH | MT], V, [PID | REST], N, TOT) ->
   PID ! {MH, V, TOT - N + 1},
   vScatter(MT, V, REST, N - 1, TOT).

vReduce(RES, 0) ->
   RES;
vReduce(RES, N) ->
   receive
        {vector, V} ->
             vReduce(vSum(RES, V), N - 1)
   end.

vSpawn([]) ->
   [];
vSpawn([_H | T]) ->
   [pool:pspawn_link(
         pwnd,
         vWorker,
         [self()]
   )] ++ vSpawn(T).

vStart(M, V) ->
   % Distribute code
   {Mod, Bin, Filename} = code:get_object_code(?MODULE),
   {ResL, []} = rpc:multicall(
        code,
        load_binary,
        [Mod, Filename, Bin]
   ),
   io:format("ResL = ~w~n", [ResL]),
   ZERO = lists:map(fun(X)->0*X end,
        lists:seq(1, length(V))
   ),
   PIDS = vSpawn(lists:seq(1, length(V))),
   io:format("PIDS = ~w~n", [PIDS]),
   vScatter(M, V, PIDS, length(PIDS), length(PIDS)),
   vReduce(ZERO, length(V)).

Заключение
Таким образом, отредактировав всего пару конфигурационных файлов и заменив spawn на pspawn, мы получили гибкое распределенное приложение, способное реагировать на изменения кода.
Для повышения общей производительности есть много вариантов. Например, компиляция BEAM модулей с нативным кодом (HiPE, изначально являлся проектом Upsala University). На тестовой non-SMP одноядерной платформе на базе Celeron 2400 MHz производительность перемножения векторов с количеством элементов ~108 при запуске HiPE модуля увеличилась на 30%. Есть возможность использования портов и драйверов (ports and linked-in drivers) для запуска приложений, написанных на С и других языках. Можно задействовать BLAS. Есть и другие варианты оптимизации.

Ниже, в коде, функция vStart/2 использует автоматический механизм передачи и загрузки модулей (двоичного кода) на узлы кластера. Поэтому отпадает необходимость при изменении программы распространять ее на каждую машину вручную. Кроме того в Erlang реализована возможность горячей замены кода (hotswap) без остановки выполнения приложения, при этом в памяти может существовать 2 версии модуля. Это позволяет существенно снизить или совсем исключить простои, которые являются необходимой мерой при разработке приложений, например, на С, Java и т. д. (подробнее). Некоторые системы, написанные разными разработчиками на Erlang, работают годами и регулярно обновляются.

В 2005 году был представлен проект ERESYE, позволяющий программировать Artificial Intelligence (искусственную разумность:) и экспертные системы в Erlang. Есть пример использования этой технологии.

Т. о. можно наблюдать преимущества функционального программирования в среде Erlang/OTP, в котором за долгую историю языка воплощено и продолжает активно внедряться множество продвинутых технологий, которым даже подражают другие языки, например, Scala (Erlang vs. Scala) и т. д.

Trivia
При загрузке кода в ваш редактор отступы могут сбиться. Для vim в командном режиме перейдите в начало файла (gg) и наберите на клавиатуре команду =G
Это откорректирует отступы.

Источники