球拍嵌套列表和應用功能

Question

我想教自己球拍。我目前正在嘗試編寫一個函數來幫助理解嵌套列表。該函數採用嵌套列表和過程，並將過程應用於每個元素以生成新列表。舉個例子：

(map-tree even? '(1 2 3 4)) => '(#f #t #f #t) 

這裏是我到目前爲止有：

(define (map-tree proc tree) 
    (map-tree-aux tree proc '())) 

(define (map-tree-aux tree proc lst) 
(if (null? tree) 
    lst 
    (if (list? tree) 
     (if (null? (cdr tree)) 
      (if (number? (car tree)) 
        (map-tree-aux (car tree) proc (append-end (proc (car tree)) lst)) 
        (map-tree-aux (car tree) proc lst)) 
      (if (number? (car tree)) 
        (map-tree-aux (cdr tree) proc (append-end (proc (car tree)) (map-tree-aux (car tree) proc lst))) 
        (map-tree-aux (cdr tree) proc lst))) 
     lst))) 

(define (append-end elem lst) 
    (append lst (list elem))) 

雖然這工作與我提供的原來的例子，更復雜的例子出來錯誤：

(map-tree even? '(1 (2 (3 (4))))) should be '(#f (#t (#f (#t)))), but is currently (#f #t #f #t). 

我知道這只是一個問題，在某個地方「列出」，但我有一個問題，找出如何做到這一點。

我首先想到的是如果樹空，(car tree)不是一個數字，但我得到我想要的東西相反（嵌套在相反方向的結果列表）應用程序list向lst。我非常感謝你的幫助。

謝謝！

Answer 1

當遍歷名單列表中，對案件檢查總體思路是：

• 如果列表爲空(null? lst)，做點什麼 ...
• 如果列表中的第一項是原子(not (pair? (car lst)))，做別的事情 ...
• 如果列表中的第一個項目是列表本身(pair? (car lst))，其他 ...

Choosing the right construct也是重要的，即。代替嵌套if陳述，使用cond或match等是優選的。

還可以嘗試並避免在遞歸步驟中使用非常量時間過程（例如append）以提高效率。

---

有了這些想法，一個方法來創建有問題的功能是通過簡單地使用cons打造，同時保留舊的結構，一個新的列表，如下所示：

(define (my-map pred lst) 
    (cond 
    ((null? lst) '()) 
    ((not (pair? (car lst))) 
    (cons (pred (car lst)) 
      (my-map pred (cdr lst)))) 
    (else 
    (cons (my-map pred (car lst)) 
      (my-map pred (cdr lst)))))) 

你可以編寫使用的match代替cond相同的功能：

(define (my-map pred lst) 
    (match lst 
    ['() '()] 
    [(cons (? pair?) b) 
    (cons (my-map pred (car lst)) 
      (my-map pred (cdr lst)))] 
    [(cons a b) 
    (cons (pred (car lst)) 
      (my-map pred (cdr lst)))])) 

您也可以建立一個尾遞歸函數，它牛逼他：

(define (my-map pred lst) 
    (let loop ((lst lst) 
      (acc '())) 
    (cond 
     ((null? lst) 
     (reverse acc)) 
     ((not (pair? (car lst))) 
     (loop (cdr lst) (cons (pred (car lst)) acc))) 
     (else 
     (loop (cdr lst) (cons (loop (car lst) '()) acc)))))) 

注意(reverse acc)在基本情況下返回，因爲建在累加器acc是從原來的列表lst相反的順序列表。爲了避免這種情況，要積累的延續，而不是我們可以修改這個功能：

(define (my-map pred lst) 
    (let loop ((lst lst) 
      (acc identity)) 
    (cond 
     ((null? lst) 
     (acc '())) 
     ((not (pair? (car lst))) 
     (loop (cdr lst) (lambda (r) 
         (acc (cons (pred (car lst)) r))))) 
     (else 
     (loop (cdr lst) 
      (lambda (r) 
       (acc (cons (loop (car lst) identity) r)))))))) 

對於所有的情況，你將有：

(my-map even? '(1 2 3 4 5 7)) 
=> '(#f #t #f #t #f #f) 
(my-map even? '(1 (2 (3 (4 (5 (7))))))) 
=> '(#f (#t (#f (#t (#f (#f))))))