Как достичь хвостовой рекурсии в функциональных программах

Question

Возьмет, к примеру, следующая наивная реализация правой складки на схеме:

(define (fold-rite kons knil clist) 
    (if (null? clist) 
    knil 
    (kons (car clist) (fold-rite kons knil (cdr clist))))) 

Это, очевидно, не является кандидатом для устранения хвостового вызова с рекурсивным вызовом fold-rite должен завершиться до вызова kons. Теперь, я мог бы быть немного умное и использовать продолжающее прохождение стиля вместо:

(define (fold-rite-cps kons knil clist kontinuation) 
    (if (null? clist) 
    (kontinuation knil) 
    (fold-rite-cps kons knil (cdr clist) 
     (lambda (x) (kontinuation (kons (car clist) x)))))) 

Теперь fold-rite-cps является хвостовой рекурсией, но промежуточные продолжения, построенных во время рекурсии все равно должны храниться где-то. Поэтому, хотя я не могу сдуть стек, я все еще использую примерно столько же памяти, как и в первой версии, и почему-то я чувствую, что сначала собирать массивную кучу продолжений, а затем распутывать их всего одним махом плохой для производительности, хотя вторая версия была на самом деле значительно быстрее на моей машине.

Но если левая складка может работать в постоянном пространстве (за вычетом накопленного значения), а правая справка в списке такая же, как у левой складки на обратном пути, то я полагаю, что должен быть способ реализовать хвостовая рекурсивная правая сфера, которая также может работать в постоянном пространстве. Если да, то как мне это сделать? Получив еще более общую информацию о том, какие способы сделать рекурсивную функцию без хвоста в хвост-рекурсивную, желательно ту, которая может работать в постоянном пространстве (предполагая, что явный цикл может быть написан на императивном языке, который также работает в постоянном пространство)? Я сделал какие-то неправильные предположения?

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

Answer 1

Основываясь на комментариях выше, я думаю, что наилучший ответ без изменения структур данных (cons cells) будет следующим: (в общем, lisp, потому что это то, что мне было удобно).

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

(defun foldl (op clist &optional base) 
    (if (null clist) 
     base 
     (foldl op (cdr clist) 
      (funcall op (car clist) base)))) 

(defun foldr (op clist &optional base) 
    ;; reverse the list then fold it 
    (foldl op (foldl #'cons clist nil) base)) 

Для прямого ответа: Нет, это не представляется возможным foldr в постоянном пространстве, так как единая связанная природа минусах клеток требует полного списка обхода для достижения последнего элемента, а затем разматывания шаг или отдельный список для отслеживания фактической операции сгиба.