Behaviour of overlapping instances in recursive list transform

Question

Overlapping instances are not prioritised as intended in my recursive list transform.

I am trying to create a transpose function that operates on nested lists of arbitrary depth. The goal is to have two functions, one which can transpose the 'highest dimension' down to the 'lowest', that is, a nested list with dimensions [a, b, c] would be transformed into a nested list with the dimensions [b, c, a], and one which does the opposite, [a, b, c] to [c, a, b].

{-# LANGUAGE FlexibleContexts, FlexibleInstances #-}
module Transpose where
import Data.List

class DeepTranspose a where
    deepTransposeDown :: a -> a
    deepTransposeUp   :: a -> a

instance {-# OVERLAPPING #-} (DeepTranspose a) => DeepTranspose [[a]] where
    deepTransposeDown = map deepTransposeDown.transpose
    deepTransposeUp   = transpose.map deepTransposeUp

instance {-# OVERLAPPABLE #-} DeepTranspose a where
    deepTransposeDown = id
    deepTransposeUp   = id

My intention is that the first instance is applied to all nested lists, and that the second instance is applied to everything else.

Below are some examples of tests, 'ref' indicates the intended behaviour of the function

a = [[1,2],[3,4]] :: [[Int]]
b = [[[1,2],[3,4]],[[5,6],[7,8]]] :: [[[Int]]]
c = [[[[1,2],[3,4]],[[5,6],[7,8]]],[[[9,10],[11,12]],[[13,14],[15,16]]]] :: [[[[Int]]]]

ref1a = transpose a
test1a = deepTransposeDown a
ref1b = map transpose.transpose $ b
test1b = deepTransposeDown b
ref1c = map (map transpose.transpose).transpose $ c
test1c = deepTransposeDown c

ref2a = transpose a
test2a = deepTransposeUp a
ref2b = transpose.map transpose $ b
test2b = deepTransposeUp b
ref2c = transpose.map (transpose.map transpose) $ c
test2c = deepTransposeUp c

The results of the reference and the test are different however, for example:

>>>c
[[[[1,2],[3,4]],[[5,6],[7,8]]],[[[9,10],[11,12]],[[13,14],[15,16]]]]
>>>ref1c
[[[[1,9],[2,10]],[[3,11],[4,12]]],[[[5,13],[6,14]],[[7,15],[8,16]]]]
>>>test1c
[[[[1,2],[3,4]],[[9,10],[11,12]]],[[[5,6],[7,8]],[[13,14],[15,16]]]]

I don't have much experience using overlapping instances, so I am unsure of how the choice of instance is made. To me it appears as though transposition only occurs in the first 'layer' after which the second instance (id) is used. This effectively turns it into the normal transpose, which is not very interesting.

Answer 1

I don't completely understand what's going on, but you need

instance {-# OVERLAPPING #-} (DeepTranspose [a]) => DeepTranspose [[a]] where
                                         -- ^^^ --

This is because in your instance map deepTransposeDown.transpose needs DeepTranspose [a]. If you only require DeepTranspose a, that's not enough to satisfy the required constraint, so it falls back to the id instance (even if a=[[Int]]).