Question 3-3

Write a Haskell function select, which takes a list indices of integers (which you may assume is in increasing order) and another list data, and it returns the items of data at the indices mentioned in indices. For example, select [1,2,4] [10..20] would return [11,12,14], since 11 is at position 1 in the list [10..20] (we start numbering positions from 0), 12 at position 2, and 14 at position 4. Your function should be able to work in O(n) time, where n is the length of data.

Solution

selectSub [] _ _ = []
selectSub (i:is) (x:xs) pos =
    if pos == i then x : selectSub is xs (pos + 1)
                else selectSub (i : is) xs (pos + 1)

select indices data = selectSub indices data 0