计算Haskell中排序列表的数字的最频繁出现 [英] Compute Most Frequent Occurance of Numbers of A Sorted List in Haskell

问题描述

问题是要计算整数排序列表的模式(最常出现的值).

The question is to compute the mode (the value that occurs most frequently) of a sorted list of integers.

[1,1,1,1,2,2,3,3]  -> 1
[2,2,3,3,3,3,4,4,8,8,8,8] -> 3 or 8
[3,3,3,3,4,4,5,5,6,6] -> 3

只需使用Prelude库.

Just use the Prelude library.

Prelude库中的功能过滤器，地图，文件夹吗?

Are the functions filter, map, foldr in Prelude library?

推荐答案

从头开始.

您想要遍历一个序列并获得整数的最大频率.

You want to make a pass through a sequence and get the maximum frequency of an integer.

这听起来像是一项折叠工作，因为折叠经过一个序列，在为您提供最终结果之前，一直沿途汇总一个值.

This sounds like a job for fold, as fold goes through a sequence aggregating a value along the way before giving you a final result.

foldl :: (a -> b -> a) -> a -> [b] -> a

折叠的类型如上所示.我们已经可以填写其中的一些内容(我发现这可以帮助我确定所需的类型)

The type of foldl is shown above. We can fill in some of that already (I find that helps me work out what types I need)

foldl :: (a -> Int -> a) -> a -> [Int] -> a

我们需要通过折叠来获得价值.我们必须跟踪当前运行和当前计数

We need to fold something through that to get the value. We have to keep track of the current run and the current count

data BestRun = BestRun {
   currentNum :: Int,
   occurrences :: Int,
   bestNum :: Int,
   bestOccurrences :: Int
}

现在我们可以再填写一点:

So now we can fill in a bit more:

foldl :: (BestRun -> Int -> BestRun) -> BestRun -> [Int] -> BestRun

所以我们想要一个执行聚合的函数

So we want a function that does the aggregation

f :: BestRun -> Int -> BestRun
f (BestRun current occ best bestOcc) x
  | x == current = (BestRun current (occ + 1) best bestOcc) -- continuing current sequence
  | occ > bestOcc = (BestRun x 1 current occ) -- a new best sequence
  | otherwise      = (BestRun x 1 best bestOcc) -- new sequence

所以现在我们可以使用foldl as

So now we can write the function using foldl as

bestRun :: [Int] -> Int
bestRun xs = bestNum (foldl f (BestRun 0 0 0 0) xs)

这篇关于计算Haskell中排序列表的数字的最频繁出现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！