Occurs check: cannot construct the infinite type?

Question

I'm trying to write a function that, given two quadtrees representing images, will output another boolean quadtree "mask", with value True for a pixel if both quadtrees have the same color the corresponding position, and False otherwise.

I'm getting this error:

Occurs check: cannot construct the infinite type: a = QT a
  Expected type: QT (QT a)
  Inferred type: QT a
In the second argument of `mask', namely `c2'
In the first argument of `Q', namely `(mask a c2)'

and can't understand why. The function is:

data (Eq a, Show a) => QT a = C a | Q (QT a) (QT a) (QT a) (QT a)
    deriving (Eq, Show)

mask :: (Eq a, Show a) => QT a -> QT a -> QT Bool
mask q1 q2 = m q1 q2
    where
    m (C c1) (C c2) = C (c1 == c2)
    m (Q (C a) (C b) (C c) (C d)) (Q (C e) (C f) (C g) (C h))
        | and $ zipWith (==) [a, b, c, d] [e, f, g, h] = C True
        | otherwise = Q (mask a e) (mask b f) (mask c g) (mask d f)
    m (Q a b c d) (C c2)   = Q (mask a c2) (mask b c2) (mask c c2) (mask d c2)
    m c@(C _) q@(Q _ _ _ _) = mask q c
    m (Q a b c d) (Q e f g h) = Q (mask a e) (mask b f) (mask c g) (mask d h)

Answer 1

c2 has type a, but mask wants an argument of type QT a. You should use an @ pattern like you do on the line below it:

m (Q a b c d) c2@(C _)   = Q (mask a c2) (mask b c2) (mask c c2) (mask d c2)

I think the previous line also has the same problem.

Answer 2

You didn't quite ask this, but.. this line:

m (Q (C a) (C b) (C c) (C d)) (Q (C e) (C f) (C g) (C h))

It just...

Many years ago me and a friend learned to program in BASIC. He created a very cool spaceships game. I told him that he should add more spaceships, and that would be cooler. He said that it was hard work. Turns up he didn't know about arrays and had code duplication for each of the 8 ships on the screen.

Please make cleaner code, something like this:

data SplitTree a = Leaf a | SplitNode [SplitTree a]
  deriving (Eq, Show)

mask :: Eq a => SplitTree a -> SplitTree a -> SplitTree Bool
mask (Leaf x) (Leaf y) = Leaf (x == y)
mask (SplitNode xs) (SplitNode ys)
  | and $ zipWith (==) xs ys = Leaf False
  | otherwise = SplitNode $ zipWith mask xs xs

(I'm not 100% sure that this is what you were trying to do, but I may or may not have purposefully introduced some simple bugs into this code as I don't like doing homework)

Writing good code makes it easier to get it correct. If it's not correct, then the bugs are easier to find.

It's hard to help you with that mess. The easiest way to fix such a mess is a rewrite. Isn't that a waste?

Before you go solving the small problem of your code not working, please solve the huge problem of it being a mess. Me and others had a lot of suffering maintaining unmaintainable code, please try to make good code.