Haskell中的联合函数

Question

我一直在Haskell中编写代码,但无法理解实现union函数的想法.我还发现了一些嵌入在Haskell平台中的函数定义.但问题是我需要一种简洁易懂的方法来使其发挥作用.任何人都可以帮助我吗？

Answer 1

假设你在谈论union :: Eq a => [a] -> [a] -> [a]这需要两个输入列表,并返回一个包含了所有每个参数列表元素的第三列表中,那么它的定义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

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

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

现在这个定义可能更具可读性.所述union的xs和ys被xs附加到唯一的(" nub床")的值ys已经由处理foldl (flip delete) _ xs.的是,净结果foldl是逐个尝试delete的每个元素xs由(nub ys).最终意义的union xs ys是xs附加到每个独特元素,而ys不是那些元素 xs.

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

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

这有点令人失望,是[]用来表示类似Set概念的结果union.但是,如果我们使用Set.fromList那时查看结果,我们就可以了.

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技巧如何运作？让我们打开定义foldl来看,再次滥用等式推理.

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

这应该使技巧更明显 - 它循环的元素xs,从一个接一个地删除它们(nub ys).

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