5

cons、first、rest、empty? などの基本的な操作のみを使用してリストを逆にする方法を考えていました。

ヘルパー関数やアキュムレータは許可されておらず、関数は 1 つの入力 (リスト) のみを受け取ります。

頭を包むことはできませんが、可能だと言われました。

これが私がこれまで考えてきたことです。リストの残りの再帰を形成する方法がわかりません。

(defunc rev-list (x)
  (if (or (equal (len x) 0) (equal (len x) 1))
      x
      (cons (first (rev-list (rest x)))
            ???)))

リストの最初と最後を交換する関数で同様のことを行うことは明らかに可能ですが、私もそれを完全には理解していません。そのコードは次のとおりです。

(define swap-ends (x)
  (if (or (equal (len x) 0) (equal (len x) 1))
      x
      (cons (first (swap-ends (rest x))) 
            (swap-ends (cons (first x) 
                             (rest (swap-ends (rest x))))))))
4

3 に答える 3

5

(注: 答えはこの投稿の最後にあります) 2 番目の関数、

(define (swap-ends x)                                   ; swap [] = []
  (if (or (equal (length x) 0) (equal (length x) 1))    ; swap [x] = [x]
      x                                                 ; swap (x:xs) 
      (cons (first (swap-ends (rest x)))                ;    | (a:b) <- swap xs 
            (swap-ends (cons (first x)                  ;    = a : swap (x : b)
                             (rest (swap-ends (rest x))))))))

(コメントに Haskell の翻訳付き) それは何をするのですか? ifの代替句のデータ フロー図は次のとおりです。

                   /-> first ----------------------> cons
x --> first ------/-------------> cons --> swap --/
  \-> rest -> swap ---> rest ---/

(矢印に従って左から右へ)。そう、

[] -> []
[1] -> [1]
                     /-> 2 -----------------------> [2,1]
[1,2] --> 1 --------/------------> [1] --> [1] --/
      \-> [2] -> [2] ---> [] ---/

                           /-> 3 -------------------------> [3,2,1]
[1,2,3] --> 1 ------------/----------> [1,2] --> [2,1] --/
        \-> [2,3] -> [3,2] -> [2] --/

                             /-----> 4 ----------------------------> [4,2,3,1]
[1,2,3,4] --> 1 ------------/---------------> [1,3,2] -> [2,3,1] -/
          \-> [2,3,4] -> [4,3,2] -> [3,2] -/

これまでのところ、実際にリストの最後の要素を交換しています。自然帰納法で証明してみよう

true(N-1) => true(N):

                       /-> N --------------------------------------> [N,2..N-1,1]
[1..N] --> 1 ---------/-----------> [1,3..N-1,2] -> [2,3..N-1,1] -/
       \-> [2..N] -> [N,3..N-1,2]   /
                    -> [3..N-1,2] -/

それで証明されています。したがって、(N-1) の長さのリストを逆にするという仮定の下で、N の長さのリストを逆にするデータ フロー図を考案する必要があります。

[1..N] --> 1 ------------------------------------\
       \-> [2..N] -> [N,N-1..2] -> N -------------\------------------\
                     \-> [N-1,N-2..2] -> [2..N-1] -> [1..N-1] -> rev -> cons

これにより、実装が得られます

(define (rev ls)                                 ; rev [] = []
  (cond                                          ; rev [x] = [x]
    ((null? ls) ls)                              ; rev (x:xs) 
    ((null? (rest ls)) ls)                       ;   | (a:b) <- rev xs 
    (else                                        ;   = a : rev (x : rev b)
      (cons (first (rev (rest ls)))
            (rev (cons (first ls)
                       (rev (rest (rev (rest ls))))))))))

(rev '(1 2 3 4 5))     ; testing
;Value 13: (5 4 3 2 1)

コメント内の Haskell の翻訳は、非常に自然に図に従っています。それは実際に読み取り可能です:aは最後の要素でbあり、反転された「コア」(つまり、最初と最後の要素のない入力リスト) であるため、反転されたコアを反転し、最初の要素を付加して入力リストの最後の部分を取得します。それを逆にして、最後の要素を先頭に追加します。単純。:)

2020 更新:これは@Rördのコメントからのコードに基づくスキーム バージョンで、同様に読みやすく、Haskell のパターン マッチングの代わりに引数が分解されます。

(define (bind lst fun)
  (apply fun lst))

(define (rev lst)
  (if (or (null? lst)
          (null? (cdr lst)))
    lst
    (bind lst
      (lambda (first . rest)
         (bind (rev rest)
           (lambda (last . revd-core)
              (cons last (rev (cons first (rev revd-core))))))))))
于 2013-10-23T08:38:23.667 に答える
2 
(define (reverse x)
  (let loop ((x x) (y '()))
    (if (null? x)
        y
        (let ((temp (cdr x)))
          (set-cdr! x y)
          (loop temp x))))))

それを効率的に行う数少ない方法の 1 つです。しかし、まだ一種のヘルパー プロシージャです。

別の方法ですが、末尾再帰ではなく、追加で set-cdr を使用しない場合は! 大きなリストには本当に使えません。

(define (reverse L)
  (if (null? l)
      '()
       (append (reverse (cdr L)) (list (car L)))))
于 2013-10-23T02:54:51.770 に答える