首页 文章

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

提问于
浏览
7

我正在阅读learn you a 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)将不匹配,将通过附加空列表[]来完成递归 .

  • 我个人更喜欢第二个版本的可读性,但也许这样做我错了 .

  • 它对方法的性能有影响吗?据我所知,如果最顶层的模式不匹配,Haskell将检查下一个模式 . 模式的顺序是否会影响性能?

亲切的问候,

Edit:

可能重复:Haskell GHC: what is the time complexity of a pattern match with N constructors?

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

1 回答

  • 7

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

    几乎;除外:

    \> 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
    

    换句话说,第二个定义总是强制两个参数weak head normal form .

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

相关问题