0

我一直在使用 Haskell 进行编码，但无法掌握实现联合功能的想法。我还发现了一些嵌入在 Haskell 平台中的函数定义。但问题是我需要一种简洁易懂的方式来让它工作。任何人都可以帮助我吗？

4

2 回答 2

11

假设您正在谈论union :: Eq a => [a] -> [a] -> [a]which 接受两个输入列表并返回包含每个参数列表的所有元素的第三个列表，那么它Data.List在base包中定义。

在源代码中，它分为两个函数，通用函数unionBy接受一个自定义的相等定义（类型等于的函数(==) :: a -> a -> Bool），然后Eq通过传入(==)作为相等的具体实现来定义使用类型类的函数。

union                   :: (Eq a) => [a] -> [a] -> [a]
union                   = unionBy (==)

不过，我们可以代(==)入unionBy代码，因为 Haskell 允许我们使用等式推理。

union = unionBy (==)

-- so...

union       :: Eq a => [a] -> [a] -> [a]
union xs ys =  xs ++ foldl (flip (deleteBy (==))) (nubBy (==) ys) xs

unionBy同样的模式在 in 和 的定义中deleteBy又出现了两次nubBy，两者都遵循相同的约定。delete从列表中删除一个元素并nub返回一个唯一元素的列表。我们将再次简化定义以消除所有痕迹(==)并简单地假设元素a已Eq定义。

union xs ys = xs ++ foldl (flip delete) (nub ys) xs

现在该定义可能更具可读性。的union和附加xs到已由 处理ys的xs唯一（“nub床”）值。其最终结果是对from的每个元素一一尝试。最终的意思是从less 中附加到每个唯一元素 。ysfoldl (flip delete) _ xsfoldldeletexs(nub ys)union xs ysxsysxs

顺便说一句，有了这个来源，我们可以注意到一些古怪的行为，union例如它如何处理第一个参数中的重复项与第二个参数不同

union [1,1,2] [2] == [1,1,2]
union [2] [1,1,2] == [2,1]

这有点令人失望，这是使用[]来表示类似Set的概念的结果union。但是，如果我们使用Set.fromListthen 查看结果，那就没问题了。

xs, ys :: Eq a => [a]
Set.fromList (xs `union` ys) == Set.fromList xs `Set.union` Set.fromList ys

这也给了我们另一个定义union

union xs ys = Set.toList (Set.fromList xs `Set.union` Set.fromList ys)

那么这个foldl技巧是如何工作的呢？让我们解开foldlto see 的定义，再次滥用等式推理。

union xs ys = xs ++ (case xs of
  []      -> nub ys
  (x:xs') -> foldl (flip delete) (delete x (nub ys)) xs'
  )

这应该使这个技巧更加明显——它循环遍历 的元素xs，从 . 中一个一个地删除它们(nub ys)。

虽然希望这有助于使代码union更加清晰，但真正的收获应该是等式推理是剖析 Haskell 代码的强大工具。不要害怕通过手动内联函数的定义来直接简化代码。

于 2013-10-08T02:49:50.083 回答
0

我不确定这是否union符合您的要求，但这很简单。我需要自己的功能来删除重复项。

rmdups ls = [d|(z,d)<- zip [0..] ls,notElem d $ take z ls]

它的作用与任何具有相同目的的递归函数相同。

union l1 l2 = let l = l1 ++ l2 in rmdups l
于 2018-05-06T19:05:47.057 回答