Оптимизировать индексирование «списка» в 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. Тем не менее, если функция действительно «очень детерминированная», ее тривиально переписывать нерекурсивным образом.