Апрельский конкурс по ФП: поэтический вечер
Сегодня я хотел бы дать краткий отчёт о конкурсе по функциональному программированию, который прошёл в начале апреля (как всегда под эгидой Фонда Поддержки Функционального Программирования ФП (ФП) и как всегда по чётным месяцам текущего года). Конкурс получил кодовое наименование «Поэтический вечер им. А.С. Пушкина» и заключался в том, что участникам надо было написать программу, которая восстанавливала бы нарушенный порядок зарифмованных стихотворений. В качестве заходного стихотворения было выбрано произведение «Вурдалак» из цикла «Песни Западных Славян», а для проверки придуманного метода и разработанного алгоритма использовалась сказка «О попе и работнике его Балде».В итоге в конкурсе приняли участие три человека (и ещё как минимум двое попытались, но не сдали ничего). Из представленных языков программирования использовались Scala, Haskell и Shell (в порядке занятых мест). Конечно, я не ограничил условия, и один из конкурсантов написал скрипт, который ищет стихотворение в этих ваших интернетах, но этот участник не предусмотрел того, что найденное стихотворение наверняка не будет совпадать по строкам, что вызовет неимоверную боль в валидаторе, подсчитывающем количество очков. Так оно и случилось.
Для подготовки, оценки результатов и получения эталонного результата мною был написан небольшой модуль на богоспасаемом языке программирования Haskell, который я и хотел бы представить здесь на всеобщее обозрение. Так что кому интересно — добро пожаловать под кат.
Первой задачей, стоявшей передо мной, как перед организатором конкурса, являлась задача подготовки исходных данных. Поскольку сражаться конкурсанты должны были на ниве рифмоплётства, то есть подбора рифм, я решил, ничтоже сумняшеся, взять стихи какого-нибудь великолепного поэта и просто перемешать их строки. Ну, а как можно годно перемешать строки, как не упорядочить их в лексикографическом порядке (исключая всякие знаки препинания и прочее).Это и было сделано. Для этих целей была реализована следующая функция:
sortRhymeFile: FilePath → IO () sortRhymeFile fn = do cnt <- UTF8.readFile fn let cnt' = unlines $ sortBy (comparing (filter isAlpha)) $ filter (not . null) $ lines cnt UTF8.writeFile ("srt_" ++ fn) cnt' Как видно, она берёт файл в кодировке UTF8, читает его, разбивает весь текст на строки, вымарывает из списка пустые строки (они нам не требуются), а затем сортирует, сравнивая только по буквенным символам. После сортировки список снова превращается в текст и записывается в файл с похожим наименованием. Всё Второй задачей явилась необходимость сравнивать присылаемые конкурсантами результаты с оригиналом. Чтобы как-то ранжировать результаты участников, необходимо было придумать формулу. В этом вопросе сложности нет, поскольку можно просто взять и посчитать сумму абсолютных значений разностей между позициями одинаковых строк в двух файлах. Для выполнения этой задачи была реализована такая простая функция: compareRhymeFiles :: FilePath -> FilePath → IO () compareRhymeFiles src tgt = do cSrc <- UTF8.readFile src cTgt <- UTF8.readFile tgt let lSrc = zip (lines cSrc) [1..] mTgt = M.fromList $ zip (lines cTgt) [1..] diff = foldl (cmpLines mTgt) 0 lSrc putStrLn ("Степень различия между представленными файлами: " ++ show diff ++ ".") where cmpLines :: Map String Int -> Int → (String, Int) → Int cmpLines mTgt n (s, i) = case M.lookup s mTgt of Just j → n + abs (i — j) Nothing → error («Произошло невозможное:» ++ s ++ » » ++ show i) Как изящно! Оба файла загружаются в память и разбиваются на строки. После этого списки строк преобразуются в пары, где вторым элементом являются номера этих строк в файлах. Один из списков таких пар преобразуется в ассоциированную карту, но ключами в ней являются не числа, а строки, поскольку искать мы будем номера строк. А далее список пар, который не был преобразован, сворачивается при помощи специальной локальной функции.Эта функция ищет в ассоциированной карте номер заданной строки и при нахождении прибавляет к счётчику абсолютное значение разности позиций строк в двух файлах. А вот если не найдёт, то здесь мне пришлось пойти на остановку работы программы при помощи функции error, поскольку ситуация эта в рамках данного конкретного конкурса невозможна. Но один из конкурсантов, нарушив приличия, добился именно её. Ну да он и приз не получил :).
Теперь осталось рассмотреть мой вариант восстановления рифм в перемешанном стихотворении, который я использовал в качестве Эталона. Я посчитал, что те конкурсанты, кто покажет результат хуже эталонного, не достойны какого-либо приза. К счастью, таковых не оказалось.Итак, как восстановить рифмы? Я резонно посчитал, что обычно у плохих поэтов (каковым я и являюсь) рифмуются последние слоги в слове. Поэтому надо просто взять и выделить оные последние слоги в каждой строке, а потом отсортировать их при чтении задом наперёд, поскольку начала слогов часто разные, а вот окончания точно уж одинаковые.
Задумано — реализовано:
tryPoetry: FilePath → IO String tryPoetry fn = do cnt <- UTF8.readFile fn let pairs = zip (lines cnt) (lines $ filter (\c -> isAlpha c || isSpace c) cnt) step1 = map (second words) pairs step2 = map (second (map syllables)) step1 step3 = sortBy (comparing (reverse. last. last. snd)) step2 step4 = map (second (map concat)) step3 step5 = map (second unwords) step4 poetry = unlines $ map fst step5 return poetry Конечно, эта функция ужасна-ужасна-ужасна. Так не пишут на языке Haskell. Никогда не берите пример с этой функции. Но так уж получилось, а переделывать было уже некогда. А всё дело в определении функции syllables, которая используется здесь. По аналогии со стандартными функциями lines и words, она получает на вход слово и возвращает список его слогов. Только вот беда, возвращает она все буквы в верхнем регистре. Это было сделано потому, что надо было как-то сравнивать буквы в любом регистре с некоторыми списками, да вот так и вышло.А теперь в определении функции tryPoetry пришлось городить пару из двух списков, из которых второй получается рабочим с разбитыми на слоги словами, а из первого берутся строки для результирующей сортировки, и эти строки получаются равными строкам из исходного файла со стихотворением. А в итоге функция делает вот что:
В образце pairs создаётся список пар, первым элементом которых являются строки из перемешанного файла, а вторым — те же строки, но с удалёнными небуквенными символами (остались одни буквы и пробелы), при этом строки соответствуют друг другу. В образце step1 вторые строки в парах разбиваются на слова (стандартная функция words). В образце step2 каждое слово во вторых строках разбивается на слоги (вот оно использование порочно написанной функции syllables, до которой мы ещё доберёмся). В образце step3 список пар сортируется при помощи сравнения (внимание!) обращённого (reverse) последнего слога (первое использование функции last) последнего слова (второе использование той же функции) второго элемента пары (snd). Элементы в парах остаются соответствующими друг другу, хотя список пар уже отсортирован. В образце step4 слоги во вторых элементах пар сливаются в слова. В образце step5 слова во вторых элементах пар сливаются в строки. В образце poetry берутся только первые элементы пар (отсортированные) и превращаются в связный текст, который далее и возвращается. Внимательный читатель увидит здесь, что шаги 4 и 5 не нужны, поскольку после шага 3 строки уже отсортированы так, как надо. Но эти шаги были написаны ради единообразия.Теперь перейдём к функции разбиения слова на слоги. Она работает в полном соответствии с правилами русского языка, и вот её определение:
syllables: String → [String] syllables w = case countVowels word of 0 → [word] 1 → [word] n → s: syllables ss where word = map toUpper w (s, ss) = takeFirstSyllable word
countVowels: String → Int countVowels = foldl (\n c → if c `elem` vowels then n + 1 else n) 0 Сперва она считает количество гласных букв в слове. Если гласных букв нет вовсе, либо она одна такая, то всё слово объявляется одним слогом (то есть это слово состоит из одного слога). Но если гласных букв больше, то мы выделяем первый слог при помощи функции takeFirstSyllable, а остаток слова скармливаем рекурсивно. Так что рассмотрим определение этой важной функции: takeFirstSyllable: String → (String, String) takeFirstSyllable w = (b ++ [f] ++ f', fs') where (b, f: fs) = break (`elem` vowels) w (f', fs') = if head fs `elem` sonorous && head (tail fs) `notElem` vowels then if head (tail fs) == 'Ь' then (take 2 fs, drop 2 fs) else ([head fs], tail fs) else ([], fs) Как раз эта функция работает по правилам русского языка. Сперва она идёт по списку символов до первой гласной буквы. Как только она найдена, все буквы перед ней (образец b) и сама гласная буква (образец f) становятся первым слогом. А затем остаток слова изучается на предмет, не идёт ли после гласной сонорная согласная, но так, чтобы после неё шла не гласная буква. Если такое находится, то к слогу прикрепляется и эта сонорная согласная.А вот сами списки гласных букв и сонорных согласных:
vowels: String vowels = «АЕЁИОУЫЭЮЯ»
sonorous: String sonorous = «ЙЛМНР» На этом всё. Этот метод действительно был очень слаб, но рифмованные строки он вполне находил, так что он как раз решал свою задачу — был правильным, но при этом был достаточно слабым, чтобы быть эталонным для сравнения результатов конкурсантов. Данный конкурс и задача в нём были несколько неадекватны, поскольку для решения подобного рода задач необходимы методы искусственного интеллекта и компьютеры типа IBM Watson. Взять хотя бы проблему выбора первой строфы, которая всегда будет вставать, когда заканчивается рифма. Ну и неоднозначность имеет место тоже. Так что простыми эвристиками и манипуляцией символами здесь никак не обойтись, требуются попытки использовать смысл текста.Однако наработанные в рамках конкурса результаты вполне могут быть употребимы и на пользу. Например, функцию поиска рифм можно с успехом применить при реализации помощника для поэтов и поэтесс, который будет находить тем, кого оставила муза, интересные и нестандартные рифмы. Само собой разумеется, что такую функцию можно параметризовать способом рифмования, накрутить на неё гигантский словарь слов и т. д., и т. п. Всё это ждёт своего заинтересованного разработчика.
Отдельно стоит отметить, всё же, решение конкурсанта, который использовал поиск в сети Интернет для нахождения правильного порядка строк. Вот здесь я вижу уже зачатки слабенького искусственного интеллекта. Почему бы и нет? Почему нельзя разрешить боту обращаться за помощью в глобальное информационное пространство? А вот и можно и даже нужно. Поэтому, всё-таки, решение это я отмечаю особенно, а его автору направляю свои аплодисменты.
Как всегда всякий желающий может получить файл с исходными кодами, рассмотренными в этой небольшой заметке, здесь.
Мои предыдущие статьи о конкурсах по ФП на Хаброхабре:
