优化Haskell中的“列表”索引

Question

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

例如，inits [1..] !! 10000非常慢。编译器能以某种方式推断出inits会在第10000个元素上产生什么，而不需要任何递归等等？当然，这一想法也可以推广到清单之外。

编辑：虽然inits [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这样的函数的递归。也就是说，如果一个函数真的是“非常确定的”，那么用一种非递归的方式重写它应该是微不足道的。