Geek Answers Handbook

Optimize List Indexing in Haskell

Let's say you have a very deterministic algorithm that creates a list, e.g. initsin Data.List. Is there a way that the Haskell compiler can optimally perform the “indexing” operation on this algorithm without actually generating all the intermediate results?

For example, it inits [1..] !! 10000runs quite slowly. Can the compiler somehow determine what it initswill produce on the 10000th element without any recursion, etc.? Of course, the same idea could be generalized outside the lists.

Edit: While it inits [1..] !! 10000is a constant, I'm curious about some kind of “index” operation on some algorithm. For example, can one optimize \i -> inits [1..] !! iin such a way that there is no recursion [or minimal] in order to achieve a result for anyone i?

+4
source share
1 answer

Yes and no. If you look at the definition Data.List.inits:

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

You will see that it is defined recursively. This means that each item in the resulting list is built on the previous item in the list. Therefore, if you need any n-th element, you need to collect all n-1 previous elements.

Now you can define a new function

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

. inits' [1..] !! 10000, , . , inits , .

, inits. , " ", .

+7

More articles:


All Articles