在Scheme中列出元素的出现次数？
如果我可以在命令式语言中使用一个数组，或者在C ++中使用map（tree-structure），那么这非常简单。 在计划中，我不知道如何开始这个想法？ 任何人都可以帮助我吗？
谢谢，
在球拍，你可以做
(count even? '(1 2 3 4)) 但是更严重的是，在Scheme中使用列表来做这件事情要比你提到的要容易得多。 列表或者是空的，或者是一对持有第一个项目和其余的项目。 在代码中遵循这个定义，你会得到它“写出来”。
这里有一个启示 ，基于HtDP （这是一个很好的书来了解这些事情）。 开始只是function“标题” – 它应该收到一个谓词和一个列表：
(define (count what list) ...)
添加input的types – what是一些值， list是一个东西的列表：
;; count : Any List -> Int (define (count what list) ...)
现在，给定list的types，并将list的定义定义为一个空列表或一对两件事物，我们需要检查它是哪一种列表：
;; count : Any List -> Int (define (count what list) (cond [(null? list) ...] [else ...]))
第一种情况应该是显而易见的：空列表中有what项目？
对于第二种情况，你知道这是一个非空的列表，因此你有两个信息：它的头（你first使用的还是car ）和它的尾巴（你得到的是rest还是cdr ）：
;; count : Any List -> Int (define (count what list) (cond [(null? list) ...] [else ... (first list) ... ... (rest list) ...]))
现在你只需要弄清楚如何把这两个信息结合起来就可以得到代码。 最简单的一点信息是：由于（非空）列表的尾部本身就是一个列表，因此可以使用count来计算其中的内容。 因此，你可以进一步得出结论，你应该使用(count what (rest list))在那里。
你的问题是不是很清楚什么是计数。 我会假设你想创build一些元素的频率表。 有几种方法可以解决这个问题。 （如果您使用的是球拍，请向下滚动至我的首选解决scheme的底部。）
便携，纯function，但冗长，缓慢
这种方法使用关联列表（alist）来保存元素及其计数。 对于传入列表中的每个项目，它将在alist中查找该项目，并将其值递增，如果不存在，则将其初始化为1。
(define (bagify lst) (define (exclude alist key) (fold (lambda (ass result) (if (equal? (car ass) key) result (cons ass result))) '() alist)) (fold (lambda (key bag) (cond ((assoc key bag) => (lambda (old) (let ((new (cons key (+ (cdr old) 1)))) (cons new (exclude bag key))))) (else (let ((new (cons key 1))) (cons new bag))))) '() lst))
增量是有趣的部分。 为了实现纯粹的function，我们实际上不能改变alist的任何元素，而是必须排除被改变的关联，然后把结果（用新的值）加到结果上。 例如，如果你有以下的alist：
((foo . 1) (bar . 2) (baz . 2))
并想为baz的价值增加1，你创build一个新的排除baz alist：
((foo . 1) (bar . 2))
然后添加baz的新值：
((baz . 3) (foo . 1) (bar . 2))
第二步是excludefunction，可能是function中最复杂的部分。
便携，简洁，快速但不起作用
更直接的方法是使用哈希表（来自SRFI 69），然后逐个更新列表的每个元素。 由于我们直接更新哈希表，它不是纯粹的function。
(define (bagify lst) (let ((ht (make-hash-table))) (define (process key) (hash-table-update/default! ht key (lambda (x) (+ x 1)) 0)) (for-each process lst) (hash-table->alist ht)))
纯function，简洁，快速，但不可移植
这种方法使用Racket特定的哈希表（与SRFI 69不同），它支持纯function的工作stream程。 作为另一个好处，这个版本也是三者中最简洁的。
(define (bagify lst) (foldl (lambda (key ht) (hash-update ht key add1 0)) #hash() lst))
你甚至可以用这个理解：
(define (bagify lst) (for/fold ((ht #hash())) ((key (in-list lst))) (hash-update ht key add1 0)))
这更像是便携式SRFI 69哈希库的缺点，而不是执行纯function任务的任何特定计划失败。 有了合适的库，这个任务可以轻松实现。
在像Scheme这样的函数式编程语言中，你必须考虑一点点，并利用列表的构造方式。 不是通过递增索引遍历列表，而是recursion地遍历列表。 你可以用car （单个元素）删除列表的头部，你可以用cdr （列表本身）获得尾部，你可以用cons将头部和尾部粘在一起。 你的函数的大纲是这样的：
- 您必须将您正在search的元素和当前计数“传递”给函数的每个调用
- 如果你点击空列表，你可以完成列表，你可以输出结果
- 如果列表中的汽车等于您正在查找的元素，请使用列表的cdrrecursion调用该函数，并使用counter + 1
- 如果不是，则使用列表的cdr和与之前相同的计数器值recursion调用该函数
在Scheme中，通常使用关联列表作为O（n）穷人的散列表/字典。 唯一剩下的问题是如何更新关联的元素。
