我应该在哪里以及为什么要使用额外的空图案

Question

例如:

intersectBy : (a -> a -> Bool) -> List a -> List a -> List a
intersectBy _  [] _     =  []
intersectBy _  _  []    =  []
intersectBy eq xs ys    =  [x | x <- xs, any (eq x) ys]

有额外的模式[],似乎它们在Haskell中使用,Data.List但是那是什么样的优化？和伊德里斯在哪里有区别？

我问,因为我听说"这将使得它更难以推理",而且说我的人没有时间完全解释它.

我怀疑我是否能理解"减少功能的证据".

有人可以从哈斯克尔和伊德里斯的位置向我解释额外模式的政治,这样我就能理解并看到差异.

Answer 1

从语义上讲,模式

intersectBy _  [] _     =  []

即使从性能的角度来看,看起来也是多余的.相反,在Haskell中

intersectBy _  _  []    =  []

否则不是多余的

intersectBy (==) [0..] []

因为理解会试图尝试所有的元素,所以会发散x <- [0..].

不过,我不确定我是否喜欢这种特殊情况.为什么我们不应该添加一个特殊的案例,intersectBy (==) [0..] [2]以便它返回[2]？此外,如果考虑性能,在许多情况下我想通过预排序使用O(n log n)方法,即使这不适用于无限列表并且需要Ord a.

Answer 2

通过git blameGHC Trac和图书馆邮件列表查询历史记录时,无需猜测.

最初的定义只是第三个等式,

intersectBy eq xs ys    =  [x | x <- xs, any (eq x) ys]

在https://github.com/ghc/ghc/commit/8e8128252ee5d91a73526479f01ace8ba2537667中,添加了第二个等式作为严格性/性能改进,同时添加了第一个等式,以使新定义始终至少为定义为原始.否则,intersectBy f [] _|_将_|_在[]以前.

在我看来,这个当前的定义现在是最大的懒惰:它对于任何输入都是尽可能定义的,除了必须首先选择是否检查左侧或右侧列表的空白.(并且,正如我上面提到的,这种选择与历史定义一致.)

Answer 3

@chi解释了这个_ _ []案例,但也_ [] _有一个目的:它决定了intersectBy 句柄bottom.定义如下:

?. intersectBy undefined    []     undefined
[]
?. intersectBy   (==)    undefined    []
*** Exception: Prelude.undefined

删除第一个模式,它变为:

?. intersectBy undefined undefined    []
[]
?. intersectBy   (==)       []     undefined
*** Exception: Prelude.undefined

我不是100%肯定这一点,但我相信在第一种模式中没有绑定任何东西也有性能优势.最终的格局将产生相同的结果为xs == []不评估 eq或ys,但据我所知它仍然分配堆栈空间为他们的thunk.