计算 Haskell 中排序列表中最常出现的数字

Question

问题是计算整数排序列表的众数（最常出现的值）。

[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 库即可。

Prelude 库中有filter、map、foldr 函数吗？

Answer 1

从头开始。

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

这听起来像是折叠的工作，因为折叠会经历一个序列，在给你最终结果之前聚合一路上的值。

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

Foldl 的类型如上所示。我们已经可以填写其中的一些内容（我发现这可以帮助我确定我需要什么类型）

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

我们需要通过它折叠一些东西来获取值。我们必须跟踪当前运行和当前计数

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

所以现在我们可以填写更多内容：

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

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

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 编写该函数

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

Answer 2

Prelude库中有filter、map、foldr函数吗？

停止...胡格尔时间！

您知道 Hoogle 会告诉您函数来自哪个模块吗？ Hoolging 地图 会在搜索页面上显示以下信息：

地图::(a -> b) -> [一]-> [b]

基础 Prelude，基础 Data.List

这意味着地图同时在 Prelude 和 Data.List 中定义。你可以搜索其他功能，同样可以看到它们确实在 Prelude 中。

您还可以查看 Haskell 2010 >标准 Prelude 或Prelude hackage 文档。

因此我们可以进行map、filter和foldr以及Prelude中的其他操作。那挺好的。让我们从 Landei 的想法开始，将列表变成列表的列表。

groupSorted :: [a] -> [[a]]
groupSorted = undefined
-- groupSorted [1,1,2,2,3,3] ==> [[1,1],[2,2],[3,3]]

我们应该如何实现groupSorted？嗯，我不知道。我们稍后再考虑一下。假设我们已经实现了它。我们如何使用它来获得正确的解决方案？我假设如果有多个正确的解决方案（如您的第二个示例中所示），则可以只选择一个正确的解决方案。

mode :: [a] -> a
mode xs = doSomething (groupSorted xs)
  where doSomething :: [[a]] -> a
        doSomething = undefined
        -- doSomething [[1],[2],[3,3]] ==> 3
-- mode [1,2,3,3] ==> 3

在列表上使用groupSorted之后，我们需要做一些事情。但什么？好吧...我们应该在列表列表中找到最长的列表。正确的？这将告诉我们哪个元素在原始列表中出现最多。然后，一旦找到最长的子列表，我们就想返回其中的元素。

chooseLongest :: [[a]] -> a
chooseLongest xs = head $ chooseBy (\ys -> length ys) xs
  where chooseBy :: ([a] -> b) -> [[a]] -> a
        chooseBy f zs = undefined
        -- chooseBy length [[1],[2],[3,3]] ==> [3,3]
-- chooseLongest [[1],[2],[3,3]] ==> 3

chooseLongest 是之前的doSomething。我们的想法是，我们想要在列表列表 xs 中选择最好的列表，然后获取其中的一个元素（它的 head 就可以了）。我通过创建一个更通用的函数 chooseBy 来定义它，该函数使用一个函数（在本例中，我们使用 length 函数）来确定最佳选择。

现在我们到了“困难”的部分。折叠。 chooseBy 和 groupSorted 都是折叠。我将引导您完成groupSorted，并将chooseBy留给您。

如何编写自己的折叠

我们知道 groupSorted 是一个折叠，因为它消耗整个列表，并产生全新的东西。

groupSorted :: [Int] -> [[Int]]
groupSorted xs = foldr step start xs
  where step :: Int -> [[Int]] -> [[Int]]
        step = undefined
        start :: [[Int]]
        start = undefined

我们需要选择一个初始值 start 和一个步进函数 step。我们知道它们的类型，因为 foldr 的类型是 (a -> b -> b) -> b-> [一]-> b，在本例中，a 是 Int（因为 xs 是 [Int]，它与[a]对齐），而我们想要最终得到的b是[[Int]]。

现在请记住，步进函数将逐一检查列表中的元素，并使用 step 将它们融合到累加器中。我将调用当前检查的元素 v 和累加器 acc。

step v acc = undefined

请记住，理论上，foldr 的工作方式是从右到左。假设我们有列表[1,2,3,3]。让我们逐步完成该算法，从最右边的 3 开始并向左进行。

step 3 start = [[3]]

无论 start 是什么，当我们将它与 3 组合时，它最终应该是 [[3]]。我们知道这一点是因为如果 groupSorted 的原始输入列表只是 [3]，那么我们需要 [[3]] 作为结果。然而，它不仅仅是[3]。现在我们假设它只是 [3,3]。 [[3]] 是新的累加器，我们想要的结果是 [[3,3]]。

step 3 [[3]] = [[3,3]]

我们应该如何处理这些输入？好吧，我们应该将 3 添加到该内部列表中。但下一步呢？

step 2 [[3,3]] = [[2],[3,3]]

在这种情况下，我们应该创建一个包含 2 的新列表。

step 1 [[2],[3,3]] = [[1],[2],[3,3]]

就像上次一样，在这种情况下，我们应该创建一个新列表，其中包含 1。

至此我们已经遍历了整个输入列表，并得到了最终的结果。那么我们如何定义step呢？根据 v 和 acc 之间的比较，似乎有两种情况。

step v acc@((x:xs):xss) | v == x    = (v:x:xs) : xss
                        | otherwise = [v] : acc

在一种情况下，v 与 acc 中第一个子列表的头相同。在这种情况下，我们将 v 添加到同一个子列表中。但如果情况并非如此，那么我们将 v 放入其自己的列表中，并将其添加到 acc 之前。那么 start 应该是什么？嗯，需要特殊处理；让我们只使用 [] 并为其添加一个特殊的模式匹配。

step elem [] = [[elem]]
start = []

现在你就得到了它。要编写折叠，您所需要做的就是确定 start 和 step 是什么，然后就完成了。通过一些清理和 eta 减少：

groupSorted = foldr step []
  where step v [] = [[v]]
        step v acc@((x:xs):xss)
          | v == x    = (v:x:xs) : xss
          | otherwise = [v] : acc

这可能不是最有效的解决方案，但它确实有效，如果您以后需要优化，您至少知道这个函数是如何工作的。

Answer 3

我不想破坏所有的乐趣，但是 group 功能会很有帮助。不幸的是它是在Data.List中定义的，因此您需要编写自己的。一种可能的方法是：

-- corrected version, see comments
grp [] = []
grp (x:xs) = let a = takeWhile (==x) xs
                 b = dropWhile (==x) xs
             in (x : a) : grp b

例如 grp [1,1,2,2,3,3,3] 给出 [[1,1],[2,2],[3, 3,3]]。我认为从那里你可以自己找到解决方案。

Answer 4

我会尝试以下操作：

mostFrequent = snd . foldl1 max . map mark . group
   where
      mark (a:as) = (1 + length as, a)
      mark [] = error "cannot happen"   --  because made by group

请注意，它适用于包含可排序元素的任何有限列表，而不仅仅是整数。