Scheme / Racket에서 꼬리 재귀를 사용하여 추가 절차를 구현하는 방법은 무엇입니까? [복제]

Question

오랫동안 나는 꼬리 재귀 (반복)를 사용하여 Racket에서 추가 절차를 구현하려고 노력하고 있습니다.

지금까지 내가 한 최고의 솔루션은 다음과 같습니다.

(define (my-reverse lst)
  (define (iter lst reversed)
    (if (null? lst)
        reversed
        (iter (cdr lst) (cons (car lst) reversed))))
  (iter lst '()))

(define (append-iter el lst)
  (my-reverse (cons el (my-reverse lst))))

(append-iter 4 '(1 2 3)) ; (1 2 3 4)

내 질문은 더 나은 구현 방법이 있는지 여부입니다.

Answer 1

글쎄, 그것은 "better"에 대한 당신의 정의에 달려 있습니다. :). 솔루션은 간단하며 꼬리 재귀를 사용하여 목록 끝에 요소를 추가하는 자체 프로 시저를 작성하는 더 간단한 방법을 찾을 수 없습니다.

내 유일한 코멘트는 my-reverse내장 reverse프로 시저 와 동일한 작업을 수행 한다는 것입니다. 가장 확실하게 꼬리 재귀 적이므로 다음과 같이 간단히 작성할 수 있습니다.

(define (append-iter el lst)
  (reverse (cons el (reverse lst))))

연속 전달 스타일 을 사용하는 것이 괜찮다 면 다음 솔루션도 꼬리 재귀 적이며 가장 기본적인 기본 절차에만 의존합니다.

(define (append-iter el lst)
  (append-cps lst (cons el '()) (lambda (x) x)))

(define (append-cps lst1 lst2 k)
  (if (null? lst1)
      (k lst2)
      (append-cps
       (cdr lst1)
       lst2
       (lambda (appended-cdr)
         (k (cons (car lst1) appended-cdr))))))

어느 쪽이든 예상대로 작동합니다.

(append-iter 4 '(1 2 3))
=> '(1 2 3 4)

궁금한 점이 있다면 CPS 솔루션이 아래 표시된 것과 같은 식으로 평가되어 자연스럽게 답을 얻을 수 있습니다.

((lambda (append-cdr)
   ((lambda (appended-cdr)
      ((lambda (appended-cdr)
         ((lambda (x) x)
          (cons 1 appended-cdr)))
       (cons 2 appended-cdr)))
    (cons 3 append-cdr)))
 '(4))
=> '(1 2 3 4)

Answer 2

예,

(define (rev-append lst reversed)
    (if (null? lst)
        reversed
        (rev-append (cdr lst) 
                    (cons (car lst) reversed))))

(define (append-iter el lst)
  (rev-append (rev-append lst '()) 
              (cons el '())))

약간 "더 좋음"입니다.

rev-append귀하 my-reverse의 것 iter입니다. 자체 최고 수준의 바인딩이 필요합니다.