I was taking a look at some prelude functions to teach a workmate about recursion and I found that some are written in rather a weird way. Example:
{-# NOINLINE [1] zipWith #-}
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f = go
where
go [] _ = []
go _ [] = []
go (x:xs) (y:ys) = f x y : go xs ys
Why is it written as a call to go
where go
is defined right afterwards? IMO a more natural way to define it is:
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith _ [] _ = []
zipWith _ _ [] = []
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
I guess it is due to some inline / loop-fusion / lazy / whatever-feature that allow GHC
to optimize better, but this is the point in which Haskell becomes quite obscure to me. Can anyone explain (as easier as possible) the reason for such a function definition, if there is any.
Many comments, @AndrewRay's answer and in this question, point in the direction of inlining as the reason for such an auxiliar local function. Nevertheless, zipWith
is marked with the pragma NOINLINE [1] zipWith
, which, up to GHC's user guide: 7.13.5.5. Phase control, means to not inline before first phase and maybe inline afterwards (for whatever this means). In the linked question, the PO refers to foldr
which is implemented using the same trick but without any PRAGMA. I'd argue that the author is avoiding inlining but my knowledge in this is small.
added link to source definition of zipWith
As Willem Van Onsem mentioned in his comment, this means that f
doesn't need to be passed in each recursive call.
Your version of the function uses the recursive call zipWith f xs ys
. Because f
is an argument of zipWith
, it has to get passed repeatedly. This means that it isn't obvious from looking at zipWith
that f
never changes from one level of recursion to the next.
The Prelude
version uses the recursive call go xs ys
, which immediately signals that every recursive call to go
makes use of the same f
. Being able to immediately notice invariants like this helps us reason logically about our code.
EDIT: I had previously believed that inlining wasn't relevant here, but Carl and Daniel Wagner both point out that the thunk f
only needs to be evaluated once and substituted in the definition of go
, rather than being reevaluated for every recursion as would be the case in your definition of zipWith
.
You also mention loop-fusion, which is the process of merging adjacent traversal functions into a single traversal. Since this is already a single traversal, that doesn't apply here either.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With