在方案中计算嵌套列表中原子的出现次数

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。