计算方案中列表中元素的出现次数?

发布于 2024-11-02 15:12:10 字数 92 浏览 0 评论 0原文

例如,如果我可以使用命令式语言中的数组或 C++ 中的映射(树结构),这将非常容易。在方案中,我不知道如何开始这个想法?有人能帮我解决这个问题吗?

谢谢,

This is extremely easy if I can use an array in imperative language or map (tree-structure) in C++ for example. In scheme, I have no idea how to start this idea? Can anyone help me on this?

Thanks,

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(4

时间你老了 2024-11-09 15:12:10

您的问题对于计算的内容不是很具体。我假设您想要创建某种元素的频率表。有几种方法可以解决这个问题。 (如果您使用 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 的任何元素,而是必须排除正在更改的关联,然后将该关联(具有新值)添加到结果中。例如,如果您有以下 alist:

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

并且想要将 1 添加到 baz 的值,您可以创建一个不包括 baz 的新 alist:,

((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 在执行纯功能任务时的任何特定失败。有了合适的库,这个任务就可以轻松、有效地实现。

Your question wasn't very specific about what's being counted. I will presume you want to create some sort of frequency table of the elements. There are several ways to go about this. (If you're using Racket, scroll down to the bottom for my preferred solution.)

Portable, pure-functional, but verbose and slow

This approach uses an association list (alist) to hold the elements and their counts. For each item in the incoming list, it looks up the item in the alist, and increments the value of it exists, or initialises it to 1 if it doesn't.

(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))

The incrementing is the interesting part. In order to be pure-functional, we can't actually change any element of the alist, but instead have to exclude the association being changed, then add that association (with the new value) to the result. For example, if you had the following alist:

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

and wanted to add 1 to baz's value, you create a new alist that excludes baz:

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

then add baz's new value back on:

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

The second step is what the exclude function does, and is probably the most complicated part of the function.

Portable, succinct, fast, but non-functional

A much more straightforward way is to use a hash table (from SRFI 69), then update it piecemeal for each element of the list. Since we're updating the hash table directly, it's not pure-functional.

(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)))

Pure-functional, succinct, fast, but non-portable

This approach uses Racket-specific hash tables (which are different from SRFI 69's ones), which do support a pure-functional workflow. As another benefit, this version is also the most succinct of the three.

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

You can even use a for comprehension for this:

(define (bagify lst)
  (for/fold ((ht #hash()))
            ((key (in-list lst)))
    (hash-update ht key add1 0)))

This is more a sign of the shortcomings of the portable SRFI 69 hashing library, than any particular failing of Scheme for doing pure-functional tasks. With the right library, this task can be implemented easily and functionally.

忘你却要生生世世 2024-11-09 15:12:10

在 Racket 中,您可以执行此操作

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

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

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

(define (count what list)
  ...)

添加输入的类型 - what 是某个值,list 是一个list of stuff:

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

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

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

第一种情况应该很明显:空列表中有多少个 what 项?

对于第二种情况,您知道它是一个非空列表,因此您有两条信息:它的头(您可以使用 firstcar 获得)和它的头tail(通过 restcdr 获得):

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

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

In Racket, you could do

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

But more seriously, doing this with lists in Scheme is much easier that what you mention. A list is either empty, or a pair holding the first item and the rest. Follow that definition in code and you'll get it to "write itself out".

Here's a hint for a start, based on HtDP (which is a good book to go through to learn about these things). Start with just the function "header" -- it should receive a predicate and a list:

(define (count what list)
  ...)

Add the types for the inputs -- what is some value, and list is a list of stuff:

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

Now, given the type of list, and the definition of list as either an empty list or a pair of two things, we need to check which kind of list it is:

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

The first case should be obvious: how many what items are in the empty list?

For the second case, you know that it's a non-empty list, therefore you have two pieces of information: its head (which you get using first or car) and its tail (which you get with rest or cdr):

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

All you need now is to figure out how to combine these two pieces of information to get the code. One last bit of information that makes it very straightforward is: since the tail of a (non-empty) list is itself a list, then you can use count to count stuff in it. Therefore, you can further conclude that you should use (count what (rest list)) in there.

月朦胧 2024-11-09 15:12:10

在像Scheme这样的函数式编程语言中,你必须以不同的方式思考并利用列表的构造方式。您不是通过增加索引来迭代列表,而是递归地遍历列表。您可以使用 car (单个元素)删除列表的头部,您可以使用 cdr (列表本身)获取尾部,并且可以将头部与其粘合在一起尾部带有cons。你的函数的轮廓将是这样的:

  • 你必须“传递”你正在搜索的元素和函数每次调用的当前计数
  • 如果你点击空列表,你就完成了列表可以输出结果
  • 如果列表中的 car 等于你要查找的元素,则使用列表的 cdr 和计数器 + 1 递归调用该函数
  • 如果不是,则使用列表的 cdr 和计数器递归调用该函数与之前相同的计数器值

In functional programming languages like Scheme you have to think a bit differently and exploit the way lists are being constructed. Instead of iterating over a list by incrementing an index, you go through the list recursively. You can remove the head of the list with car (single element), you can get the tail with cdr (a list itself) and you can glue together a head and its tail with cons. The outline of your function would be like this:

  • You have to "hand-down" the element you're searching for and the current count to each call of the function
  • If you hit the empty list, you're done with the list an you can output the result
  • If the car of the list equals the element you're looking for, call the function recursively with the cdr of the list and the counter + 1
  • If not, call the function recursively with the cdr of the list and the same counter value as before
情话墙 2024-11-09 15:12:10

在Scheme中,您通常使用关联列表作为 O(n) 穷人的哈希表/字典。您剩下的唯一问题是如何更新关联的元素。

In Scheme you generally use association lists as an O(n) poor-man's hashtable/dictionary. The only remaining issue for you would be how to update the associated element.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文