Haskell:如何在(zip [0 ..])中进行foldr/build fusion？

Question

在Haskell中,我们可以使用这个有用的习惯用法从列表中获取索引元素:

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

然而,根据实施zip中GHC.List作为base-4.9.1.0,这将不能完全执行的操作列表的融合,即,这实际上不会产生列表[0 ..],但参数列表indexify将被构造.

当然,有一个允许适当的列表融合的定义:

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

我们需import GHC.Prim (build)要这样做吗？或者是否有其他实现简化为indexify'？

Answer 1

这已经存在于ilist包中,如indexed.相关的源代码片段是

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
  #-}

正如您可能会注意到的,重写规则使用了几乎相同的定义,因此这可能是最好的方法.另外,GHC.Exts还可以导出build,因此您无需导入GHC.Prim.