Haskell: How to make foldr/build fusion happen in (zip [0..])?

Question

In Haskell, we can use this useful idiom to get from a list that of indexed elements in it:

indexify :: (Num i) => [a] -> [(i,a)]
indexify = zip [0..]

However, according to the implementation of zip in GHC.List as of base-4.9.1.0, this will not completely perform list fusion, i.e. this will not actually generate the list [0..], but the argument list to indexify will be constructed.

Of course, there is a definition that allows appropriate list fusion:

indexify' :: (Num i) => [a] -> [(i,a)]
indexify' xs = build $ \c n ->
                foldr (\x r !i -> (i,x) `c` r (i+1)) (const n) xs 0

Do we need to import GHC.Prim (build) to do this? Or is there another implementation that simplifies to indexify'?

Answer 1

This already exists in the ilist package, as indexed. The relevant source code snippets are

import GHC.Exts  -- exports `build`

indexed :: [a] -> [(Int, a)]
indexed xs = go 0# xs
  where
    go i (a:as) = (I# i, a) : go (i +# 1#) as
    go _ _ = []
{-# NOINLINE [1] indexed #-}

indexedFB :: ((Int, a) -> t -> t) -> a -> (Int# -> t) -> Int# -> t
indexedFB c = \x cont i -> (I# i, x) `c` cont (i +# 1#)
{-# INLINE [0] indexedFB #-}

{-# RULES
"indexed"       [~1] forall xs.    indexed xs = build (\c n -> foldr (indexedFB c) (\_ -> n) xs 0#)
"indexedList"   [1]  forall xs.    foldr (indexedFB (:)) (\_ -> []) xs 0# = indexed xs
  #-}

As you'll probably notice, the rewrite rule makes use of pretty much the same definition you have, so that probably is the best way to do it. Also, GHC.Exts also exports build, so you don't need to import GHC.Prim.