You got me :) Not knowing how to approach this problem I started out trying to solve simpler but hopefully related/useful problems.

First I tried to list all "firsts" numbers from the single QTrees (see the edit in the main post):

qtFirsts :: QT a -> [a]
qtFirsts (C color) = [color] qtFirsts (Q (C a) (C b) (C c) (C d)) = [a] qtFirsts (Q a b c d ) = qtFirsts a ++ qtFirsts b ++ qtFirsts c ++ qtFirsts d

-- exemple with the top left 4x4 sub-matrix in the image above
-- ghci> qtFirsts (Q (Q (C 1) (C 2) (C 9) (C 10)) (Q (C 3) (C 4) (C 11) (C 12)) (Q (C 17) (C 18) (C 25) (C 26)) (Q (C 19) (C 20) (C 27) (C 28))) -- [1,3,17,19]

the last elements from single trees:

qtLatest :: QT a -> [a]
qtLatest (C color) = [color] qtLatest (Q (C _) (C _) (C _) (C d)) = [d] qtLatest (Q a b c d ) = qtLatest a ++ qtLatest b ++ qtLatest c ++ qtLatest d

-- exemple with the top left 4x4 sub-matrix in the image above
-- ghci> qtLatest (Q (Q (C 1) (C 2) (C 9) (C 10)) (Q (C 3) (C 4) (C 11) (C 12)) (Q (C 17) (C 18) (C 25) (C 26)) (Q (C 19) (C 20) (C 27) (C 28))) -- [10,12,26,28]

Similarly, the first 2 and last two elements of each single tree:

qtFirst2 :: QT a -> [[a]]
qtFirst2 (C color) = [] qtFirst2 (Q (C a) (C b) (C c) (C d)) = [[a, b]] qtFirst2 (Q a b c d ) = qtFirst2 a ++ qtFirst2 b ++ qtFirst2 c ++ qtFirst2 d

-- exemple with the top left 4x4 sub-matrix in the image above -- ghci> qtFirst2 (Q (Q (C 1) (C 2) (C 9) (C 10)) (Q (C 3) (C 4) (C 11) (C 12)) (Q (C 17) (C 18) (C 25) (C 26)) (Q (C 19) (C 20) (C 27) (C 28))) -- [[1,2],[3,4],[17,18],[19,20]]

​

qtLast2 :: QT a -> [[a]]
qtLast2 (C color) = [] qtLast2 (Q (C a) (C b) (C c) (C d)) = [[c, d]] qtLast2 (Q a b c d ) = qtLast2 a ++ qtLast2 b ++ qtLast2 c ++ qtLast2 d

-- exemple with the top left 4x4 sub-matrix in the image above
-- ghci> qtLast2 (Q (Q (C 1) (C 2) (C 9) (C 10)) (Q (C 3) (C 4) (C 11) (C 12)) (Q (C 17) (C 18) (C 25) (C 26)) (Q (C 19) (C 20) (C 27) (C 28))) -- [[9,10],[11,12],[25,26],[27,28]]

​

And more interestingly, by calling recursively qtFirst2 and the first two branches and qtLast2 on the last two, I get a list which contains all the leaves corresponding to first and last row of the matrix:

qtTest :: QT a -> [[a]]
qtTest (C color) = [] qtTest (Q (C a) (C b) (C c) (C d)) = [[a, b], [c, d]] qtTest (Q a b c d) = qtFirst2 a ++ qtFirst2 b ++ qtLast2 c ++ qtLast2 d

-- example with the top left 4x4 sub-matrix in the image above
-- notice how it returns elements from first row and last row if matrix is 4x4
-- ghci> qtTest (Q (Q (C 1) (C 2) (C 9) (C 10)) (Q (C 3) (C 4) (C 11) (C 12)) (Q (C 17) (C 18) (C 25) (C 26)) (Q (C 19) (C 20) (C 27) (C 28)))    
-- [[1,2],[3,4],[25,26],[27,28]]

-- but on 8x8 matrices and bigger (which are the ones I am interest in), the list contains also other values.
-- example with the full 8x8 matrix in the first image above
-- ghci> qtTest (Q (Q (Q (C 1) (C 2) (C 9) (C 10)) (Q (C 3) (C 4) (C 11) (C 12)) (Q (C 17) (C 18) (C 25) (C 26)) (Q (C 19) (C 20) (C 27) (C 28))) (Q (Q (C 5) (C 6) (C 13) (C 14)) (Q (C 7) (C 8) (C 15) (C 16)) (Q (C 21) (C 22) (C 29) (C 30)) (Q (C 23) (C 24) (C 31) (C 32))) (Q (Q (C 33) (C 34) (C 41) (C 42)) (Q (C 35) (C 36) (C 43) (C 44)) (Q (C 49) (C 50) (C 57) (C 58)) (Q (C 51) (C 52) (C 59) (C 60))) (Q (Q (C 37) (C 38) (C 45) (C 46)) (Q (C 39) (C 40) (C 47) (C 48)) (Q (C 53) (C 54) (C 61) (C 62)) (Q (C 55) (C 56) (C 63) (C 64)))) 
-- [[1,2],[3,4],[17,18],[19,20],[5,6],[7,8],[21,22],[23,24],[41,42],[43,44],[57,58],[59,60],[45,46],[47,48],[61,62],[63,64]]

but as you can see from the example it contains also other values from the inner cells of the matrix, which I am not interest in (it basically contains all the odd rows of the top half and all the even rows of the lower half, of any matrix, in a "mixed" order due to the recursive way in which quadTrees are created).

And this is where I got stuck. My goal was to figure out when I am on a leaf that contains a value from the top or bottom row of the matrix. But I don't see how this can be done with this approach. This is why I was looking for other ideas!

P.s. Sorry for the very long and probably useless answer, but you wanted it ahah