Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 2 / a / Solution

Use the usual left-to-right pattern matching order:

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

The result stops when either list ends, so its length on finite total inputs is the smaller input length. Elements remaining in the longer list are discarded.

Strictness is asymmetric. Writing the bottom value as $\perp$, zip is strict in its first list but not uniformly strict in its second: zip undefined ys is undefined, whereas zip [] undefined = []. With a nonempty first list, an undefined second list does make the result undefined. Neither pair component is forced merely to produce the outer result constructor: zip [undefined] [undefined] already has a defined outer cons and pair. This follows from ordered pattern matching and lazy evaluation, not from the behavior on total lists alone.^[ref]