Заголовок данной статьи является очень двусмысленным. Это станет понятно из дальнейшего изложения. Покамест лишь объявим, что сейчас мы опишем решение задачи конкурса по функциональному программированию, который проводился в январе 2012 года. В качестве задачи почтенным участникам предлагалось расшифровать зашифрованный исходный код простейшим шифром на основе циклического применения ключа к тексту посредством операции XOR. В условиях задачи дополнительно сообщалось, что зашифрован код на языке Haskell, длина ключа не превышает 5 символов, а сам ключ состоит только из заглавных символов латинского алфавита.

В итоге 17 претендентов на призы прислали свои решения, расшифровав исходник, запустив его и прислав правильный код, который этот исходник сгенерировал для участника. Из этих участников 16 получили призы (один прислал правильный ответ после завершения конкурса). Так что теперь остаётся посмотреть, что и как было в этом конкурсе.

В одной из своих предыдущих статей («Реализация конструирования N-грамм и генерации псевдо ЕЯ-текста на их основе на языке Haskell») я рекомендовал читателю в качестве самостоятельного упражнения реализовать для построения N-грамм интерактивную среду. В сегодняшней заметке я покажу, как это можно сделать в виде консольного приложения на языке программирования Haskell. За основу мы возьмём эссе № 8 из моей книги «14 занимательных эссе о языке Haskell и функциональном программировании», которое называется «Простой интерпретатор команд», но применим в этой статье немного монадического кун-фу.

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

1. Как создавать свои собственные монады при помощи техники нанизывания имеющихся монад друг на друга посредством трансформаторов монад?
2. Как строить цикл интерпретации команд, в котором происходит распознавание введённой команды, её выполнение и вывод результатов (REP)?
3. Как в этом цикле «таскать» из функции в функцию изменяемое состояние, не прилагая для этого никаких усилий?
4. Как в любом месте цикла интерпретации бросать исключения и ловить их, обрабатывая красивым образом?
5. Как предоставлять пользователю возможность вводить команды в очень гибком режиме?

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

Данная статья в какой-то мере является переработкой и улучшением эссе № 14 из моей книги «14 занимательных эссе о языке Haskell и функциональном программировании». Статья посвящена генерации рекурсивных (или кумулятивных) сказок при помощи обобщённых функций, реализующих определённые паттерны рекурсии. Такие функции вместе со вспомогательными структурами данных и другими программными сущностями будут собраны во фреймворк для повторного использования при решении задач генерации естественно-языкового текста (ЕЯ-текста).

Что такое «рекурсивная сказка»? Рекурсивная сказка — это сказка с повторяющимся сюжетом. Есть многое множество примеров рекурсивных сказок практически у всех народов мира, и учёные даже составили довольно-таки разветвлённую классификацию оных рекурсивных сказок. Есть сказки с простым перечислением (например, английское стихотворение «Дом, который построил Джек»), есть с двойным (например, русская народная сказка «Теремок», где при появлении каждого нового персонажа все предыдущие выходят и представляются). Есть сказки, где перечисляются сами действующие лица, а есть и такие, где одно действующее лицо перечисляет какие-либо предметы (например, сказка «Лисичка со скалочкой»), либо выполняет какие-либо повторяющиеся действия (сказка «Петушок и бобовое зёрнышко»). Такие сказки, по свидетельстам фольклористов, являются одними из самых древних, и отражают глубинные архетипы человеческой психики. Ну а их предназначение достаточно просто — успокоение детей повторяющимся ритмом повествования и обучения их базовому набору слов.

Сего дня мы продолжим рассмотрение темы генерации естественноязыковых текстов, начатую в предыдущей моей статье «Генерация естественно-языковых фраз при помощи языка Haskell на основе порождающих грамматик и расширенных цепей Маркова». Возможно, что некоторым из вас сегодняшние вопросы покажутся несколько неприменимыми к теме синтеза ЕЯ-текста, однако в одно время этот подход широко обсуждался. Ну а использование статистических методов в лингвистике для анализа синтагматических отношений как использовалось, так и используется по сей день. Итак, речь поведём о так называемых N-граммах.

N-грамма — непрерывная последовательность из n символов, взятых из заданной большей последовательности тех же символов. Под символами могут пониматься такие объекты, как буквы, фонемы, слоги, морфемы, слова, пары оснований ДНК и другие подобные объекты. Каждой N-грамме приписывается частная вероятность, подсчитанная на основе выборки всех возможных N-грамм из достаточно большого корпуса текстов (под «текстом» здесь понимается соответствующая последовательность объектов — собственно тексты, речь на естественном языке, геном и т. д.).

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

Однако здесь мы рассмотрим лишь один из методов, к тому же скрещённый с расширенными цепями Маркова. Этот метод позволяет генерировать ЕЯ-текст только по заранее заготовленному шаблону, а разнообразие (мера сложности) вариантов достигается при помощи цепей Маркова. Шаблон, описываемый порождающей грамматикой, для каждого терма наполняется множествами возможных вариантов реализации терма в виде ЕЯ-слова или фразы, при этом каждому варианту реализации ставится в соответствие вероятность его проявления среди множества других вариантов реализации терма.

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

Даны числа 1, 5, 6 и 7. При помощи произвольного числа арифметических операций и скобок необходимо составить такое математическое выражение из этих чисел, чтобы его значение было равным 21. Данные числа можно использовать в выражении ровно по одному разу. Числа нельзя «склеивать» друг с другом (то есть из 1 и 5 нельзя получать 15 и т. п.).

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

При разработке некоего программно-аппаратного комплекса потребовалось создать клиентское устройство, которое для прочих устройств должно выглядеть как обычная USB-флешка, или если более формально, то USB Mass Storage Device. Необычность устройства в том, что оно должно имитировать для внешнего мира файловую систему FAT с файлами достаточно большого размера (2GB и и более), при том, что сами файлы на устройстве, конечно, отсутствуют и находятся в сети. Да и вообще это не файлы, а некие аудио-потоки.

Задача, на первый взгляд, простая: на каждый запрос на чтение блока (команду SCSI) отдаем содержимое этого блока. Блок может либо принадлежать какому-нибудь из «файлов», либо содержать служебную информацию FAT.

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

Крестьянину нужно перевезти через реку волка, козу и капусту. Но лодка такова, что в ней может поместиться только крестьянин, а с ним или один волк, или одна коза, или одна капуста. Но если оставить волка с козой, то волк съест козу, а если оставить козу с капустой, то коза съест капусту. Как перевёз свой груз крестьянин, если известно, что все переправились через реку в целости и сохранности?

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

Дан индикатор, состоящий из n лампочек, которые могут гореть или не гореть. Дан алфавит из k символов, которые закодированы различными комбинациями горящих и не горящих лампочек на индикаторе. Необходимо определить максимальное число лампочек индикатора p (p <= n) и указать эти лампочки, которые, если и перегорят, то не влияют на однозначное распознавание всех символов алфавита.

Введение

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

Обозначения

В прошлый раз я хотел обозначить морфизм/функцию буквой f, но она была занята для обозначения функтора/переменной типа f – никакой проблемы с точки зрения языка Haskell в этом нет, но при невнимательном прочтении это может вызвать путаницу, и я использовал для морфизма букву g. Пустяк, но всё же, я считаю, что полезно визуально разделять сущности, имеющие разную природу. Обычные типы я буду называть их обычными именами, а вот переменные типов я буду называть маленькими греческими буквами, причём простые (∗) – буквами из начала алфавита, а параметрические (∗ → ∗) – буквами из конца алфавита (θ не из конца, но она смотрится лучше, чем χ, которая слишком похожа на X). Итак, в терминологии категории Hask:

• Объекты: α, β, γ, δ ∷ ∗
• Функторы: θ, φ, ψ, ω ∷ ∗ → ∗
• Морфизмы: f, g, h ∷ α → β

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

Ещё одно замечание, касательно терминологии: как вы уже заметили, то, что я в прошлый раз называл словом “кайнд” (kind), я теперь называю словом “сорт” – это считается общепринятым переводом.

Категория с объектом Hask

Давайте рассмотрим категорию, в которой будет только один объект – сама категория Hask. Что же будет морфизмами в такой категории? Это должны быть какие-то отображения Hask → Hask, и мы уже знаем такой тип отображений – это эндофункторы категории Hask, то есть типы сорта ∗ → ∗, воплощения класса Functor. Теперь нужно продумать как устроены единичный морфизм и композиция в этой категории, так чтобы они удовлетворяли аксиомам.