计算Scheme中列表中元素的出现？

Question

例如，如果我可以使用命令式语言的数组或C ++中的map（树结构），则这非常容易。在计划中，我不知道如何开始这个想法？谁可以帮我这个事？

Answer 1

您的问题不是很具体，关于所计算的内容。我假设您要创建某种形式的元素频率表。有几种方法可以解决此问题。（如果您使用的是Racket，请向下滚动至底部以找到我的首选解决方案。）便携式，纯功能，但冗长且缓慢此方法使用关联列表（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))递增是有趣的部分。为了实现纯功能，我们实际上不能更改alist的任何元素，而是必须排除要更改的关联，然后将该关联（带有新值）添加到结果中。例如，如果您具有以下列表：((foo . 1) (bar . 2) (baz . 2))并想在baz的值上加1 ，则创建一个新的列表，该列表不包括baz：((foo . 1) (bar . 2))然后添加baz的新值：((baz . 3) (foo . 1) (bar . 2))第二步是exclude函数的功能，并且可能是函数中最复杂的部分。便携式，简洁，快速但无功能一种更直接的方法是使用哈希表（来自SRFI 69），然后针对列表中的每个元素逐一对其进行更新。由于我们直接更新哈希表，因此它不是纯粹的功能。(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)))纯功能，简洁，快速但不可携带此方法使用特定于球拍的哈希表（与SRFI 69的哈希表不同），该哈希表确实支持纯功能的工作流程。另一个好处是，该版本也是三个版本中最简洁的版本。(define (bagify lst)  (foldl (lambda (key ht)           (hash-update ht key add1 0))         #hash() lst))您甚至可以for对此进行理解：(define (bagify lst)  (for/fold ((ht #hash()))            ((key (in-list lst)))    (hash-update ht key add1 0)))这比可移植SRFI 69哈希库的缺点更能说明问题，而不是Scheme的任何特定失败都无法完成纯功能任务。使用正确的库，可以轻松且功能上地实现此任务。

Answer 2

在像Scheme这样的函数式编程语言中，您必须有所不同，并利用构造列表的方式。无需通过增加索引来遍历列表，而是递归地遍历列表。您可以使用car（单个元素）删除列表的头部，可以使用cdr（列表本身）获取列表的尾部，并且可以将头部和其尾部粘合在一起cons。您的功能概述如下：您必须“递归”要搜索的元素以及该函数每次调用的当前计数如果您击中空白列表，则列表已完成，您可以输出结果如果列表中的汽车等于您要查找的元素，请使用列表的cdr和计数器+ 1递归调用该函数如果不是，请使用列表的cdr和与以前相同的计数器值递归调用该函数