Большое спасибо за просмотр этого Томаса. Однако, как говорит kvb, это вызывает немного больше вопросов, чем ответов. В частности, есть ли что-то в выражениях вычислений, из-за которых компилятор теряет "хвостовую рекурсивность" функций, написанных с использованием bind, если bind не записан в стиле передачи продолжения? Значит ли это, что любой построитель вычислений в реальном мире должен проходить мимо?
ытие: это появилось в FsCheck, среде случайного тестирования F #, которую я поддерживаю. У меня есть решение, но оно мне не нравится. Более того, я не понимаю проблемы - ее просто обошли.
Довольно стандартная реализация последовательности (монадическая, если мы собираемся использовать большие слова):
let sequence l =
let k m m' = gen { let! x = m
let! xs = m'
return (x::xs) }
List.foldBack k l (gen { return [] })
Где gen может быть заменен выбранным компоновщиком вычислений. К сожалению, эта реализация потребляет пространство стека, и поэтому в конечном итоге переполнение стека, если список достаточно длинный. Я в принципе знаю, что foldBack не является хвостовой рекурсией, но умные кролики команды F # обошли это в реализации foldBack. Есть ли проблема в реализации компоновщика вычислений?
Если я изменю реализацию на нижеприведенную, все будет хорошо:
let sequence l =
let rec go gs acc size r0 =
match gs with
| [] -> List.rev acc
| (Gen g)::gs' ->
let r1,r2 = split r0
let y = g size r1
go gs' (y::acc) size r2
Gen(fun n r -> go l [] n r)
Для полноты можно найти тип Gen и конструктор вычисленийв источнике FsCheck