In math, when I want to rearrange a list of length n, I'll act on the list with a permutation. For example:
(1 2) * (x, y, z) = (y, x, z) (1 n 2) * (v[1], v[2], ..., v[n]) = (v[n], v[1], ..., v[2]) perm * (v[1], v[2], ..., v[n]) = ( v[perm(1)], v[perm(2)], ..., v[perm(n)] ) How would I do this in Haskell?
I would use the input permutation to build a map from old indices to new indices.
import Prelude hiding ((*)) import qualified Data.Map as M infixr 5 * -- right-associative so we can compose permutations conveniently (*) :: [Int] -> [a] -> [a] perm * xs = zipWith (\i _ -> xs !! M.findWithDefault i i ixMap) [0..] xs where ixMap = M.fromList (zip perm (drop 1 perm ++ take 1 perm)) You can see it in action in the ghci prompt (though as usual in programming it uses 0-based rather than 1-based indexing):
> [0,1] * "xyz" "yxz" > [0,4,1] * "abcde" "eacdb" This costs O(n^2 log m) where n is the length of xs and m is the length of perm. You can reduce this to O(n log(nm)) by switching from (!!) to M.lookup for the indexing into xs, too.
[a] -> [a] new type to represent your permutation since then you could compose permutations. Something allowing (more or less) cycle [1,2,3] . cycle [3,7] $ [1..10].
[1,2,3] * [3,7] * [1..10]?cycle = (*), and then your syntax works just fine with no further newtypes nonsense.)cycle = (*) is a clever idea.
perm :: {1,2...,N} -> {1,2...,N}a bijection and so on. A O(N^2) algorithm should be rather simple, but your input in(1 n 2)is a rotational one, not a bijection. So decide: what's your actual input?nis bigger than3,(1 n 2)is a bijection that maps1 |-> n,n |-> 2,2 |-> 1, and all other values to themselves.