Подмешиваем эффекты - теория

[migmit]

Есть у меня один проектик, никому, кроме меня, не нужный, а потому холимый, лелеемый и регулярно вычёсываемый. Проектик большой, целых двести строк (чёрт, исходники картинок к этой статье чуть не в два раза больше, и я уж молчу про саму статью) и под десять килобайт исходников (да, я люблю длинные строки). Временами из него вычленяются отдельные куски, которые вполне можно показать людям. Вот, на днях один такой попался. Родился он из медитации над заброшенным пакетом lax с hackage, который благополучно не устанавливается cabal-ом, но при этом состоит всего из одного вполне рабочего файла, который можно просто взять и использовать (ну, прагму надо будет прописать в начале).
Окончили лирику, переходим к делу. Задачка передо мной стояла совершенно классическая — взять две стрелки, перемешать, посолить, поперчить и сделать из них одну.
Чуть более подробно. У меня была некая стрелка. Вполне себе чистенькая — писалась исключительно с использованием чистых функций. Возникла необходимость добавить к ней эффекты — то есть, пока работают "эффекты" самой стрелки, дополнительно ещё производить некое IO. То есть, наши стрелки изначально неравноправны: есть стрелка a, которая, по сути, будет ни чем иным, как Kleisli IO, и стрелка b, делающая основную работу, но при этом чистая. И мы хотим слепить из всего этого что-то одно.
Основная идея будет такой: мы организуем некий цикл, где то, что подаётся на вход, будет сразу скармливаться стрелке b, часть выхода пойдёт к стрелке a, а то, что она выдаст, будет возвращаться к b:


Разумеется, так прямо сделать нельзя. Однако, никто не мешает нам хранить те части этого цикла, которые действительно имеют значение:


Посмотрим, удастся ли при таком подходе сделать что-нибудь полезное. Для начала, хорошо бы убедиться, что мы можем встроить в это дело исходные стрелки a и b. Оказывается, вполне можем, и вот как:




Комбинатор first делается элементарно:


А вот композиция — уже интереснее. Мы ведь хотим, по сути дела, следующего:



Мы можем перерисовать это дело так, чтобы стало более похоже на один цикл:



И вот тут нас поджидает засада.
Засада состоит в следующем. Забудем пока про чистую стрелку b, она не имеет значения. Допустим, мы поднимаем и соединяем последовательно две стрелки с эффектами, одна из которых читает ввод, а другая его же выводит обратно на экран. Мы получим, фактически, следующее:


Я чуть разверну цикл, чтобы интересные нам стрелки смотрели слева направо:


Что мы видим? А видим мы, что стрелка putStrLn на вход принимает то, что возвращается назад мимо неё. Увы, монада IO к таким штукам относится очень нервно. Если мы аккуратно напишем всё то, о чём пока говорили неформально, и запустим этот пример, то получим классическое "Expression: <<loop>>". А это не та реакция, которая нам нужна.
Желающие в этом убедиться могут попробовать такой пример:

echoL =
    proc ((), line) ->
        do line' <- Kleisli (const getLine) -< ()
           Kleisli putStrLn -< line
           returnA -< ((), line')
echo = runKleisli (loop echoL) ()

Ввести строчку эта стрелка ещё позволит, но на выводе получим тот самый цикл.
Нужно поправить ситуацию так, чтобы ни одна IO-стрелка не зависела от того, что идёт назад мимо неё. И сделать это можно, перенеся образование цикла в функцию "подъёма" стрелки a. Тогда вместо одного большого цикла мы получим что-то вроде



— а это гораздо лучше. Настолько лучше, что работает.
Есть и другое описание такого решения: везде, где что-то соединяется в пары, можно найти композицию. Это эмпирический (пока, по крайней мере) принцип, но он работает. В данном случае, композиция наших циклов приводит к тому, что "обратные" стрелки в нижней части цикла соединяются параллельно — а значит, композиция где-то рядом.
Более точно. Вместо одной стрелки



мы берём функцию (чистую!), которая вот такую стрелку:



преобразует вот в такую:



Тогда параллельное соединение стрелок, которое мы использовали раньше, превратится как раз-таки в композицию. Изобразить это дело на диаграмме уже не получится, или, по крайней мере, будет весьма затруднительно; поэтому, я нарисую несколько диаграмм так, как будто мы используем старое, "наивное" решение с одной стрелкой a, а уж в коде будет "продвинутое" решение, с функцией, преобразующей стрелки.
Собственно говоря, нарисовать осталось немногое. Займёмся комбинатором loop. То есть, у нас есть вот такая конструкция:



и мы хотим замкнуть нижние "висящие" хвосты. Интересно то, что мы можем это сделать двумя способами. Первый способ — ввести цикл в стрелку b, второй — пустить его вдоль стрелки a. С точки зрения диаграмм получается такое:






Самое смешное в том, что я не нашёл отличий в их функциональности. Может, конечно, они и есть, но мне лично кажется, что они эквивалентны, причём что это можно формально доказать. В ближайшее время я этим попробую заняться. Первый вариант, однако, записывается короче, выглядит более похоже на другие комбинаторы, и, в целом, больше мне нравится. Так что, использовать я буду именно его, а второй вариант пойдёт комментарием.
Наконец, самый важный вопрос: можем ли мы получить из таких циклов что-нибудь обратно? А то, выглядят они, конечно, симпатично, но не более того. Ответ — да, можем, но не вполне банальным образом. Идея в том, чтобы для начала заменить стрелку b на функцию, а затем оставить вообще только стрелку a, от которой нам, так уж получилось, деваться некуда — именно в ней будут настоящие эффекты, которые в чистую функцию не переделать никак. В наивном подходе нам нужно будет замкнуть цикл, воспользовавшись тем, что стрелка a имеет оператор loop; в продвинутом подходе всё окажется на порядок проще.
Продолжение следует.