StackOverflow в продолжении монады

Используя следующую монаду продолжения:

type ContinuationMonad() =
    member this.Bind (m, f) = fun c -> m (fun a -> f a c)
    member this.Return x = fun k -> k x

let cont = ContinuationMonad()

Я не понимаю, почему следующее дает мне переполнение стека:

let map f xs =
    let rec map xs =
        cont {
            match xs with
            | [] -> return []
            | x :: xs ->
                let! xs = map xs
                return f x :: xs
        }
    map xs id;;

let q = [1..100000] |> map ((+) 1)

Пока следующее:

let map f xs =
    let rec map xs =
        cont {
            match xs with
            | [] -> return []
            | x :: xs ->
                let! v = fun g -> g(f x)
                let! xs = map xs
                return v :: xs
        }
    map xs id;;

let q = [1..100000] |> map ((+) 1)

Ответы

Ответ 1

Чтобы исправить ваш пример, добавьте этот метод в свое определение монады:

member this.Delay(mk) = fun c -> mk () c

По-видимому, часть, которая переполняется, является уничтожением большого входного списка в рекурсивном вызове map. Отсрочка этого решения решает проблему.

Обратите внимание, что вторая версия помещает рекурсивный вызов map за другой let!, который помещает на Bind и дополнительную лямбду, фактически задерживая рекурсивный вызов map.

Мне пришлось преследовать несколько ложных следов, прежде чем прийти к такому выводу. Что помогло наблюдать, что StackOverflow также выбрано OCaml (хотя и при более высоком N), если рекурсивный вызов не задерживается. В то время как F# TCO имеет некоторые причуды, OCaml более доказана, поэтому это убедило меня в том, что проблема действительно связана с кодом, а не с компилятором:

let cReturn x = fun k -> k x
let cBind m f = fun c -> m (fun a -> f a c)

let map f xs =
  (* inner map loop overflows trying to pattern-match long lists *)
  let rec map xs =
    match xs with
      | [] -> cReturn []
      | x :: xs ->
        cBind (map xs) (fun xs -> cReturn (f x :: xs)) in
  map xs (fun x -> x)

let map_fixed f xs =
  (* works without overflowing by delaying the recursive call *)
  let rec map xs =
    match xs with
      | [] -> cReturn []
      | x :: xs ->
        cBind (fun c -> map xs c) (fun xs -> cReturn (f x :: xs)) in
  map xs (fun x -> x)

let map_fused f xs =
  (* manually fused version avoids the problem by tail-calling `map` *)
  let rec map xs k =
    match xs with
      | [] -> k []
      | x :: xs ->
        map xs (fun xs -> k (f x :: xs)) in
  map xs (fun x -> x)

Ответ 2

Компилятор F # иногда не очень умный - в первом случае он вычисляет map xs, затем f x, а затем объединяет их, поэтому map xs не находится в позиции хвоста. Во втором случае он может легко изменить порядок map xs в положении хвоста.