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

В файле, находящемся по известному адресу, записано 100 тысяч условий арифметических задач на четыре действия: сложение, вычитание, умножение и деление. Условия записаны на естественном языке. В качестве результата необходимо представить файл с ответами на задачи — по одному ответу в виде натурального числа на каждой строке (итого 100 тысяч строк).

Недавно я всё же решил сесть и разобраться с Yi — текстовым редактором наподобие Vim и Emacs, но написанном на Haskell. В комплекте даже есть Vim и Emacs симуляция.
Из-за отстутствия опыта с Vim или Emacs, мне подошла лишь Cua-симуляция. Хоткеев там мало, но зато они привычные для меня. Поэтому я решил начать с него и написать настройку для себя.
В обычных графических редакторах мне кажется удобным способ использования меню. Нажимаешь alt, открывается меню, где у каждого элемента подчёркнута буква, нажав которую, мы этот элемент выберем.
Таким образом не надо запоминать все команды сразу, а можно начинать пользоваться, подглядывая в меню, постепенно доводя до автоматизма.
Нечто подобное я решил прикрутить и в Yi.

В ставших уже традиционными ежемесячных конкурсах по функциональному программированию всем желающим предлагается поразмять свои мозги и представить на суд общественности своё решение конкурсной задачи на каком-либо языке программирования (кстати, совсем не обязательно функциональном — многие конкурсанты используют и такие экзотические языки, как Java и даже Python). В апрельском конкурсе в качестве задачи была предложена задача по поиску цепочки трансмутаций между словами в заданном словаре. Конечно, это есть задача по поиску [кратчайшего] пути в графе, рёбра которого представляют возможность перехода от слова к слову по заданному правилу (должна быть изменена и только изменена одна и только одна буква), однако задача заинтересовала участников, и в качестве результатов было представлено 22 решения на 9 различных языках (C++, Clojure, D2, Erlang, F#, Go, Haskell, Mathematica и Perl).

Словарь, по которому осуществлялся поиск, можно получить здесь. Впрочем, можно воспользоваться услугами сайта «Слова из букв», с которого, собственно, и получен словарь. Конечно, многие слова там очень странные, однако какая нам разница, на каком словаре строить граф для конкурса? Пусть это будут просто формальные цепочки символом. А по результатам конкурса вообще появлялись такие предложения от участников: «Надо написать новое определение слова «АХЧЕ» — это слово, которое используется в конкурсах по программированию, для порождения самых длинных метаграмм».

Ну а поскольку конкурс был назван «Кельтская алхимия», занимались мы трансмутациями следующих пар слов (метаграмм):

1. МУХА — СЛОН
2. ДЕНЬ — НОЧЬ
3. СНЕГ — ВОДА
4. ОТЕЦ — МАТЬ
5. РУКА — НОГА
6. ЗИМА — ЛЕТО
7. СВЕТ — ТЬМА
8. ЛИПА — КЛЁН

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



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

Для решения одной из задачек из стэнфордского курса по криптографии понадобилось создать таблицу соответствия Word64 -> Integer и несколько миллионов раз проверить в ней наличие элемента и добавить новый. Решение очевидно: хэш-таблицы. hoogle предложил Data.HashTable, программа была написана, успешно отработала и можно было бы обо всем забыть, но захотелось потренироваться в профайлинге и оптимизации.

Запуск с +RTS -sstderr вызвал легкий шок: почти половина времени уходила на сборку мусора.

Как известно, функциональный подход к программированию имеет свою специфику: в нём мы преобразовываем данные, а не меняем их. Но это накладывает свои ограничения, например при создании программ активно взаимодействующих с пользователем. В императивном языке намного проще реализовать такое поведение, ведь мы можем реагировать на какие либо события «в реальном времени», в то время как в чистых функциональных языках нам придётся откладывать общение с системой до самого конца. Однако относительно недавно стала развиваться новая парадигма программирования, решающая эту проблему. И имя ей — Functional Reactive Programming (FRP). В этой статье я попытаюсь показать основы FRP на примере написания змейки на Haskell с использованием библиотеки reactive-banana.

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

Интересующихся прошу проследовать под кат.

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

У Вас есть два сосуда, один объёмом 5 литров, а другой объёмом 8 литров. Вы можете наливать сосуды до края какой-то жидкостью (будьте осторожны, возможно, что она едкая или ядовитая) из крана. Вы можете выливать жидкость из сосуда в технологическую раковину. Вы можете переливать жидкость из сосуда в сосуд так, что либо в первом сосуде закончится жидкость, либо второй наполнится до краёв (что произойдёт ранее). Ваша задача — отмерить 2 литра жидкости.

Я придумываю особенную игру в жанре космического симулятора. Согласно одной из ключевых концепций, в игре будет встроенный язык программирования, с помощью которого можно разрабатывать и улучшать алгоритмы взаимодействия игровых элементов. Дизайн такого языка — дело непростое, учитывая его «натуральность», а не «текстовость». То есть, конструкции языка выражены в виде разных графических объектов. Рисуя эскизы его конструкций, я неожиданно для себя отвлекся и вместо языка для игры стал придумывать язык для визуализации Haskell-кода. Получалось так интересно, что я не мог оставить эскизы просто бумажными рисунками. В январе 2012 года я начал писать сервер визуализации, и вот что получилось…

10 февраля сего года состоялся февральский конкурс по функциональному программированию, который был посвящён Дню научного работника. Несмотря на то, что в конкурсе приняло участие всего лишь 4 человека (с причиной этого я ещё буду разбираться), результаты хороши — по крайней мере двое участников представили достаточно хорошее решение, которое подходит в большинстве случаев. А задача была проста — написать программу, которая для заданной шахматной задачи на мат в один ход ищет этот самый ход (а ходов может быть и несколько, конечно). Ну а на затравку конкурсантам была дана простейшая задача:



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