在方案中計算嵌套列表中原子的出現次數

Question

您好，我是Scheme的新成員。

我在網上閱讀教程，我不知道如何計算Scheme中嵌套列表中原子的出現次數。我發現一些教程提及bagify和flatten;我試圖混合他們，但我得到了一個錯誤。什麼可能是錯的？

下面的代碼：

(define (bagify lst) 
    (foldl (lambda (key ht) 
     (hash-update ht key add1 0)) 
     #hash() lst)) 

(define (flatten mylist) 
    (cond ((null? mylist) '()) 
     ((list? (car mylist)) (append (flatten (car mylist)) (flatten (cdr mylist)))) 
     (else (cons (car mylist) (flatten (cdr mylist))) (bagify(mylist))))) 

Answer 1

我覺得bagify和flatten對於這類問題薰鯡魚。當然，你可以使用flatten，然後計算結果拼合列表中的出現次數。但是，僅僅遍歷嵌套列表會更加高效和直接。

爲了簡單起見，我們首先實現非嵌套情況下的函數。下面是計算的'?出現一個版本，甚至更簡單：

(define count-?s 
    (lambda (ls) 
    (cond 
     [(null? ls) 0] 
     [(eq? (car ls) '?) (add1 (count-?s (cdr ls)))] 
     [else (count-?s (cdr ls))]))) 

改變這種對嵌套列表只需要添加一個cond線上工作。您發現的flatten的實現包含一個提示：我們希望檢查遞歸的每一步是否列表的car本身是一個列表（但是，使用list?比我們需要的功率更大;我們可以使用pair?代替只要我們的輸入總是一個適當的嵌套列表）。

一旦我們知道car也是一個（可能嵌套的）列表，我們需要將它傳遞給一個知道如何處理列表的函數。幸運的是，我們正在定義一個！

(define count-?s* 
    (lambda (ls) 
    (cond 
     [(null? ls) 0] 
     [(pair? (car ls)) (+ (count-?s* (car ls)) (count-?s* (cdr ls)))] 
     [(eq? (car ls) '?) (add1 (count-?s* (cdr ls)))] 
     [else (count-?s* (cdr ls))]))) 

這就是它的全部。很少涉及到，不是嗎？這麼少，事實上，你可以只更換一對夫婦的表情和風能與做某事嵌套列表完全不同的功能：

(define remove-?s* 
    (lambda (ls) 
    (cond 
     [(null? ls) '()] 
     [(pair? (car ls)) (cons (remove-?s* (car ls)) (remove-?s* (cdr ls)))] 
     [(eq? (car ls) '?) (remove-?s* (cdr ls))] 
     [else (cons (car ls) (remove-?s* (cdr ls)))]))) 

求解嵌套列表的一個問題是很容易的，一旦你」已經解決了它的平面列表。

1. 從平面列表解決方案開始。
2. 檢查car中的一對。
3. 對car和cdr都進行自然遞歸。
4. 合併的答案與二元運算有意義與null?殼體的左側，例如，+/0，*/1，cons/'()，and/#t，or/#f。