Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why are some Prelude functions defined in terms of a locally defined function? [duplicate]

Tags:

haskell

ghc

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.

Edits

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.

Edit 2

added link to source definition of zipWith

like image 273
lsmor Avatar asked Nov 12 '19 11:11

lsmor


1 Answers

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.

like image 66
Andrew Ray Avatar answered Nov 12 '22 07:11

Andrew Ray