Haskell：foldr/build fusionを（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パッケージにはすでに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をインポートする必要はありません。