MonadFix на строгом языке

Question

Я работаю над расширением camlp4 для haskell-подобной записи do в Ocaml и пытаюсь выяснить, как GHC компилирует рекурсивные привязки do (включается с -XDoRec).
Интересно, возможно ли существование монадического комбинатора с фиксированной точкой на строгом языке (например, Ocaml/F#/SML/...)?
Если да, как это может выглядеть? Это было бы очень полезно?

Answer 1

Синтаксис выражения вычисления F# (относится к Haskell do) поддерживает рекурсию:

let rec ones = seq {
  yield 1
  yield! ones }

Это поддерживается, потому что построитель вычислений должен поддерживать Delay операция в дополнение к другим монадическим (или MonadPlus) операциям. Код переводится в нечто вроде:

let rec ones = 
  seq.Combine
    ( seq.Yield(1),
      seq.Delay(fun () -> seq.YieldFrom(ones)) )

Тип Delay в общем, (unit -> M<'T>) -> M<'T> и хитрость заключается в том, что он оборачивает вычисление с эффектами (или немедленной рекурсивной ссылкой) в отложенное вычисление, которое оценивается по требованию.

Если вы хотите узнать больше о том, как этот механизм работает в F#, тогда уместны следующие две статьи:

• Синтаксические вопросы: написание абстрактных вычислений на F#
• Инициализация ссылочных абстрактных объектов: вызов рекурсии стоимости

Первый описывает, как синтаксис выражения вычисления F# обессилен (и как Delay вставляется - и вообще, как F# сочетает отложенные и энергичные вычисления с эффектами), а второй описывает, как F# обрабатывает let rec объявления со значениями - как ones значение выше.