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

В одном моем проектике (который эти самые пресловутые ГА) нужно было представлять математические выражения деревьями и всю работу с этими выражениями делать через эти деревья. Соответственно, был статичный словарь ([(a, b)]) идентификаторов функций и, собственно, самих функций. Вернее, два таких словаря, для унарных и бинарных функций. Что-то типа такого:

data UnaryFunc = Sin | Cos | Log | Tan | Asin | Acos | Atan
    deriving (Show, Eq, Ord)
 
data BinaryFunc = Plus | Minus | Mul | Div | Pow
    deriving (Show, Eq, Ord)
 
unaryOps :: Floating a => [(UnaryFunc, a -> a)]
unaryOps = [ (Sin, sin), (Cos, cos), (Log, log), (Tan, tan), (Asin, asin), (Acos, acos), (Atan, atan) ]
 
binaryOps :: Floating a => [(BinaryFunc, a -> a -> a)]
binaryOps = [ (Plus, (+)), (Minus, (-)), (Mul, (*)), (Div, (/)), (Pow, (**)) ]

Соответственно, кусок функции вычисления значения дерева в точке, обрабатывающий вершины с функциями, выглядел как-то так:

evalTree vars (NUn f t) | Just f' <- lookup f unaryOps = f' $ evalTree vars t
                        | otherwise = error $ "Unknown uf " ++ show f
evalTree vars (NBin f l r) | Just f' <- lookup f binaryOps = f' (evalTree vars l) (evalTree vars r)
                           | otherwise = error $ "Unknown bf " ++ show f

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

COST CENTRE                    MODULE               %time %alloc
evalTree                       ExprTree              47.7   13.6                                                                                                                                                                                                                                                         
binaryOps                      Funcs                 17.2   47.9

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

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

binaryOps :: Floating a => BinaryFunc -> a -> a -> a
binaryOps Plus = (+)
binaryOps Minus = (-)
binaryOps Mul = (*)
binaryOps Div = (/)
binaryOps Pow = (**)

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

evalTree :: Floating a => [(String, a)] -> ExprTree a -> a
evalTree _ (LC c) = c
evalTree vars (LVar (Var v)) | Just c <- lookup v vars = c
                             | otherwise = error $ "Unknown var " ++ v
evalTree vars (NUn f t) = unaryOps f $ evalTree vars t
evalTree vars (NBin f l r) = binaryOps f (evalTree vars l) (evalTree vars r)

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

В результате, правда, binaryOps все еще жрет 20% процессора и ответственна за треть аллокаций. Однако, стоит иметь ввиду такой очевидный факт, что компиляция с -prof -auto-all существенно меняет то, как исполняется код, и отменяет часть оптимизаций, поэтому ориентироваться на конкретные цифры бессмысленно. Главное — что скорость без профилирования существенно повыше стала.

В принципе, если бы не нужно было бы Ord и Eq от деревьев, то можно было бы хранить сами функции в вершинах вместо их идентификаторов.

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

Правда, для этого придется еще пообмазываться type families всякими, ибо хранить уже скомпилированное дерево в том же ExprTree не получится, а генетические алгоритмы у меня работают не напрямую с деревьями, а с инстансами тайпкласса GAble a, поэтому нужно будет запилить что-то типа

class (...) => GAble a where
    type Compiled a :: * -> *

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

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

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

За 40 минут был написан текст программы:

Сорс также доступен по https://gist.github.com/1340356 , если у кого не вставилось.

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

• uniDistr делает пару нормально распределенных чисел из пары равномерно распределенных, и возвращает остаток бесконечного списка этих равномерно распределенных. Для преобразования используется преобразование Бокса-Мюллера.
• unis дергает uniDistr, чтобы преобразовать бесконечный список равномерно распределенных случайных чисел в случайно распределенные.
• makeDoc по списку слов из словаря, требуемому размеру в символах и списку заранее сгенеренных случайных величин делает документ, используя makeDoc' как рекурсивно вызываемую «рабочую лошадку».
• genSingle получает список слов из словаря, рандомный генератор и пару чисел — число документов и размер одного документа в символах. Дергает makeDoc, чтобы сгенерить каждый из документов. Результатом является список из пар (ИмяДокумента, СодержаниеДокумента).
• gen делает примерно то же самое, что и genSingle, но только принимает не одну пару «размер-число документов», а их список, и для каждой такой пары дергает genSingle.
• gs делает из одного случайного генератора бесконечный список случайных генераторов применяя unfoldr со сплитом.

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

По памяти могу сказать, что для массива слов в первом приближении использовался банальный список, и поэтому в строке 26 на операции индексации все адово тормозило — профайлер показал, что в этом месте жралось 97% процессорного времени, а скорость генерации была такой, что нужный мне объем текстов породился бы по моим прикидкам за пару суток. Впрочем, это довольно очевидное место — списки не очень круто использовать для случайного доступа, поэтому список был заменен на Data.Array, что существенно увеличило скорость генерации. Почти на три порядка, кажется, сейчас точно не вспомню.

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

И вот после этой пары оптимизаций (и еще пары совсем незначительных) я уперся в сам процесс генерации текстов. И тут мы подступаем к самому интересному: любой внимательный читатель заметит, что это просто отличный кандидат на распараллеливание! Пусть один тред генерит себе один текст, другой тред — другой, и так далее.

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

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

Для вычисления в нужном треде используются вещи из Control.Parallel.Strategies, в частности, parMap и parListChunk Последний позволяет задавать количество элементов, которые уйдут каждому треду, а это полезно, чтобы, например, наплодить не 1000 мелких заданий, а 8 крупных, так как у меня все же не 1000, а всего 8 ядер. Есть несколько разных стратегий вычисления, используемых с parMap/parListChunk. Нужная нам — rdeepseq. Эта стратегия позволяет проходить по всему списку thunk'ов, убеждаясь, что каждый из них вычислится там, где надо, а не в основном треде.

Окей, написали parListChunk, отлично, параллельно, но... Блин, жрет память как не в себя, гигабайтами на сколь значимо больших объемах данных. А почему? А потому, что теперь, как мы и просили, все санки действительно вычисляются сразу. До добавления этого parListChunk было просто: при записи на файл оказывается, что строку-то надо вычислить, а так как запись идет блоками, а не сразу вся, то и вычисляется, например, первые 16 килобайт. Или пусть даже 16 мегабайт, не суть, все равно мало. Вычислилось, записалось, больше не нужно, Garbage Collector за нами прибрал, память освободилась. Все отлично, много памяти в один момент времени не жрется, и ваще. А теперь каждый документ вычисляется сразу и весь держится в памяти до тех пор, пока не будет записан на диск, поэтому все логично и разумно.

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

Энное время я пописываю один матан-проект с реализацией на хацкеле, который по совместительству является моей бакланаврской дипломной работой на этом курсе. На днях читал на haskellwiki статью о том, как надо писать программы, и пришла мне в голову идея, что и правда было бы неплохо как-то освещать все это дело. Пожалуй, можно было бы писать как о хаскель-проблемах, возникающих при решении этой задачи, от «пишем собственные матрицы» до «блин-нахрена-экзистенциальные-и-дуальные-типы-при-дифференциировании-вперед», так и о сопутствующей математике. Кроме того, хотелось бы получить фидбек о проекте, начиная от «чувак, твой код — полное дерьмо» и до конструктивных обсуждений всякого матана.

Собственно, теперь о проекте. Проект заключается в применении эволюционных алгоритмов к задаче восстановления регрессии — иными словами, фигачим генетическими алгоритмами по множеству математических формул и смотрим, что лучше описывает какие-то там данные. Можно погуглить по «symbolic regression», например.

Помимо прикладной части (кода, реализующего все это дело), в работе есть какие-то попытки теоретически обосновать применимость этих алгоритмов. В частности, в тех работах (Джон Коза, Иван Зелинка), которые я видел (и про которые научрук говорит, что это более-менее bleeding edge), не обосновывается теоретически вообще ничего, а просто предлагается некоторый алгоритм, который типа как работает. Что, почему, зачем — непонятно. В то же время, я пытаюсь хоть как-то что-то обосновать-оценить, ну и, кроме того, есть ряд идей о том, как сам прикладной алгоритм можно еще улучшить. А еще было бы круто найти там где-нибудь групповую структуру или что-то такое, да.

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

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

Так что, в общем, если это кому интересно — попинайте меня. Комментить можно в стандалоне, в жоже, в пстоще, да и выцепить меня в конфочках math@conference.jabber.ru и c_plus_plus@conference.jabber.ru.

...тем больше я понимаю, что, скорее всего, никогда не буду на нем писать ничего, кроме прототипов или чего-нибудь академического-научного. Лучше после такого мощного, жесткого, но офигенно драйвового погружения в ФП выучу за вечерок-другой Erlang/OCaml и буду писать на них.

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

Сначала написал на C++ за 30 минут — 118 строк. Этак строк 100, если убрать проверку на ошибки.

Потом подумал и решил, что неплохо было бы написать на Haskell, ибо как раз учу язык, попрактиковаться лишний раз неплохо, да и просто посмотреть на реакцию препода. Да, заняло часа два. Да, обратился к помощи коллег. Но язык непривычный, не знал, как лучше сделать те или иные вещи, да и вообще. Итог: 43 строки, прозрачный код и никакого лоу-левела. Приятно и фапабельно.

C++-вариант (код говно, знаю).
Haskell-вариант (код еще большее говно, знаю).

Да, с радостью выслушаю критику обоих вариантов.