Haskell：如何使 foldr/build 融合发生在 (zip [0..]) 中？

Question

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

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

但是，根据GHC.List as of base-4.9.1.0中zip的实现，这并不会完全进行列表融合，即实际上不会生成列表[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 package, as 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.

Answer 2

"Shortcut Fusion for Accumulating Parameters & Zip-like Functions

显示zip融合。简而言之，对于类似 zip 的函数，将使用对偶函数 unfoldr/destroy。

Haskell：如何使 foldr/build 融合发生在 (zip [0..]) 中？

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

haskell

list

ghc