哈斯克爾 - 最頻值

我怎樣才能在列表範例中得到最頻繁的值：哈斯克爾 - 最頻值

[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))

來源

2012-12-12 Urah

請發表您已經嘗試了什麼。 – luqui

這是爲什麼標記遞歸？ –

我想用遞歸來實現 – Urah

這裏有幾個建議

del可以使用過濾器，而不是寫你自己的遞歸來實現。在您的定義中有一個錯誤，您需要在刪除時提供ys而不是y。

del x = filter (/=x)

obj是用不同的過濾器功能類似於del。同樣，在您的定義中，您需要在obj中給出ys而不是y。

obj x = filter (==x)

tam只是length功能

-- tam = length

你並不需要保持一個列表n1和n。我也讓你的代碼更具可讀性，雖然我沒有對你的算法做任何改變。

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

rep [email protected](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

我會盡量在短期解釋一下這個代碼在做什麼。你需要找到列表中最頻繁的元素，所以首先想到的第一個想法是找出所有元素的頻率。現在group是一個結合了相鄰相似元素的功能。

> 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兩次獲得具有最大頻率的元素。

來源

2012-12-12 06:07:08 Satvik

除了最後的工作代碼片段與好的答案沒有解釋。 – luqui

@luqui有更多有禮貌的方式來表達這一點，例如：「好的答案，你可以加上最後一個片段的一些解釋嗎？」 – AndrewC

@luqui我認爲最後一個片段是足夠可讀的，但我會添加更多關於它在做什麼的信息。還有兩個工作版本 - 第一個是你的代碼很少修改，另一個是更短的更可讀的版本。 – Satvik

如果你想從代碼中得到一些想法，做你想實現什麼，這裏有一個例子：

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)]

來源

2012-12-12 06:11:26 ljedrz

對不起，作爲一項規則，我downvote完整的實現沒有解釋。我知道你已經開始了，但是...... – luqui

@luqui作爲一項規則，我認爲在低迴報的用戶表達意見之前，他們明顯試圖提供幫助，並且試圖對如何改進他們的答案給出禮貌的，建設性的，積極的建議。你已經給ybz3的代表5％的折扣，這就像我從你那裏收到900代表一樣，你很久以前就不再擔心你的代理了。我毫不猶豫地低估了毫無幫助的粗心大意，但事實並非如此。 – AndrewC

@luqui考慮一下這個事實，即烏拉想用自己的功能來實現它。我使用現有的代碼編寫了代碼，所以我的代碼甚至不接近Urah想要實現的代碼。它的目的是作爲一個線索 - 當我想自己實現某些東西時，我會看別人的代碼來獲得一些想法。 – ljedrz

擴展在Satvik的最後一個建議，你可以使用(&&&) :: (b -> c) -> (b -> c') -> (b -> (c, c'))從Control.Arrow（請注意，爲簡單起見，我用a = (->)代替那種類型的簽名）乾淨地執行decorate-sort-undecorate transform。

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。正常的事情是返回一個Maybe a，其中Nothing表示一個錯誤（在這個例子中是一個空列表），Just a表示一個「真實」的返回值。例如

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

這是好得多，因爲部分功能（函數是未定義的某些輸入值）是從一個代碼安全點可怕。您可以使用模式匹配（匹配Nothing和Just x）和Data.Maybe（優選fromMaybe和maybe而不是fromJust）中的函數來操作Maybe值。

來源

2012-12-12 11:44:25 huon

我希望看到一個完整的工作實現提示。感謝至少給出了一些解釋，以便它如何工作，儘管我認爲它可能對於OP來說太高級了。 – luqui

@luqui對於非高級問題，人們看到更先進的解決方案非常具有教育意義，所以當他們真正遇到Control.Arrow時，他們熟悉一些功能。瞭解專家程序員如何思考問題也是一種教育。並不是每個訪問者都是OP;堆棧溢出被設計爲一個永久的參考。聰明的答案在直截了當的答案中有重要的地位。 – AndrewC

我們假設你已經有argmax函數。你可以自己寫甚至更好，可以重複使用list-extras包。無論如何，我強烈建議你去看看這個軟件包。

然後，它很容易：

import Data.List.Extras.Argmax (argmax) 

-- >> mostFrequent [3,1,2,3,2,3] 
-- 3 
mostFrequent xs = argmax f xs 
    where f x = length $ filter (==x) xs

來源

2015-12-01 19:43:25 penkovsky

哈斯克爾 - 最頻值

回答

相關問題