p is a (type class polymorphic) function taking a permutation as a list of
Ints, and a nested list representing a multidimensional array of
p [2,1] [[10,20,30],[40,50,60]], however if type defaulting doesn't succeed, you may have to add a type annotation like
:: [[Int]] (nested appropriately) giving the type of the result.
class P a where p::[Int]->[a]->[a]
instance P Int where p _=id
instance P a=>P[a]where p(x:r)m|n<-p r<$>m,y:z<-sort r=last$n:[p(x:z)<$>transpose n|x>y]
Try it online!
Golfing challenges with nested arrays of arbitrary depth are a bit awkward in Haskell, because the static typing tends to get in the way. While Haskell lists (with the exact same syntax as in the challenge description) can be nested just fine, lists of different nesting depth are of incompatible types. Also, standard Haskell parsing functions require knowing the type of the value you are trying to parse.
As a result, it seems inevitable that the program needs to include type-related declarations, which are relatively verbose. For the golfed part, I settled on defining a type class
P, such that
p can be polymorphic over the type of the array.
Meanwhile, the TIO's testing harness shows a way to get around the parsing problem.
How it works
To sum up the essence of this algorithm: It performs a bubble sort on the permutation list, transposing neighboring dimensions when the corresponding permutation indices are swapped.
As given by the
class P a declaration, in any instance,
p takes two arguments, a permutation (always of type
[Int]) and an array.
- The permutation can be given in the form in the challenge description, although the way the algorithm works, the choice of indices is arbitrary, except for their relative order. (So both 0- and 1- based work.)
- The base
instance P Int handles arrays of dimension 1, which
p simply returns unchanged, since the one dimension can only be mapped to itself.
- The other
instance P a => P [a] is defined recursively, calling
p with dimension n subarrays in order to define it for dimension n+1 arrays.
p(x:r)m first calls
p r recursively on every element of
m, giving a result array
n in which all dimensions except the first have been permuted correctly relatively to each other.
- The remaining permutation that needs to be performed on
n is given by
x:y:z = x:sort r.
x<y then the first dimension of
n is already correctly placed, and
n is simply returned.
x>y, then the first and second dimension of
n need to be swapped, which is done with the
transpose function. Finally
p(x:z) is applied recursively to every element of the result, ensuring the original first dimension is transposed to the right position.