Excerpt from list items with indices in another list

Question

Therefore, I need to extract items from this list with the indices listed in another list. The signature should be something like this:

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

and result

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

As far as I know, there are no standard functions for this, I can do it in more common languages ​​with loops, but I'm not so good with haskell.

Answer 1

Assuming the indexes 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

Higher-level approaches exist, but this should be a basic effective alternative. It works in O (n), where n is the length of the lists.

, !! O (n ^ 2), !! O (n).

, go (sort indices) 0 xs. O (n log n).

Answer 2

(!!) :: [a] -> Int -> Int , :

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

(!!) O (k) k , .

, , Haskell :

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

Answer 3

!! operator :

List!!index == value_at_that index

, :

search indexes list = [list!!x | x <- indexes]