하스켈 : foldr/build fusion을 만드는 방법은 (zip [0 ..])?

하스켈에서 우리는 그것에서 그 인덱스 요소 목록에서 얻을이 유용한 관용구를 사용할 수 있습니다하스켈 : foldr/build fusion을 만드는 방법은 (zip [0 ..])?

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'으로 단순화 된 다른 구현이 있습니까?

출처

2017-01-29 gksato

'indexify = snd의 f! i x = (i + 1, (i, x))를 되 돌리시겠습니까? mapAccumL f를 0' 작품? 나는'mapAccumL'이 융합의 대상이된다고 생각합니다. – Alec

@Alec 귀하의 의견을 대답으로 바꾸고 받아들이려고했지만 작동하지 않습니다. 'mapAccumL'은'traverse = mapM'의 용어로 정의되고, "소비"방향으로 융합됩니다 (즉,'foldr'을 사용합니다). 그러나 그것은 "생산"방향으로 융합하지 않습니다 (즉' 빌드'). – gksato

아. 좋은 지적. 그 생각을 했어야 했어. 'zip'보다 약간 더 낫습니다. :) – Alec

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을 가져올 필요가 없습니다.

출처

2017-01-29 03:58:44 Alec

하스켈 : foldr/build fusion을 만드는 방법은 (zip [0 ..])?

답변

관련 문제