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：创建等效列表

回答

相关问题