Haskell - 最常见的价值

Question

如何在列表示例中获得最常见的值:

[1,3,4,5,6,6] -> output 6
[1,3,1,5] -> output 1

我试图通过我自己的功能得到它,但我无法实现它你们可以帮助我吗？

我的代码:

del x [] = []
del x (y:ys) = if x /= y 
            then y:del x y 
            else del x ys



obj  x []= []
obj  x (y:ys) = if x== y then y:obj x y else(obj  x ys)

tam [] = 0
tam (x:y) = 1+tam  y

fun (n1:[]) (n:[]) [] =n1
fun (n1:[]) (n:[]) (x:s) =if (tam(obj x (x:s)))>n then fun (x:[]) ((tam(obj x (x:s))):[]) (del x (x:s)) else(fun (n1:[]) (n:[]) (del x (x:s))) 

rep (x:s) = fun  (x:[]) ((tam(obj x (x:s))):[]) (del x (x:s))

Answer 1

扩展Satvik的最后一个建议,你可以使用(&&&) :: (b -> c) -> (b -> c') -> (b -> (c, c'))from Control.Arrow(注意我a = (->)在那个类型签名中代替以简化)来干净地执行decorate-sort-undecorate变换.

mostCommon list = fst . maximumBy (compare `on` snd) $ elemCount
      where elemCount = map (head &&& length) . group . sort $ list

该head &&& length函数有类型[b] -> (b, Int).它将列表转换为其第一个元素及其长度的元组,因此当与它组合时,group . sort您将获得列表中每个不同值的列表及其发生的次数.

此外,你应该考虑一下你打电话时会发生什么mostCommon [].显然没有合理的价值,因为根本没有元素.就目前而言,所提出的所有解决方案(包括我的)都只是在一个空列表中失败,这不是好的Haskell.正常的做法是返回a Maybe a,其中Nothing表示错误(在本例中为空列表)并Just a表示"实际"返回值.例如

mostCommon :: Ord a => [a] -> Maybe a
mostCommon [] = Nothing
mostCommon list = Just ... -- your implementation here

这更好,因为从代码安全的角度来看,部分函数(某些输入值未定义的函数)非常糟糕.你可以操纵Maybe使用模式匹配(匹配上值Nothing和Just x)和功能Data.Maybe(优选fromMaybe和maybe而非fromJust).

Answer 2

如果您希望从代码中获得一些想要实现的想法,这里有一个例子:

import Data.List (nub, maximumBy)
import Data.Function (on)

mostCommonElem list = fst $ maximumBy (compare `on` snd) elemCounts where
    elemCounts = nub [(element, count) | element <- list, let count = length (filter (==element) list)]

Answer 3

这里有一些建议

del可以使用过滤器来实现，而不是编写自己的递归。在你的定义中有一个错误，你需要给予ys而不是y删除时。

del x = filter (/=x)

objdel与不同的过滤功能类似。同样，在您的定义中，您需要给出ys而不是y在obj.

obj  x = filter (==x)

tam只是length函数

-- tam = length

您不需要保留n1和 的列表n。我还使您的代码更具可读性，尽管我没有对您的算法进行任何更改。

fun n1 n [] =n1
fun n1 n xs@(x:s) | length (obj x xs) > n = fun x (length $ obj x xs) (del x xs)
                  | otherwise             = fun n1 n $ del x xs

rep xs@(x:s) = fun  x (length $ obj x xs) (del x xs)

另一种方式，不是很理想，但更具可读性是

import Data.List
import Data.Ord

rep :: Ord a => [a] -> a
rep = head . head . sortBy (flip $ comparing length) . group . sort

我将尝试简短地解释这段代码的作用。您需要找到列表中最常见的元素，因此首先想到的想法是找到所有元素的频率。Nowgroup是一个组合相邻相似元素的函数。

> group [1,2,2,3,3,3,1,2,4]
[[1],[2,2],[3,3,3],[1],[2],[4]]

所以我使用排序将相同的元素彼此相邻

> sort [1,2,2,3,3,3,1,2,4]
[1,1,2,2,2,3,3,3,4]

> group . sort $ [1,2,2,3,3,3,1,2,4]
[[1,1],[2,2,2],[3,3,3],[4]]

查找频率最大的元素只是简化为查找元素数量最多的子列表。这里有一个函数sortBy，您可以使用它根据给定的比较函数进行排序。所以基本上我已经对子length列表进行了排序（翻转只是为了使排序降序而不是升序）。

> sortBy (flip $ comparing length) . group . sort $ [1,2,2,3,3,3,1,2,4]
[[2,2,2],[3,3,3],[1,1],[4]]

现在您只需花费head两次即可获得频率最大的元素。