Mini-Project: Permuting a Sequence

We know how to sort a sequence of elements using Merge Sort or Quicksort in an imperative language. Merge Sort is just as efficient, and arguably more elegant, to implement in Haskell as in any imperative language. Quicksort poses some challenges if we want to avoid its worst-case quadratic running time, but it can be done.

What makes sorting "slow"—meaning, take more than linear time—is the need to compare the input elements to determine the order in which they are to be arranged. In some algorithms, we know the order in which the elements are to be permuted. In this case, the desired permutation can be constructed in linear time. For example, here is a function permute that does this in Python. It takes as input an array a to be permuted and an array pos that stores the position in the output array where every element in the array a is to be stored:

def permute(a, poss):
    perm = [None] * len(a)
    for (i, x) in enumerate(a):
        perm[poss[i]] = x
    return perm

Python

>>> def permute(a, poss):
...     perm = [None] * len(a)
...     for (i, x) in enumerate(a):
...         perm[poss[i]] = x
...     return perm
...
>>> permute(['a', 'b', 'c'],[2,0,1])
['b', 'c', 'a']

The Python implementation surely requires element-by-element updates of the perm array to populate it with the input elements in the correct order. However, since the positions of all elements are given in advance, we can in fact implement this function quite elegantly using Haskell's array function:

permute :: [a] -> [Int] -> [a]
permute xs poss = elems $ array (1, n) (zip poss xs)
  where
    n = length xs

GHCi

>>> :{
  | permute xs poss = elems $ array (1, n) (zip poss xs)
  |   where
  |     n = length xs
  | :}
>>> permute ['a', 'b', 'c'] [3,1,2]
"bca"

We zip together poss and xs, thereby pairing every element in the input list xs with its position that it should have in the output list. array then constructs an array from the resulting list of pairs where every element is stored in exactly the position it was assigned. We convert this back into a list of elements by extracting the elements of the array in order using elems. We have ourselves a linear-time permutation algorithm.