Finding all the indexes of some elements on a given list. Can it be done in less than O(n^2) without arrays in Haskell?

Question

Given 2 lists of unique, orderable, non-contiguous elements, say:

['d', 'a', 'z', 'b']

I want to find their index in another list, say:

['a', 'b', 'z', 'd']

The result would be a list with their positions:

[3, 0, 2, 1]  -- element at 0 is at 3,
              -- element at 1 is at 0, etc.

Answer 1

This can be also done in O(n log n) time with a couple of sorts. I assume that the second list is a permutation of the first one.

import Data.List
import Data.Ord
import Data.Function

correspIx :: Ord a => [a] -> [a] -> [(Int, Int)]
correspIx = zip `on` map fst . sortBy (comparing snd) . zip [0..]

correspIx returns a list of pairs with the indices corresponding to each other:

correspIx "dazb" "abzd" == [(1,0),(3,1),(0,3),(2,2)]

We need another sort to get the result indicated in the question:

correspIx' :: Ord a => [a] -> [a] -> [Int]
correspIx' xs ys = map snd $ sortBy (comparing fst) $ correspIx xs ys

Now correspIx' "dazb" "abzd" == [3,0,2,1].