Haskell：創建等效列表

我想用下面的定義創建一個函數。Haskell：創建等效列表

equivalent :: Eq a => (a -> a -> Bool) -> [a] -> [[a]]

等效的定義。
三個整數x，y，p
x mod p == y mod p那麼x和y是等價的。
否則x和y不等價。

案例：P = 3，
equivalent eq [1..10]返回列表[[3, 6, 9], [1, 4, 7, 10], [2, 5, 8]]
eq是需要兩個整數並返回真/假的功能。

你能指導我如何在Haskell中創建函數嗎？

來源

2017-07-29 notfounds

你有什麼試過？什麼地方出了錯？ –

我嘗試從[1 ... 10]中提取兩個值並嘗試使用函數eq進行等價判斷，但我不知道如何將具有兩個參數的函數傳遞給'filter'。 – notfounds

我誤解了'Eq'，我會重新思考。 – notfounds

這是一個遞歸解決方案。

彈出列表的第一個元素（x）。
使用partition到列表中的其餘部分分割成是相當於x（group）元素和元素不相當於x（others）。
x:group是我們發現的第一個組，然後我們遞歸others。

import Data.List (partition) 

equivalent :: (a -> a -> Bool) -> [a] -> [[a]] 
equivalent eq = go 
    where 
    go [] = [] 
    go (x:xs) = 
     let (group, others) = partition (eq x) xs 
     in (x:group) : go others

證明使用：

>>> import Data.Function (on) 
>>> equivalent ((==) `on` (`mod` 3)) [1..10] 
[[1,4,7,10],[2,5,8],[3,6,9]]

順便說一句，這裏是另一種方式來完成同樣的事情，我懷疑是速度快：

>>> fmap (fmap snd) . groupBy ((==) `on` fst) . sort . fmap (\i -> (i `mod` 3, i)) $ [1..10] 
[[3,6,9],[1,4,7,10],[2,5,8]]

來源

2017-07-29 04:30:44

感謝您的快速回復。我剛開始學習Haskell。再次感謝 – notfounds

對於模塊化算術示例，排序不是最好的選擇。排序是O（n log n），其中n是處理元素的數量。如果使用帶有餘數的'Data.Map'作爲鍵和數字列表作爲值，則可以得到O（n log m），其中n是值的數量，m是* distinct *餘數的數量。適用時，「數據」。IntMap'幾乎可以肯定會快得多，並且O（n）邊界不太容易表徵。（你可以將它看作具有相當大的常數因子的O（n），但實際上它通常比建議的要好得多）。 – dfeuer

另外一個執行這項工作的方法是使用filter和(\\) (difference)通過列表功能。所以下面的遞歸代碼應該足夠了。

groupByRemaindersOf :: Integral a => a -> [a] -> [[a]] 
groupByRemaindersOf _ []  = [] 
groupByRemaindersOf p (x:xs) = let ys = x : filter (\y -> y `rem` p == x `rem` p) xs in ys : groupByRemaindersOf p (xs \\ ys) 

*Main> groupByRemaindersOf 3 [1..10] 
[[1,4,7,10],[2,5,8],[3,6,9]]

儘管這似乎是比涉及sort任何算法快，我相信有Map類型的蓄電池可能仍然做的比這更好的摺疊。

來源

2017-07-30 22:17:36 Redu

Haskell：創建等效列表

回答

相關問題