Permutation of a list in haskell

Question

We are given two lists xs :: [a] and ys :: [Int]. For example:

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

We have to generate a new list zs :: [a], such that zs is a permutation of xs generated using ys. For above example:

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

Explanation: "random" occurs at 2nd position in xs, "text" occurs on the 3rd position and "some" occurs on the 1st position.

Till now, I have arrived at this solution:

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]

Is there a better definition for f which will avoid use of array? I am looking for memory efficient solutions. Array is a bad choice if xs is say a large list of big strings. Time complexity of f could be relaxed to O(n log n).

Answer 1

Simply sorting twice, back and forth, does the job:

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

So that

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

(using the idea from this answer).

Since we sort on Int indices the both times, you can use some integer sorting like radix sort, for an O(n) solution.