6.2.3. Рекурсивная do-нотация

6.2.3.1. Рекурсивные группы связываний

Расширение RecursiveDo также вводит новое ключевое слово rec, которое помещает группу взаимно рекурсивных монадических операторов внутрь выражения do, образуя один оператор. Подобно оператору let внутри do, переменные, связанные в rec, видны во всей группе rec и далее. Например, сравните:

do { a <- getChar            do { a <- getChar
   ; let { r1 = f a r2          ; rec { r1 <- f a r2
   ;     ; r2 = g r1 }          ;     ; r2 <- g r1 }
   ; return (r1 ++ r2) }        ; return (r1 ++ r2) }

В обоих случаях r1 и r2 доступны во всём блоке let или rec, а также в следующих за ним операторах. Разница в том, что let не является монадическим, а rec является. (В Haskell let, конечно же, на самом деле является letrec.)

Семантика rec довольно проста. Когда GHC обнаруживает группу rec, он вычисляет множество связанных в ней переменных и вводит соответствующий вызов оператора рекурсии значений для базовой монады mfix, принадлежащего классу MonadFix. Вот пример:

rec { b <- f a c     ===>    (b,c) <- mfix (\ ~(b,c) -> do { b <- f a c
    ; c <- f b a }                                         ; c <- f b a
                                                           ; return (b,c) })

Как обычно, метапеременные b, c и т. д. могут быть произвольными шаблонами. В общем случае оператор rec ss преобразуется в оператор

vs <- mfix (\ ~vs -> do { ss; return vs })

где vs — кортеж переменных, связанных в ss.

Обратите особое внимание: преобразование блока rec заключается лишь в обёртывании вызова mfix; никакой другой анализ связываний не выполняется. Это задача mdo-нотации, описанной далее.

6.2.3.2. Нотация mdo

Блок rec указывает компилятору, где именно следует завязать рекурсивный узел. Оказывается, расположение рекурсивных узлов может быть довольно тонким вопросом: в частности, желательно оборачивать их вокруг как можно более малых групп. Этот процесс называется сегментацией и подробно описан в разделе 3.2 статьи Рекурсивный do для Haskell. Сегментация улучшает полиморфизм и уменьшает размер рекурсивного узла. Что особенно важно, она позволяет избежать ненужного взаимодействия, вызванного фундаментальной проблемой так называемой аксиомы правого сокращения для монадической рекурсии. Вкратце, у большинства интересующих нас монад (IO, строгого состояния и т. д.) операторы рекурсии не удовлетворяют этой аксиоме, поэтому отказ от сегментации может привести к ненужному взаимодействию и изменить поведение результирующего преобразования при завершении. (Подробности приведены в разделах 3.1 и 7.2.2 работы Рекурсия значений в монадических вычислениях.)

Нотация mdo избавляет от необходимости явно размещать в коде блоки rec. В отличие от обычного выражения do, в котором переменные, связанные операторами, видны только последующим операторам, переменные, связанные в выражении mdo, видны во всех операторах этого выражения. Затем компилятор автоматически определяет минимальные сегменты операторов с взаимной рекурсивной зависимостью, обрабатывая их так, как если бы пользователь заключил их в квалификатор rec.

Определение является синтаксическим:

• Генератор ⟨g⟩ зависит от следующего за ним в тексте генератора ⟨g’⟩, если

  • ⟨g’⟩ определяет переменную, используемую в ⟨g⟩, или
  • ⟨g’⟩ расположен в тексте между ⟨g⟩ и ⟨g’’⟩, причём ⟨g⟩ зависит от ⟨g’’⟩.
• Сегмент данного выражения mdo — это минимальная последовательность генераторов, в которой ни один генератор не зависит от генератора вне этой последовательности. В частном случае заключительное выражение в выражении mdo считается отдельным сегментом, хотя оно и не является генератором.

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

Вот пример выражения mdo и его преобразование в блоки rec:

mdo { a <- getChar      ===> do { a <- getChar
    ; b <- f a c                ; rec { b <- f a c
    ; c <- f b a                ;     ; c <- f b a }
    ; z <- h a b                ; z <- h a b
    ; d <- g d e                ; rec { d <- g d e
    ; e <- g a z                ;     ; e <- g a z }
    ; putChar c }               ; putChar c }

Обратите внимание: одно выражение mdo может привести к созданию нескольких блоков rec. Если рекурсивных зависимостей нет, mdo не добавит блоков rec. В последнем случае выражение mdo в точности совпадает с выражением do, как и следовало ожидать.

Подводя итог: получив выражение mdo, GHC сначала выполняет сегментацию, добавляя блоки rec вокруг минимальных рекурсивных групп. Затем каждое полученное выражение rec преобразуется в код с помощью вызова Control.Monad.Fix.mfix, как описано в предыдущем разделе. Исходное выражение mdo проходит проверку типов тогда и только тогда, когда её проходит преобразованная версия.

Ниже приведены другие важные замечания по использованию рекурсивной do-нотации:

• Она включается расширением RecursiveDo или прагмой LANGUAGE RecursiveDo. (Это же расширение включает mdo-нотацию и использование блоков rec внутри выражений do.)
• Блоки rec также можно использовать внутри выражений mdo; при этом они будут рассматриваться как один оператор. Однако хорошим стилем считается использовать в одном выражении либо блоки mdo, либо блоки rec.
• Если для монады требуются рекурсивные связывания, эта монада должна быть объявлена экземпляром класса MonadFix.
• Автоматически предоставляются следующие экземпляры MonadFix: List, Maybe, IO. Кроме того, модули Control.Monad.ST и Control.Monad.ST.Lazy предоставляют экземпляры класса MonadFix для внутренней монады состояния Haskell (строгой и ленивой соответственно).
• Как и для связываний let и where, затенение имён не допускается внутри выражения mdo или блока rec; то есть все имена, связанные в одном rec, должны быть различными. (В противном случае GHC сообщит об ошибке.)