Haskell模式匹配:可读性和性能

Question

我正在通过学习你的haskell教程,我一直在嘲笑作者给出的一些例子.

例如,他重新实现zip如下:

zip' :: [a] -> [b] -> [(a,b)]  
zip' _ [] = []  
zip' [] _ = []  
zip' (x:xs) (y:ys) = (x,y):zip' xs ys

他对所有其他例子采用了类似的方法,他将最具体的模式放在第一位.这是一个略有不同的zip函数版本:

zip' :: [a] -> [b] -> [(a,b)]
zip' (x:xs) (y:ys)  = (x, y):zip' xs ys
zip' _ _            = []

据我所知,两种方法都做同样的事情.如果提供空列表(x:xs)或(y:ys)将不匹配,将通过附加空列表[]来完成递归.

1. 我个人更喜欢第二个版本的可读性,但也许我这样做是错的.
2. 它对方法的性能有影响吗？据我所知,如果最顶层的模式不匹配,Haskell将检查下一个模式.模式的顺序是否会影响性能？

亲切的问候,

编辑:

可能重复: Haskell GHC:模式与N个构造函数匹配的时间复杂度是多少？

简介:模式的顺序对于语义(在严格评估参数方面)和函数的可读性非常重要.模式匹配本身将始终处于O(1)时间复杂度.

Answer 1

据我所知,两种方法都做同样的事情.

几乎; 除外:

\> zip' undefined []   -- 1st definition of zip'
[]
\> zip' (filter (< 4) [1..]) [1, 2, 3]
[(1,1),(2,2),(3,3)]

然而:

\> zip' undefined []   -- 2nd definition of zip'
*** Exception: Prelude.undefined
\> zip' (filter (< 4) [1..]) [1, 2, 3]
[(1,1),(2,2),(3,3)   -- gets stuck here; never returns

换句话说,第二个定义总是迫使弱头部正常形态的两个参数.

在性能方面,这意味着可以构建一个病态示例,使得WHNF涉及大量计算,因此一个定义与另一个定义的表现非常不同.