英文:
Haskell - compute frequencies of elements in a list
问题
Sure, here's the translated code portion:
我需要计算输入列表的频率映射。我的尝试:
f :: (Eq a, Ord a) => (a -> a) -> Map.Map a Int -> Map.Map a Int
f x m = Map.alter id (Map.findWithDefault 0 x m + 1) m
freqs :: (Eq a, Ord a) => [a] -> Map.Map a Int
freqs xs = foldr f (Map.fromList []) xs
不用说,上述代码无法编译。
至少有一个用于频率计数的问题,但在我的情况下,有以下要求:
- 需要使用
Map.alter
- 需要使用
foldr
(Map.findWithDefault
也可能有用。)
问题:我在这里漏掉了什么?
英文:
I need to compute a frequency map of an input list. My attempt:
f :: (Eq a, Ord a) => (a -> a) -> Map.Map a Int -> Map.Map a Int
f x m = Map.alter id (Map.findWithDefault 0 x m + 1) m
freqs :: (Eq a, Ord a) => [a] -> Map.Map a Int
freqs xs = foldr f (Map.fromList []) xs
Needless to say, the above does not compile.
There seems to be at least one question for frequency counts, yet, in my case, there are requirements:
- Need to use
Map.alter
- Need to use
foldr
(Map.findWithDefault
might come in handy, too.)
Question: What am I missing here?
答案1
得分: 3
以下是已翻译的内容:
"如果这是一项练习,例如,一项家庭作业任务(根据所述的要求,它确实似乎是一项),我建议您只阅读这个答案,以获得足够的信息再次尝试,只有在您要么已经得到了一个可行的解决方案,要么再次陷入困境而无法继续时才返回。
由于您的问题没有说明您当前的无法编译的解决方案尝试背后的思维过程,我无法真正告诉您出了什么问题以及如何修复它,因此我将沿用自己的思维过程来尝试解决这个问题,考虑到给定的限制。
在这之前,一些一般性观察可能有助于指导您的进一步尝试:
- 在这种练习中,通常不要求您以非常复杂或不寻常的方式使用练习规定您必须使用的内容(这里是
Map.alter
和foldr
)。通常情况下,您实际上被期望了解它们的示范性典型用法(即它们被认为“适用”的方式),这通常非常符合手头的任务,至少事后看来是这样的。 Map.alter
用于修改Map
中的单个条目,通过其键标识 — 可能是添加或删除它,或者只是更改关联的值。foldr
用于处理Foldable
,通常是一个列表。在命令式语言中,在大多数情况下,您会在相同的情况下使用循环和累加器变量(或累加器数据结构)。- 如果练习说明某事“也可能会派上用场”,通常有一个直接的解决方案,不需要它,还有另一个也可能很直接的解决方案,可能需要它。因此,不要试图从一开始就添加这些东西,只需在以后有明显的用途时记住它们。
在此答案中,我将假设 Map
模块已按其文档中建议的导入:
import Data.Map (Map)
import qualified Data.Map as Map
因此,任务似乎是统计列表中所有不同元素的出现次数,使用 Map.alter
和 foldr
,将结果作为从元素到次数的 Map
返回。
想法:让我们从一个空的映射开始,逐个查看列表的元素,生成已看到的元素的更新映射。
我们是否可以使用 Map.alter
来从这些映射之一获取后续映射?让我们查看它的签名:
alter :: Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
因此,如果我们传递一个从 Maybe a
到 Maybe a
的函数和一个键,我们将得到一个函数,它“更改”一个映射(将一个这样的映射作为参数并返回相同类型的映射)。文档没有详细说明我们传递给 Map.Alter
的第一个参数的 Maybe a
参数将如何使用,但如果可能的话,它似乎是合理的,如果存在,则是在问题中的键处的前一个值 Just
,否则是 Nothing
。从文档中给出的示例中,返回值的作用很明显:Nothing
“删除”条目(即将其从生成的 Map
中省略),Just x
“修改”给定键处的条目的值为 x
(如果已存在),否则将键和值 x 插入到传递的 Map
中。
因此,我们需要一个可以作为 Map.alter
第一个参数插入的函数。这个函数将收到 Just
问题中元素的先前计数,或者如果尚未出现则为 Nothing
,并且必须返回考虑到一个元素的一次更多出现的新计数,即将其增加一次。我们可以轻松编写这个函数:
inc :: Maybe Int -> Maybe Int
inc Nothing = Just 1
inc (Just n) = Just $ n + 1
我们必须使用 foldr
。可能是为了处理输入列表中的所有元素。让我们查看其签名:
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
我们知道我们正在处理的不只是任何 Foldable
,而是具体的列表,因此对于我们的情况,这将变为
foldr @[] :: (a -> b -> b) -> b -> [a] -> b
(在 GHCi 中,您可以使用 :t foldr @[]
查询此信息。)
我们可以使用我们的输入列表作为第三个参数(类型为 [a]
)。类型 b
是最终结果和中间结果(可以考虑为累加器)的类型。根据上面的想法,我们可以得出 Map a Int
很适合作为 b
。foldr
的第二个参数是“累加器”的“起始值”。根据上述想法,它必须是 [Map.empty
](https://hackage.haskell.org/package/containers-0
英文:
If this is an exercise, e.g., a homework task, (and from the stated requirements, it certainly seems to be one) I recommend that you read this answer only as far as to give you enough information to try again yourself, and to only come back when you either got to a working solution or are too stuck again to proceed yourself.
As your question doesn't state the thought process behind your current non-compiling solution attempt, I can't really tell where it went wrong or how to fix it, so instead I'll walk you along my own thought process in attempting to solve this problem with the given constraints.
Before I do that, some general observations, that might help inform your own further attempts:
- In exercises like this, you're usually not expected to use the stuff that the exercise states you must use (here:
Map.alter
andfoldr
) in very convoluted or unusual ways. Often, you're in fact expected find out more about their exemplar prototypical usage (i.e., what they're considered to be "good for"), which often fits the task at hand so well that it'll be rather simple — at least in retrospect. Map.alter
is for modifying a single entry of aMap
, identified by its key — maybe adding or removing it, maybe just changing the associated value.foldr
is for processing aFoldable
in general or specifically a list. In imperative languages, you'd use a loop and an accumulator variable (or accumulator data structure) in mostly the same situations.- If an exercise states that something "might come in handy, too", there's often a straight forward solution without it and another, maybe similarly straight forward one, that might require it. Thus, don't try to shove these things in from the beginning, just keep them in mind in case you'll see a clear use for them.
In this answer, I'll assume that the Map
module is imported as suggested in its documentation:
import Data.Map (Map)
import qualified Data.Map as Map
So the task seems to be counting number of occurrences for all distinct elements of a list, using Map.alter
and foldr
, returning the result as a Map
from elements to number or occurrences.
Idea: Let's start with an empty map, and look at the elements of the list one by one, generating updated maps accounting for the elements seen so far.
Can we use Map.alter
for getting from one of these maps to the subsequent one? Let's look at its signature:
alter :: Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
So if we pass a function from Maybe a
to Maybe a
and a key, we'll get a function that "changes" a map (takes one such map as an argument and returns a map of the same type). The documentation doesn't spell out what the Maybe a
argument will be passed to that function we pass as first argument to Map.Alter
, but it seems quite plausible that it's Just
the previous value at the key in question if present, and Nothing
otherwise. The role of the return value is clear from the examples given in the documentation: Nothing
"deletes" the entry (i.e., omits it from the resulting Map
), Just x
"modifies" the value of the entry at the given key to x
if already present or "inserts" the key-value par with the given key and value x if it wasn't already in the passed Map
.
So we need a function we can plug as first argument into Map.alter
. That function will receive Just
the previous count for the element at question or Nothing
if it didn't occur yet and will have to return Just
the new count considering one more occurrence of the element, i.e., increase it by one. We can easily write that function:
inc :: Maybe Int -> Maybe Int
inc Nothing = Just 1
inc (Just n) = Just $ n + 1
We have to use foldr
. Probably it's to handle all elements from the input list. Let's look at its signature:
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
We know we are dealing with not just any Foldable
, but specifically with a list, so for our case, this becomes
foldr @[] :: (a -> b -> b) -> b -> [a] -> b
(In GHCi, you can query this with :t foldr @[]
.)
We can use our input list as the third argument (of type [a]
). Type b
is the type of both, the end result and of the intermediate results (which one might consider accumulators). From our idea stated above, we can conclude that Map a Int
fits nicely as b
. The second argument of foldr
is the "start value" of the "accumulator". According to said idea, it must be Map.empty
.
So what's still missing is the first argument, a function from a
(type of the elements of the list) and b
(the Map a Int
representing the counts so far) to b
(another Map a Int
, representing the counts updated with the occurrence of that element). I'll call that function considerOccurence
, because it gives us a map of updated tallies considering one more occurrence of a specific element. It's type must be Ord a => a -> Map a Int -> Map a Int
. With Map.alter
and our inc
from above, we can easily implement it:
considerOccurence :: Ord a => a -> Map a Int -> Map a Int
considerOccurence x previousCounts = Map.alter inc x previousCounts
or in point-free notation:
considerOccurence :: Ord a => a -> Map a Int -> Map a Int
considerOccurence = Map.alter inc
Now we can plug considerOccurence
into foldr
to get the function we want for the overall task:
freqs :: Ord a => [a] -> Map a Int
freqs xs = foldr considerOccurence Map.empty xs
or in point-free notation
freqs :: Ord a => [a] -> Map a Int
freqs = foldr considerOccurence Map.empty
In case you want it all in a single top-level function:
freqs :: Ord a => [a] -> Map a Int
freqs = foldr considerOccurence Map.empty
where
considerOccurence = Map.alter inc
inc Nothing = Just 1
inc (Just n) = Just $ n + 1
Let's test it:
>>> freqs "Missisippi"
fromList [('M',1),('i',4),('p',2),('s',3)]
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论