深度列表

Question

我試圖找到列表中的每個元素的深度，同時創造一個扁平的輸出與它們的深度級別寫的輸出原子，到目前爲止，我想出了下面的邏輯 -

(define nestingDepth 
(lambda (lst1) 
    (cond ((null? lst1) 1) 
      ((list? (car lst1)) 
      (cons(+ 1(nestingDepth (car lst1)))) (nestingDepth (cdr lst1)))   
      ((null? (cdr lst1)) (cons (1 (cdr lst1))) (nestingDepth (cdr lst1)))))) 

但是這不是輸出中的任何內容。請更新我出錯的地方。 預期結果將類似於 - 輸入 - 「（A（B）C） 輸出 - （1 A 2 B 1 C）

Answer 1

由於一些其他的答案也提到，這是非常重要的確保每個案件退回正確類型的東西。如果輸入是空列表，那麼輸出應該是空列表。如果輸入是一對，那麼你需要處理汽車和對的cdr並連接它們。如果輸入既不是空列表也不是一對，那麼結果就是深度和輸入的列表。

現在，增量式構建結果可能會很方便。您可以向左向右打造，並使用類似下面的方法添加的每個元素和它的深度：

(define (depths tree) 
    (let depths ((tree tree) 
       (depth 0) 
       (results '())) 
    (cond 
     ((null? tree) results) 
     ((pair? tree) (depths (car tree) 
          (+ 1 depth) 
          (depths (cdr tree) 
            depth 
            results))) 
     (else (cons depth (cons tree results)))))) 

> (depths '(a ((b) c ((d))) e)) 
(1 a 3 b 2 c 4 d 1 e) 

Answer 2

這裏是一個可能的解決方案（我已經改變了輸出格式稍微使溶液更容易編碼）。 append-map在SRFI 1中定義。

(define (depths x) 
    (cond ((list? x) 
     (append-map (lambda (y) 
         (map (lambda (z) 
           (cons (car z) (+ (cdr z) 1))) 
          (depths y))) 
        x)) 
     (else `((,x . 0))))) 

（我寫的是一個經驗豐富的策士會寫它，而不是有人會寫家庭作業。如果這是你的情況，請理解我的代碼做什麼，然後再形成一些功課可接受的代碼）

Answer 3

基本情況是錯誤的（如果您打算輸出列表作爲結果，則不能返回1），遞歸的高級方式不會構建列表作爲輸出...完整的重寫是需要;下面的解決方案是便攜式的，應該在任何Scheme解釋工作，僅利用的基本程序：

(define (nestingDepth lst) 
    (let depth ((lst lst) (n 1)) 
    (cond ((null? lst) '()) 
      ((not (pair? (car lst))) 
      (cons n 
       (cons (car lst) 
         (depth (cdr lst) n)))) 
      (else 
      (append (depth (car lst) (+ 1 n)) 
        (depth (cdr lst) n)))))) 

如預期的輸出：

(nestingDepth '(a (b (c (d e))) f g)) 
=> '(1 a 2 b 3 c 4 d 4 e 1 f 1 g) 

Answer 4

所有以前的解決方案進行適當的（嵌套）名單運作良好，對於那些爲不正確名單工作的人，我不確定他們是否正確。

例如，(depths '(a . b))爲Joshua's生成(1 a 0 b)，爲Chris'生成(((a . b) . 0))，但我應該說它應該是(1 a 1 b)。

我因此去

(define (depths sxp) 
    (let loop ((sxp sxp) (res null) (level (if (cons? sxp) 1 0))) 
    (cond 
     ((null? sxp) res) 
     ((pair? sxp) (let ((ca (car sxp))) 
        (loop ca 
          (loop (cdr sxp) res level) 
          (if (pair? ca) (add1 level) level)))) 
     (else  (cons level (cons sxp res)))))) 

和我的測試情況是：

(check-equal? (depths '(a . b)) '(1 a 1 b)) 
(check-equal? (depths 'a) '(0 a)) ; 0 
(check-equal? (depths '(a)) '(1 a)) 
(check-equal? (depths '(a a)) '(1 a 1 a)) 
(check-equal? (depths '(a (b . c) d (e (f (g h . i) . j)))) '(1 a 2 b 2 c 1 d 2 e 3 f 4 g 4 h 4 i 3 j)) 

(check-equal? (depths '(a (b) c)) '(1 a 2 b 1 c)) 
(check-equal? (depths '(a ((b) c ((d))) e)) '(1 a 3 b 2 c 4 d 1 e)) 
(check-equal? (depths '(a (b (c (d e))) f g)) '(1 a 2 b 3 c 4 d 4 e 1 f 1 g))