Haskell中列表的排列

Question

我们得到两个列表xs :: [a]和ys :: [Int]。例如：

xs = ["some", "random", "text"]
ys = [2, 3, 1]

我们必须生成一个新列表zs :: [a]，它zs是xs生成 using的排列ys。对于上面的例子：

zs = ["random", "text", "some"]

解释：“random”出现在第 2 个位置xs，“text”出现在第 3 个位置，“some”出现在第一个位置。

到目前为止，我已经找到了这个解决方案：

f :: [a] -> [Int] -> [a]
f xs ys = getList (listArray (1, n) xs) ys where
  n = length xs
  getList :: Array Int a -> [Int] -> [a]
  getList a ys = [ a ! x | x <- ys]

是否有更好的定义f可以避免使用数组？我正在寻找内存高效的解决方案。如果xs说一大串大字符串，数组是一个糟糕的选择。的时间复杂度f可以放宽到O(n log n).

Answer 1

只需来回排序两次即可完成此工作：

import Data.Ord
import Data.List

f :: [a] -> [Int] -> [a]
f xs = map fst . sortBy (comparing snd) . zip xs . 
       map fst . sortBy (comparing snd) . zip ([1..] :: [Int]) 

以便

Prelude Data.Ord Data.List> f ["some", "random", "text"] [2, 3, 1]
["random","text","some"]

（使用这个答案的想法）。

Int由于我们两次都对索引进行排序，因此您可以使用一些整数排序（例如基数排序）来获得O(n)解决方案。