计算方案中列表中元素的出现次数?
例如,如果我可以使用命令式语言中的数组或 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 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(4)
您的问题对于计算的内容不是很具体。我假设您想要创建某种元素的频率表。有几种方法可以解决这个问题。 (如果您使用 Racket,请向下滚动到底部以获得我的首选解决方案。)
可移植、纯功能,但冗长且缓慢
此方法使用关联列表 (alist) 来保存元素及其计数。对于传入列表中的每个项目,它会在列表中查找该项目,并递增其存在的值,如果不存在则将其初始化为 1。
递增是有趣的部分。为了实现纯功能,我们实际上不能更改 alist 的任何元素,而是必须排除正在更改的关联,然后将该关联(具有新值)添加到结果中。例如,如果您有以下 alist:
并且想要将 1 添加到
baz
的值,您可以创建一个不包括baz
的新 alist:,然后添加
baz
的新值重新出现:第二步是
exclude
函数的作用,并且可能是该函数中最复杂的部分。可移植、简洁、快速,但无功能
一种更直接的方法是使用哈希表(来自 SRFI 69),然后针对列表中的每个元素逐一更新它。由于我们直接更新哈希表,因此它不是纯功能的。
纯功能、简洁、快速,但不可移植
这种方法使用特定于 Racket 的哈希表(与 SRFI 69 的哈希表不同),它确实支持纯功能工作流程。另一个好处是,这个版本也是三个版本中最简洁的。
您甚至可以为此使用
for
理解:这更多地表明了可移植 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.
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:
and wanted to add 1 to
baz
's value, you create a new alist that excludesbaz
:then add
baz
's new value back on: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.
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.
You can even use a
for
comprehension for this: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.
在 Racket 中,您可以执行此操作
,但更严重的是,使用 Scheme 中的列表执行此操作比您提到的要容易得多。列表要么是空的,要么是包含第一项和其余项的一对。在代码中遵循该定义,您将得到它“自行写出”。
这是基于 HtDP 的入门提示(这是一本了解这些内容的好书)。从函数“header”开始 - 它应该接收一个谓词和一个列表:
添加输入的类型 -
what
是某个值,list
是一个list of stuff:现在,给定
list
的类型,以及 list 的定义为空列表或一对两个事物,我们需要检查它是哪种列表:第一种情况应该很明显:空列表中有多少个
what
项?对于第二种情况,您知道它是一个非空列表,因此您有两条信息:它的头(您可以使用
first
或car
获得)和它的头tail(通过rest
或cdr
获得):您现在需要做的就是弄清楚如何组合这两条信息来获取代码。最后一点信息使它非常简单:由于(非空)列表的尾部本身就是一个列表,因此您可以使用
count
来计算其中的内容。因此,您可以进一步得出结论,您应该在其中使用(count what (rest list))
。In Racket, you could do
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:
Add the types for the inputs --
what
is some value, andlist
is a list of stuff: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: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
orcar
) and its tail (which you get withrest
orcdr
):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.在像Scheme这样的函数式编程语言中,你必须以不同的方式思考并利用列表的构造方式。您不是通过增加索引来迭代列表,而是递归地遍历列表。您可以使用
car
(单个元素)删除列表的头部,您可以使用cdr
(列表本身)获取尾部,并且可以将头部与其粘合在一起尾部带有cons
。你的函数的轮廓将是这样的: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 withcdr
(a list itself) and you can glue together a head and its tail withcons
. The outline of your function would be like this:在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.