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.
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).