Продолжение Вычисление Выражение Стиля Стиля

Question

Можете ли вы реализовать CPS с помощью выражений вычислений в F #?

Блог Брайана Макнамара дает следующее решение:

type ContinuationBuilder() = 
  member this.Return(x) = (fun k -> k x) 
  member this.ReturnFrom(x) = x 
  member this.Bind(m,f) = (fun k -> m (fun a -> f a k)) 
  member this.Delay(f) = f() 

let cps = ContinuationBuilder()

Выглядит хорошо.Я могу написать List.map в CPS:

let rec mapk f xs = cps {
  match xs with
  | [] -> return []
  | x::xs ->
      let! xs = mapk f xs
      return f x::xs
}

Но переполнение стека:

mapk ((+) 1) [1..1000000] id

Что я делаю не так?

Answer 1

Проблема в том, что ваша Delay функция в компоновщике вычислений немедленно вызывает функцию - это означает, что когда вы вызываете mapk, она немедленно запускает сопоставление с образцом и затем рекурсивно вызывает mapk (перед передачей ее результат операции Bind).

Вы можете исправить это, используя реализацию Delay, которая возвращает функцию, которая вызывает f только после того, как ей дано окончательное продолжение - таким образом, рекурсивный вызов просто вернет функцию (без выполнения более рекурсивных вызовов). которые вызывают переполнение стека):

member this.Delay(f) = (fun k -> f () k)

В этой версии Delay ваш код работает, как и ожидалось.