9

リストに要素を実装appendする例をいくつか見てきましたが、すべて末尾再帰を使用していません。そのような機能を機能的なスタイルで実装する方法は?

 (define (append-list lst elem)
    expr)
4

5 に答える 5

7

以下は、末尾再帰モジュロ コンス最適化の実装であり、完全な末尾再帰コードになります。入力構造をコピーし、新しい要素をミューテーションによってトップダウン方式で追加します。このミューテーションは内部の新しく作成されたデータに対して行われるため、外部では引き続き機能します (渡されたデータは変更されず、結果を生成する以外に目に見える影響はありません)。

(define (add-elt lst elt)
  (let ((result (list 1)))
    (let loop ((p result) (lst lst))
      (cond 
        ((null? lst) 
           (set-cdr! p (list elt)) 
           (cdr result))
        (else 
           (set-cdr! p (list (car lst)))
           (loop (cdr p) (cdr lst)))))))

私は "head-sentinel" トリックを使用するのが好きです。これにより、余分なコンス セルが 1 つ割り当てられるだけで、コードが大幅に簡素化されます。

このコードは、低レベルのミューテーション プリミティブを使用して、一部の言語 (Prolog など) でコンパイラによって自動的に行われることを実現します。TRMC 最適化の仮想スキームでは、次の末尾再帰モジュロ コンスコードを記述し、コンパイラに自動的に上記のコードと同等のコードに変換させることができます。

(define (append-elt lst elt)              ;; %% in Prolog:
  (if (null lst)                          ;; app1( [],   E,R) :- Z=[X].
    (list elt)                            ;; app1( [A|D],E,R) :-
    (cons (car lst)                       ;;  R = [A|T], % cons _before_
          (append-elt (cdr lst) elt))))   ;;  app1( D,E,T). % tail call

cons操作append-elt がない場合は、末尾再帰になります。ここで、TRMC 最適化の出番です。

2021 更新:もちろん、末尾再帰関数を持つことの全体的なポイントは、ループを表現することです (関数型スタイルで、はい)。例として、Common Lisp (CLISP 実装) では、ループ式

(loop for x in '(1 2) appending (list x))

(これは、独自の非常に具体的な方法で機能しない場合でも、高レベルの仕様のようなものです) は、同じ末尾のコンス セルの追跡および変更スタイルに変換されます。

[20]> (macroexpand '(loop for x in '(1 2) appending (list x)))
(MACROLET ((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-ERROR)))
 (BLOCK NIL
  (LET ((#:G3047 '(1 2)))
   (PROGN
    (LET ((X NIL))
     (LET ((#:ACCULIST-VAR-30483049 NIL) (#:ACCULIST-VAR-3048 NIL))
      (MACROLET ((LOOP-FINISH NIL '(GO SYSTEM::END-LOOP)))
       (TAGBODY SYSTEM::BEGIN-LOOP (WHEN (ENDP #:G3047) (LOOP-FINISH))
        (SETQ X (CAR #:G3047))
        (PROGN
         (LET ((#:G3050 (COPY-LIST (LIST X))))
          (IF #:ACCULIST-VAR-3048
           (SETF #:ACCULIST-VAR-30483049
            (LAST (RPLACD #:ACCULIST-VAR-30483049 #:G3050)))
           (SETF #:ACCULIST-VAR-30483049
            (LAST (SETF #:ACCULIST-VAR-3048 #:G3050))))))
        (PSETQ #:G3047 (CDR #:G3047)) (GO SYSTEM::BEGIN-LOOP) SYSTEM::END-LOOP
        (MACROLET
         ((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-WARN) '(GO SYSTEM::END-LOOP)))
         (RETURN-FROM NIL #:ACCULIST-VAR-3048)))))))))) ;
T
[21]>

(すべての構造変更プリミティブの母は と綴られていますR.P.L.A.C.D.) したがって、これは実際に似たようなことを行う Lisp システム (Prolog だけでなく) の 1 つの例です。

于 2012-11-06T17:52:35.973 に答える
5

末尾再帰プロシージャを作成することは可能です...append-element

(define (append-element lst ele)
  (let loop ((lst (reverse lst))
             (acc (list ele)))
    (if (null? lst)
        acc
        (loop (cdr lst) (cons (car lst) acc)))))

reverse...しかし、それは（適切な測定のために）投入されたものではより非効率的です。最初にリストを逆にすることなく、このプロシージャを末尾再帰として記述する別の機能的な方法（たとえば、入力リストを変更しない）を考えることはできません。

質問に対する機能しない回答については、@WillNessが内部リストを変更する優れたSchemeソリューションを提供しました。

于 2012-11-06T17:17:10.860 に答える
3

これは、継続を使用した機能的な末尾再帰の append-elt です。

(define (cont-append-elt lst elt)
  (let cont-loop ((lst lst)
                  (cont values))
    (if (null? lst)
        (cont (cons elt '()))
        (cont-loop (cdr lst)
                   (lambda (x) (cont (cons (car lst) x)))))))

パフォーマンスに関しては、ラケットとガンビットでのウィルの突然変異に近いですが、イカルスとチキンオスカーの逆の方が優れていました. ただし、ミューテーションは常に最高のパフォーマーでした。ただし、私はこれを使用しませんでしたが、純粋に読みやすいという理由で、オスカーのエントリのわずかなバージョンです.

(define (reverse-append-elt lst elt)
  (reverse (cons elt (reverse lst))))

そして、パフォーマンスの変化が必要な場合は、次のようにします。

(define (reverse!-append-elt lst elt)
  (let ((lst (cons elt (reverse lst))))
     (reverse! lst)
     lst))
于 2013-07-20T21:38:57.713 に答える
2

素朴に言うことはできませんが、TCMCを提供する実装も参照してください-末尾呼び出しモジュロ短所。それが可能になります

(cons head TAIL-EXPR)

TAIL-EXPR短所自体が末尾呼び出しの場合は末尾呼び出しします。

于 2012-11-06T18:12:36.123 に答える
1

これはSchemeではなくLispですが、次のように翻訳できると確信しています。

(defun append-tail-recursive (list tail)
  (labels ((atr (rest ret last)
             (if rest
                 (atr (cdr rest) ret
                      (setf (cdr last) (list (car rest))))
                 (progn
                   (setf (cdr last) tail)
                   ret))))
    (if list
        (let ((new (list (car list))))
          (atr (cdr list) new new))
        tail)))

リターンリストの先頭と末尾を保持し、リスト引数をトラバースするときに末尾を変更します。

于 2012-11-06T17:40:54.553 に答える