优化Haskell中的"列表"索引

Question

假设你有一个非常确定的算法产生一个列表,就像inits在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,它会很快完成,因为列表的连续元素不依赖于以前的元素.当然,如果你实际上是在尝试生成一个inits列表而不是一个单独的元素,那么这将会慢得多.

编译器必须知道很多信息才能从函数中优化掉递归inits.也就是说,如果函数确实是"非常确定的",那么以非递归的方式重写它应该是微不足道的.