Lispのネストされたリストの問題

Question

したがって、（入れ子になった '（4 5 2 8））のようなリストを取り、（4（5（）2）8）を返すメソッドを書く必要があります。

私は、これを達成するために3つのサポート方法を書く必要があると考えました。

(define (sizeList L) 
    (if (null? L) 0 
     (+ 1 (sizeList (cdr L))))) 

input : (sizeList '(1 2 3 4 5 6 7)) 
output: 7 

第二リストから要素を削除します：について

(define (remLast E) 
    (if (null? (cdr E)) '() 
     (cons (car E) (remLast (cdr E))))) 

input : (remLast '(1 2 3 4 5 6 7)) 
output: (1 2 3 4 5 6) 

：

(define (drop n L) 
    (if (= (- n 1) 0) L 
     (drop (- n 1) (cdr L)))) 

input : (drop 5 '(1 2 3 4 5 6 7)) 
output: (5 6 7) 

第三は、リストの最後の要素を削除最初は、リストのサイズを取得しますネストされたメソッド私は最初の要素の車を行う必要があると思うし、ドロップで再帰し、最後の要素を削除しますが、私の人生のために私はそれを行う方法や、 p arenthesis？何か案は？

Answer 1

さまざまな再帰的解決が可能ですが、入力リストのサイズの2乗に依存するコストがあるため、直感的なものはパフォーマンスが非常に悪いという問題があります。

例えば、この単純な解決策を検討：

; return a copy of list l without the last element 
(define (butlast l) 
    (cond ((null? l) '()) 
     ((null? (cdr l)) '()) 
     (else (cons (car l) (butlast (cdr l)))))) 

; return the last element of list l 
(define (last l) 
    (cond ((null? l) '()) 
     ((null? (cdr l)) (car l)) 
     (else (last (cdr l))))) 

; nest a linear list 
(define (nested l) 
    (cond ((null? l) '()) 
     ((null? (cdr l)) l) 
     (else (list (car l) (nested (butlast (cdr l))) (last l))))) 

nestedの各再帰呼び出しでは、butlastへの呼び出しとlastへの呼び出しがあります。これはつまり、リストの最初の半分の各要素についてリストを2回スキャンする必要があり、これにはオーダーO（n ）の操作が必要です。

リストのサイズに比例して増加する操作数の再帰的解を見つけることはできますか？答えは「はい」です。この解決方法の鍵は、リストを逆にして、リストとその逆の両方で並行して作業することです。リストの1つの要素を取得し、cdrで1つの要素を取得し、両方のリストの最初の半分が考慮されているときに処理を停止するためにカウンタを同時に使用する。ここでは、このアルゴリズムの可能な実装である：

(define (nested l) 
    (define (aux l lr n) 
    (cond ((= n 0) '()) 
      ((= n 1) (list (car l))) 
      (else (list (car l) (aux (cdr l) (cdr lr) (- n 2)) (car lr))))) 
    (aux l (reverse l) (length l))) 

注パラメータがn(length l)から開始し、各再帰で2だけ減少させること：これは偶数または奇数番号のリストの場合の両方を管理することを可能にします要素。 reverseは、リストを反転させる基本関数ですが、この原始的な機能を使用できない場合は、次のように再帰的なアルゴリズムとそれを実装することができます。

(define (reverse l) 
    (define (aux first-list second-list) 
    (if (null? first-list) 
     second-list 
     (aux (cdr first-list) (cons (car first-list) second-list)))) 
    (aux l '()))