Я работаю над расширением camlp4 для haskell-подобных нотации в Ocaml и пытаюсь выяснить, как GHC компилирует рекурсивные do-bindings (включенные с -XDoRec).
Интересно, возможно ли, чтобы монадический комбинатор фиксированных точек существовал в строгом языке (например, Ocaml/F #/SML/...)?
Если да, как это может выглядеть? Было бы очень полезно?
MonadFix на строгом языке
Ответ 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 выше.