Only the matcher cannot be recursive, because that could lead to infinite pattern matching (infinitely large programs). Having a recursive builder is fine, because they can contain arbitrary functions.

You can allow arbitrary functions in patterns by using ViewPatterns:

normJoinList (JoinTree (normJoinList -> JNil) (normJoinList -> JNil)) = JNil
normJoinList x = x

pattern Nil <- (normJoinList -> JNil)
  where Nil = JNil

I think that does what you want:

> case Nil `JoinTree` Nil of Nil -> True; _ -> False
True

Only the matcher cannot be recursive, because that could lead to infinite pattern matching (infinitely large programs). The desugaring of case x of Nil -> y would be:

  case x of
    JNil -> y
    JoinTree x2 x3 -> case x2 of
      JNil -> case x3 of
        JNil -> y
      JoinTree x4 x5 -> case x4 of
        ...

Going on infinitely.

Having a recursive builder is fine, because they can contain arbitrary functions. Here is perhaps a simpler example that shows this without the confusion of constructors:

pattern Foo <- ()
  where Foo = let loop = loop in loop

You can allow arbitrary functions in patterns by using ViewPatterns:

normJoinList (JoinTree (normJoinList -> JNil) (normJoinList -> JNil)) = JNil
normJoinList x = x

pattern Nil <- (normJoinList -> JNil)
  where Nil = JNil

I think that does what you want:

> case Nil `JoinTree` Nil of Nil -> True; _ -> False
True