Как я могу сделать эту функцию хвостовой рекурсивной?

Question

Я все еще пытаюсь реализовать 2-3 пальца, и я добился хорошего прогресса ( хранилище). Делая некоторые тесты, я обнаружил, что мой довольно простой toList приводит к StackruException когда дерево довольно большое. Сначала я увидел легкое исправление и сделал его рекурсивным.

К сожалению, оказалось, что toList не был виновником, но viewr было:

/// Return both the right-most element and the remaining tree (lazily).
let rec viewr<'a> : FingerTree<'a> -> View<'a> = function
    | Empty -> Nil
    | Single x -> View(x, lazyval Empty)
    | Deep(prefix, deeper, One x) ->
        let rest = lazy (
            match viewr deeper.Value with
            | Nil ->
                prefix |> Digit.promote
            | View (node, lazyRest) ->
                let suffix = node |> Node.toList |> Digit.ofList
                Deep(prefix, lazyRest, suffix)
        )
        View(x, rest)
    | Deep(prefix, deeper, Digit.SplitLast(shorter, x)) ->
        View(x, lazy Deep(prefix, deeper, shorter))
    | _ -> failwith Messages.patternMatchImpossible

В поисках единственного рекурсивного вызова очевидно, что это не хвостовая рекурсия. Каким-то образом я надеялся, что эта проблема не будет существовать, потому что этот вызов обернут в Lazy ИМХО которое похоже на продолжение.

Я слышал и читал о продолжениях, но до сих пор никогда (не должен) использовать (d) их. Я думаю, здесь мне действительно нужно. Я довольно долго смотрю на код, выставляю параметры функций здесь и там, вызываю их в других местах... Я полностью потерян!

Как это может быть сделано?

---

Обновление: код вызова выглядит следующим образом:

/// Convert a tree to a list (left to right).
let toList tree =
    let rec toList acc tree =
        match viewr tree with
        | Nil -> acc
        | View(head, Lazy tail) -> tail |> toList (head::acc)
    toList [] tree

---

Обновление 2: этот код вызвал сбой.

let tree = seq {1..200000} |> ConcatDeque.ofSeq
let back = tree |> ConcatDeque.toList

Дерево построено нормально, я проверил, и оно всего 12 уровней. Это вызов в строке 2, который вызвал переполнение.

---

Обновление 3: kvb был прав, проблема с каналом, с которой я столкнулся прежде, как-то связана с этим. Повторное тестирование перекрестного продукта отладки / выпуска и с / без канала работало во всех случаях, кроме одного: произошел сбой в режиме отладки с оператором канала. Поведение было таким же для 32 против 64 бит.

Я совершенно уверен, что при публикации вопроса я использовал режим релиза, но сегодня он работает. Может быть, был какой-то другой фактор... Извините за это.

---

Хотя крах решен, я оставляю вопрос открытым из теоретического интереса. В конце концов, мы здесь, чтобы учиться, не так ли?

Итак, позвольте мне адаптировать вопрос:
Смотря на код, viewr определенно не хвостовая рекурсия. Почему он не всегда взрывается и как его переписать, используя продолжения?

Answer 1

Призвание viewr никогда не приводит к немедленному рекурсивному вызову viewr (рекурсивный вызов защищен lazy и не принуждается в течение оставшейся части звонка viewr), поэтому нет необходимости делать его хвостовым рекурсивным, чтобы предотвратить рост стека без ограничений. То есть призыв к viewr создает новый кадр стека, который сразу же выталкивается, когда viewrработа сделана; вызывающая сторона может затем принудительно вызвать ленивое значение, в результате чего создается новый кадр стека для вложенного viewr вызов, который затем сразу же выталкивается снова и т. д., поэтому повторение этого процесса не приводит к переполнению стека.