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 A recursive do for Haskell. Сегментация улучшает полиморфизм и уменьшает размер рекурсивного узла. Что наиболее важно, она предотвращает ненужное вмешательство, вызванное фундаментальной проблемой так называемого аксиомы right-shrinking для монадической рекурсии. Короче говоря, большинство интересующих нас монад (IO, строгое состояние и т. д.) не имеют операторов рекурсии, удовлетворяющих этому аксиому, и поэтому отсутствие сегментации может привести к ненужному вмешательству, изменяя поведение завершения результирующего перевода. (Подробности см. в разделах 3.1 и 7.2.2 Value Recursion in Monadic Computations).

Обозначение 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 автоматически предоставляются: Список, Может быть, IO. Кроме того, модули Control.Monad.ST и Control.Monad.ST.Lazy предоставляют экземпляры класса MonadFix для внутренней монады состояния Haskell (строгой и ленивой соответственно).
• Как и в случаях с let и where связями, перекрытие имён не допускается внутри выражения mdo или блока rec ; то есть все имена, связанные в одном выражении rec , должны быть различными. (GHC будет выдавать ошибку, если это не так.)