list - 从另一个列表中给定索引的列表元素中提取

Question

所以我需要从给定列表中提取具有另一个列表中给出的索引的元素。
签名应该是这样的:

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

和结果

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

据我所知，没有标准功能，我可以在更常见的带有循环的语言上做到这一点，但我对 haskell 不太擅长。

Answer 1

假设索引已排序，您可以编写自己的显式递归。

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

存在更多高级方法，但这应该是一种基本的有效替代方法。它以 O(n) 运行，其中 n 是列表的长度。

请注意，重复调用 !!而是需要 O(n^2) 时间，因为每个 !!成本 O(n)。

如果索引未排序，请使用 go (sort indices) 0 xs反而。成本增加到 O(n log n)。