Is it able to avoid UndecidableInstances in this example?

Question

I am trying to implement binary tree as a typeclass:

class BinaryTree bt where
    empty :: bt a -> Bool
    empty = isNothing . root
    emptyTree :: bt a
    branch :: a -> bt a -> bt a -> bt a 
    root :: bt a -> Maybe a
    lbranch :: bt a -> bt a 
    rbranch :: bt a -> bt a 

And I want to illustrate that binary trees are data containers using this definition:

instance BinaryTree bt => Functor bt where
    fmap f bt = case root bt of
        Nothing -> emptyTree
        Just a -> branch (f a) (f <$> lbranch bt) (f <$> rbranch bt)

I've got:

BinaryTree/BinaryTree.hs:18:10: error:
    • The constraint ‘BinaryTree bt’
        is no smaller than the instance head ‘Functor bt’
      (Use UndecidableInstances to permit this)
    • In the instance declaration for ‘Functor bt’

Using UndecidableInstances absolutely makes the code compile. But I am wondering that is this a proper case to use UndecidableInstances? I've read about articles like "When is UndecidableInstances safe?", but I do not really get it.

---

Update 1: About "Why using typeclasses"

It is a part of an exploration, in which I try to distinct complete binary trees and perfect binary trees from general binary trees by Haskell code, in a proper way, by describing the property of them in Haskell code. (The properties are: 1) complete binary trees are one-to-one correspond to lists, bt2list and list2bt are available, and 2) perfect binary trees is the combine of two same-depth perfect binary trees. )

Specifically, the ultimate goal is to declare a type for complete binary trees, that refuses a value which is a binary tree but not a complete binary tree when compiling. (And also for perfect binary trees.)

The exploration is still not given up and suggestions are welcomed. Many thanks!

Answer 1

On undecidable instances

UndecidableInstances is a mostly harmless extension. Don't worry if you have to turn it on.

In the worst case, UndecidableInstances can make the compiler get stuck in an infinite loop if you happen to have mutually depending instances, such as

instance A t => B t where ...
instance B t => A t where ...

If you are careful to avoid that, the compiler will just work fine.

The extension has no ill effects on the compiled code, only on the compilation itself. If your code compiles, you are safe.

On overlapping instances

On the other side, this is something to worry

instance BinaryTree bt => Functor bt where

The head of this instance is Functor t and that overlaps with any other instances for Functor. That is to be avoided.

Haskell instance resolution performs no backtracking at all, since that can lead to an exponential blow up in compilation time, and break separate compilation. There is no sane way to write something like

instance MyClass1 f => Functor f where ...
instance MyClass2 f => Functor f where ...

To make this work, when resolving Functor X, Haskell should first try to resolve MyClass1 X, and if that fails try MyClass2 X. This turns out to be too problematic in practice.

Note that Haskell allows instances to be declared in any module. So to check "no instance for MyClass1 X" Haskell would need to read all the modules in your program. This would prevent the compiler to compile a module at a time, so it's disallowed.

So, an instance like

instance MyClass1 f => Functor f where ...

actually means "If you are resolving Functor X, you must have MyClass X. If you don't, fail". It's not an implication but more like an "if and only if". The compiler commits to the first instance whose head (the Functor f part) matches. The instance context (the MyClass1 f => part) is not considered until the compiler has committed.

There are some ways to relax the constraints on overlapping instances, but I don't recommend those. They're very fragile if you don't precisely understand what's going on under the hood.

Conclusion

To avoid the overlap, you could use a newtype wrapper:

newtype F f a = F (f a)
instance BinaryTree bt => Functor (F bt) where

Even if it's not equivalent, you could specify a functor superclass:

class Functor bt => BinaryTree bt where ...

This will force new instances to ensure trees are functors.

Perhaps more importantly, you should also consider to avoid using type classes at all for this task. It's pretty unusual in Haskell to declare a type class unless you have several instances in mind. In your case, your class seems to be a single type: a binary tree. All its instances will be essentially the same type. So, why using classes at all?