algorithm - 优化 Haskell 中的 "list"索引

Question

假设您有一个生成列表的非常确定性的算法，例如 Data.List 中的 inits。有什么方法可以让 Haskell 编译器在不实际生成所有中间结果的情况下优化地对该算法执行“索引”操作？

例如，inits [1..] !! 10000 非常慢。编译器能否以某种方式推断出 inits 将在第 10000 个元素上产生什么而无需任何递归等？当然，同样的想法可以推广到列表之外。

编辑:虽然初始化[1..]! 10000 是常数，我想知道对某些算法的任何“类索引”操作。例如，可以 \i -> inits [1..] !! i 进行优化，以便不执行 [或最小] 递归来获得任何 i 的结果？

Answer 1

是也不是。如果您查看 Data.List.inits 的定义:

inits                   :: [a] -> [[a]]
inits xs                =  [] : case xs of
                                  []      -> []
                                  x : xs' -> map (x :) (inits xs')

您会看到它是递归定义的。这意味着结果列表的每个元素都建立在列表的前一个元素之上。所以如果你想要任何第 n 个元素，你必须构建所有 n-1 个前面的元素。

现在你可以定义一个新函数了

inits' xs = [] : [take n xs | (n, _) <- zip [1..] xs]

具有相同的行为。如果您尝试使用 inits' [1..] !! 10000，它很快完成，因为列表的连续元素不依赖于前面的元素。当然，如果您实际上试图生成一个 init 列表而不是单个元素，这会慢得多。

编译器必须知道很多信息才能优化 inits 等函数的递归。也就是说，如果一个函数真的“非常确定”，那么以非递归方式重写它应该是微不足道的。