问题是计算排序的整数列表的模式(最常出现的值).
[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吗？
从头开始.
您想要通过序列并获得整数的最大频率.
这听起来像是折叠的工作,因为折叠在给出最终结果之前会经历一个聚合值的序列.
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
所以现在我们可以使用foldlas 编写函数
bestRun :: [Int] -> Int
bestRun xs = bestNum (foldl f (BestRun 0 0 0 0) xs)
Prelude库中的函数是filter,map,foldr吗？
停止...... Hoogle时间!
你知道吗,Hoogle告诉你一个函数来自哪个模块？Hoolging地图会在搜索页面上显示此信息:
map ::(a - > b) - > [a] - > [b]
base Prelude,base Data.List
这意味着在地图中Prelude和地图中都定义了地图Data.List.您可以勾选其他功能,同样看到它们确实在Prelude中.
您还可以查看Haskell 2010>标准前奏或Prelude hackage文档.
因此,我们被允许map,filter和foldr,以及任何其他的前奏.非常好.让我们从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.我们知道他们的类型因为foldris 的类型(a -> b -> b) -> b -> [a] -> 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
这可能不是最有效的解决方案,但它可以工作,如果您以后需要优化,您至少可以了解此功能的工作原理.