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

Question

如果我可以在命令式语言中使用数组或者在C++中使用map(树形结构),这非常容易.在计划中,我不知道如何开始这个想法？谁可以帮我这个事？

谢谢,

Answer 1

你的问题对于计算的内容并不十分具体.我假设您想要创建某种元素的频率表.有几种方法可以解决这个问题.(如果您使用的是Racket,请向下滚动到底部以获取我的首选解决方案.)

便携,纯功能,但冗长而缓慢

此方法使用关联列表(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))

递增是有趣的部分.为了实现纯函数,我们实际上不能更改alist的任何元素,而是必须排除正在更改的关联,然后将该关联(使用新值)添加到结果中.例如,如果您有以下列表:

((foo . 1) (bar . 2) (baz . 2))

并且想要添加1 baz的值,您创建一个新的列表,排除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)))

纯功能,简洁,快速,但不便携

这种方法使用特定于Racket的哈希表(与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

在 Racket 中，你可以这样做

(count even? '(1 2 3 4))

但更严重的是，使用计划中的列表执行此操作比您提到的要容易得多。列表要么是空的，要么是包含第一项和其余项的一对。在代码中遵循该定义，您将得到它“自行写出”。

这是基于HtDP的入门提示（这是一本了解这些内容的好书）。从函数“header”开始——它应该接收一个谓词和一个列表：

(define (count what list)
  ...)

添加输入的类型——what是一些值，并且list是一个内容列表：

;; count : Any List -> Int
(define (count what list)
  ...)

现在，给定 的类型list以及 list 的定义为空列表或一对两个事物，我们需要检查它是哪种列表：

;; count : Any List -> Int
(define (count what list)
  (cond [(null? list) ...]
        [else ...]))

what第一种情况应该很明显：空列表中有多少项？

对于第二种情况，您知道它是一个非空列表，因此您有两条信息：它的头（您使用firstor获得car）和它的尾部（您使用restor获得cdr）：

;; count : Any List -> Int
(define (count what list)
  (cond [(null? list) ...]
        [else ... (first list) ...
              ... (rest list) ...]))

您现在所需要做的就是弄清楚如何组合这两条信息来获取代码。最后一点信息使它非常简单：由于（非空）列表的尾部本身就是一个列表，因此您可以使用count它来计算其中的内容。因此，您可以进一步得出结论，您应该(count what (rest list))在那里使用。