Haskell中無限列表的編譯器優化？

我有t -> Maybe t類型的各種「部分排列」功能，要麼通過返回Just帶我到數據結構中的新位置，要麼返回Nothing，如果他們還沒有到達那裏。Haskell中無限列表的編譯器優化？

我經常必須重複特定的模式將這些部分的排列，構建所有的中間值的列表，但截斷列表每當我回到起始位置或置換失敗。

scan_partial_perms :: Eq t => [t -> Maybe t] -> t -> [t] 
scan_partial_perms ps v = map fromJust . takeWhile test $ scanl (>>=) (Just v) ps 
    where test (Just i) | i /= v = True 
      test _ = False 

iterate_partial_perm = scan_partial_perm . iterate 
cycle_partial_perms = scan_partial_perms perms . cycle

我相當有信心，有scanl在這種情況下所期望的嚴謹和尾遞歸特性。任何其他優化此代碼的提示？特別是，我應該閱讀關於-O3 -fllvm以外的哪些編譯器選項？

在最壞的情況，我可以像

perm l i = l !! i `rem` length l

定義的訪問函數替換scanl和無限的名單我想像這不能改善然而正確的優化性能。

來源

2012-01-21 Jeff Burdges

'-O3'意味着同樣的事情'-O2'。 – ehird

謝謝！另外，我是否應該將此代碼發佈到codereview.SE？ –

我認爲這非常適合SO，因爲這個問題相當具體。 – Owen

我認爲你有一個錯誤在scan_partial_perms，

scan_partial_perms ps v = map fromJust . takeWhile test $ scanl (>>=) (Just v) ps

scanl f s list總是s啓動，因此takeWhile test (scanl ...)是[]。如果這是故意的，那就很混亂。假設你想要的是

scan_partial_perms ps v = (v:) . map fromJust . takeWhile test . tail $ scanl (>>=) (Just v) ps

沒有什麼可以做的。您可以{-# SPECIALISE #-}它，因此Eq詞典消除了專門的換型。如果編譯器本身沒有這樣做（如果它可以看到使用站點的話），這會對你有所幫助。隨着GHC> = 7，可以改爲讓它{-# INLINABLE #-}，使其可以專門或許在每次使用網站內聯。

我不知道會發生什麼情況下來LLVM的道路，但在覈心級，map，fromJust和takeWhile尚未內聯，所以，如果你有足夠的絕望，你可以得到的，也許零點幾秒％的手動內聯他們，如果他們沒有在LLVM後端後內聯：

scan_partial_perms ps v = v : go v ps 
    where 
    go w (q:qs) = case q w of 
        Just z 
         | z /= v -> z : go z qs 
        _ -> [] 
    go _ _  = []

但這些都是非常便宜的功能，所以收益 - 如果在所有存在 - 將是小的。

所以，你有什麼比較好的已經，如果它不夠好，你需要攻擊不同的路線。

的一個與列表索引，

perm l i = l !! (i `rem` length l) 
-- parentheses necessary, I don't think (l !! i) `rem` length l was what you want

不好看。 length是昂貴的，(!!)是太昂貴，所以兩者一般應避免。

來源

2012-01-21 21:40:59

糟糕是我寫的版本會失敗。我會檢查出專門和可以接受的，謝謝！ –

Haskell中無限列表的編譯器優化？

回答

相關問題