Haskell – 计算列表中元素的频率

huangapple go评论60阅读模式
英文:

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

不用说,上述代码无法编译。

至少有一个用于频率计数的问题,但在我的情况下,有以下要求:

  1. 需要使用 Map.alter
  2. 需要使用 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:

  1. Need to use Map.alter
  2. Need to use foldr
    (Map.findWithDefault might come in handy, too.)

Question: What am I missing here?

答案1

得分: 3

以下是已翻译的内容:

"如果这是一项练习,例如,一项家庭作业任务(根据所述的要求,它确实似乎是一项),我建议您只阅读这个答案,以获得足够的信息再次尝试,只有在您要么已经得到了一个可行的解决方案,要么再次陷入困境而无法继续时才返回。

由于您的问题没有说明您当前的无法编译的解决方案尝试背后的思维过程,我无法真正告诉您出了什么问题以及如何修复它,因此我将沿用自己的思维过程来尝试解决这个问题,考虑到给定的限制。

在这之前,一些一般性观察可能有助于指导您的进一步尝试:

  • 在这种练习中,通常不要求您以非常复杂或不寻常的方式使用练习规定您必须使用的内容(这里是Map.alterfoldr)。通常情况下,您实际上被期望了解它们的示范性典型用法(即它们被认为“适用”的方式),这通常非常符合手头的任务,至少事后看来是这样的。
  • Map.alter 用于修改 Map 中的单个条目,通过其键标识 — 可能是添加或删除它,或者只是更改关联的值。
  • foldr 用于处理 Foldable,通常是一个列表。在命令式语言中,在大多数情况下,您会在相同的情况下使用循环和累加器变量(或累加器数据结构)。
  • 如果练习说明某事“也可能会派上用场”,通常有一个直接的解决方案,不需要它,还有另一个也可能很直接的解决方案,可能需要它。因此,不要试图从一开始就添加这些东西,只需在以后有明显的用途时记住它们。

在此答案中,我将假设 Map 模块已按其文档中建议的导入:

import Data.Map (Map)
import qualified Data.Map as Map

因此,任务似乎是统计列表中所有不同元素的出现次数,使用 Map.alterfoldr,将结果作为从元素到次数的 Map 返回。

想法:让我们从一个空的映射开始,逐个查看列表的元素,生成已看到的元素的更新映射。

我们是否可以使用 Map.alter 来从这些映射之一获取后续映射?让我们查看它的签名:

alter :: Ord k => (Maybe a -> Maybe a) -> k -> Map k a -> Map k a 

因此,如果我们传递一个从 Maybe aMaybe 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 很适合作为 bfoldr 的第二个参数是“累加器”的“起始值”。根据上述想法,它必须是 [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 and foldr) 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 a Map, identified by its key — maybe adding or removing it, maybe just changing the associated value.
  • foldr is for processing a Foldable 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)]

huangapple
  • 本文由 发表于 2023年5月21日 18:32:31
  • 转载请务必保留本文链接:https://go.coder-hub.com/76299436.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定