Extract from a list elements with indexes given in another list

Question

So I need to extract elements from given list with indexes that are given in another list. Signature supposed to be something like this:

search :: [Int] -> [a] -> [a]

and the result

search [1,3,5] [34,65,67,34,23,43,54]
[65,34,43]

As far as I know there is no standard functions for this, I can do this on more common languages with cycles, but I'm not that good with haskell.

Answer 1

Assuming the indices are sorted, you can write your own explicit recursion.

search :: [Int] -> [a] -> [a]
search indices xs = go indices 0 xs  -- start from index 0
   where
   go :: [Int] -> Int -> [a] -> [a]
   -- no more indices, we are done
   go []     _ _                = []
   -- more indices but no more elements -> error
   go _      _ []               = error "index not found"
   -- if the wanted index i is the same as the current index j,
   -- return the current element y, more to the next wanted index
   go (i:is) j yys@(y:_) | i==j = y : go is  j     yys
   -- otherwise, skip y and increment the current index j
   go iis    j (_:ys)           =     go iis (j+1) ys

More high-level approaches exist, but this should be a basic efficient alternative. It runs in O(n), where n is the length of the lists.

Note that repeatedly calling !! would instead require O(n^2) time, since each !! costs O(n).

If the indices are not sorted, use go (sort indices) 0 xs instead. The cost increases to O(n log n).

Answer 2

One can use the (!!) :: [a] -> Int -> Int operator and list comprehension to achieve this like:

search :: [Int] -> [a] -> [a]
search js xs = [xs!!j | j <- js]

But the (!!) operator works in O(k) with k the requested index, so this will be inefficient.

Given the list of indices is ordered and does not go out of bounds, a pure Haskell function could be the following:

search :: [Int] -> [a] -> [a]
search = search' 0
    where search' _ []     _  = []
          search' i (j:js) xs = y : search' (j+1) js ys
              where (y:ys) = drop (j-i) xs