Haskell Template Compatibility: Readability and Performance

Question

I go through a haskell tutorial and I turn off some of the author’s examples.

For example, it overrides zip as follows:

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

He uses a similar approach for all his other examples, where he first puts the most specific patterns. Here are a few versions of the zip function:

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

As far as I understand, both methods do the same. If an empty list is provided in any case (x: xs) or (y: ys) does not match what ends the recursion by adding an empty list [].

• I personally prefer the second version for readability, but maybe I'm wrong about that.
• Does this affect the effectiveness of the method? As far as I understand, if the topmost template does not match, Haskell will check the next template. Does pattern order describe performance?

Yours faithfully,

Edit:

Duplication possible: Haskell GHC: what is the time complexity of matching patterns with N constructors?

Summary: The order of the patterns is very important for semantics (in terms of strict evaluation of the arguments) and the readability of the function. Pattern matching itself will always have O (1) time complexity.

Answer 1

As far as I understand, both methods do the same.

nearly; with the exception of:

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

then:

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

In other words, the second definition always forces a weak head normal form for both arguments.

In terms of performance, this means that it is possible to construct such a pathological example that WHNF involves heavy calculations, so one definition is performed very differently than another.