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.

Boar

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

Cyanogen

Indices are sorted so it's not a problem. Thank you for answer. – Boar

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

Soso

Second version of the function does not compile, mismatched types. – Boar

@Agent_0f_things: forgot an accent. Fixed now. – Soso

Answer 3

You can access lists' elements with the !! operator like this:

List!!index == value_at_that index

So, your function could look like the following:

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

Aleksandropol

Correct, however I'd remark that this is quite inefficient. List lookup being O (n), any repeated use of !! should be avoided. – Ecstatic

@leftaroundabout, well, yeah, but how else would one extract elements from a list given only indexes of these elements given that there seem to be no restrictions on the order of the indexes? If there were some, then improvements could've been made. – Aleksandropol

Sorting is only O (n · log n), so for sufficiently big lists it's more efficient to impose an ascending order (but also keep the information of how the order was originally), then use that to extract the elements, then sort back into the original order of requested indices. – Ecstatic

...alternatively, you can also convert the list into a more indexing-friendly structure (Vector or IntMap) and look up the indices from that, instead of the values-list itself. – Ecstatic

I know about !! operator just couldn't wrap my head aroung how to use it here properly. As far as i know indexes always come in ascending order however there can be "gaps" so to speak. And they should not go out of boundaries. – Boar

Answer 4

A library-based solution:

When faced with this sort of Haskell job, it is often a good idea to try to find a suitable library function for it. Unlike ad hoc manual recursion, an official library function can be trusted to interact smoothly with the idiosyncrasies of the Haskell runtime system.

Here, the job at hand seems well suited to the unfoldr library function:

unfoldr :: (st -> Maybe (a, st)) -> st -> [a]

The unfoldr function takes a) an initial state and b) a state transition function, which produces (maybe) a new state together with an output value.

Here, the state could consist of a triplet containing:

1. the depth into the initial list of values
2. the remaining part of the list of indices
3. the remaining part of the list of values

As a preliminary step, we assume temporarily that the list of indices is ordered, so we can process both lists in linear fashion (this restriction will get lifted further below).

This gives the following code:

import Data.List (unfoldr)

search1 :: [Int] -> [a] -> [a]
search1 indices xs  =  unfoldr  stepFn  state0
  where
    state0 = (0, indices, xs)
    stepFn (_, [], _)         =  Nothing  -- no indices left, hence the end
    stepFn (d, idx:idxs, xs)  =  let
                                      ofs  = idx - d
                                      rest = drop ofs xs
                                 in
                                      Just ( head rest,
                                            (idx, idxs, rest) )

Testing:

$ ghci
GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
 λ> 
 λ> :load q72853867.hs
 [1 of 1] Compiling Main             ( q72853867.hs, interpreted )
 Ok, one module loaded.
 λ> 
 λ> search1  [0,0,2,5,5,9,12]  [0..12]
 [0,0,2,5,5,9,12]
 λ> 

So that works. Now looking to lift the ordered indices restriction.

Allowing for unordered lists of indices:

The idea here is to sort the list of indices, but to do so in a way that keeps track of the rank occupied in the initial list by any given index. The idea is mentioned in a comment by @leftaroundabout .

So we can write a search2p auxiliary function which produces the requested values, but paired with their corresponding index ranks. Next, we provide a search2 wrapper function that restores the initial index order and discards the rank information:

import Data.List (unfoldr, sortBy)
import Data.Ord  (comparing)

search2p :: [Int] -> [a] -> [(Int,a)]
search2p indices xs  =  unfoldr  stepFn  state0
  where
    state0 = (0,  sortBy (comparing fst) (zip indices [(0::Int)..]),  xs)
    stepFn (_, [], _)         =  Nothing  -- no indices left, hence the end
    stepFn (d, (idx, rank):idxs, xs)  =  let
                                             ofs  = idx - d
                                             rest = drop ofs xs
                                         in
                                             Just ( (rank, head rest) ,
                                                    (idx, idxs, rest) )


search2 :: [Int] -> [a] -> [a]
search2 indices xs = map snd $ sortBy (comparing fst) $ search2p indices xs

Note: this is similar to a technique known in some circles as the decorate-sort-undecorate paradigm.

Testing:

 λ> 
 λ> search2p  [0,3,0,5,12,1,1]  [0..12]
 [(0,0),(2,0),(5,1),(6,1),(1,3),(3,5),(4,12)]
 λ> 
 λ> search2  [0,3,0,5,12,1,1]  [0..12]
 [0,3,0,5,12,1,1]
 λ> 

Amaras

Answer 5

A simple O(n) solution that allows for indices in an arbitrary order would be to first copy the list into an array, which allows for O(1) access by index, using the ! operation:

import qualified Data.Array as A

listToArray :: [a] -> Array Int a
listToArray xs = A.listArray (0, length xs - 1) xs

search :: [Int] -> [a] -> [a]
search indices list = map (array A.!) indices
  where array = listToArray list

or equivalently, using vectors

import qualified Data.Vector as V

search :: [Int] -> [a] -> [a]
search indices list = map (vec V.!) indices
  where vec = V.fromList list

The downside with this is that it copies the entire list, which can be slower in some cases, especially if the list of indices is short and most indices are in the beginning of the list, but most of the time it should be faster.

Protectionist