Haskell 中无限列表的编译器优化？

Question

我有各种 t -> 类型的“部分排列”函数也许 t 要么通过返回 Just 将我带到数据结构中的新位置，要么返回 Nothing（如果它们还无法到达那里）。

我通常必须以重复的特定模式应用这些部分排列，构建所有中间值的列表，但每当我返回到起始位置或排列失败时，就会截断该列表。

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 之外，我还应该阅读哪些编译器选项？

在最坏的情况下，我可以用定义的访问器函数替换 scanl 和无限列表，就像

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

我想象的那样，但这不能通过正确的优化来提高性能。

Answer 1

我认为你在 scan_partial_perms 中有一个错误，

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

scanl fs list 总是以 s 开头，所以 takeWhile test (scanl ...) 是[]。如果这是故意的，那就太混乱了。假设你想要什么，

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

你无能为力。您可以{-# SPECIALIZE #-} 它，以便消除专门用于类型的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 很昂贵，(!!) 也很昂贵，因此通常应该避免两者。