Why is there a type class Measured for Data.FingerTree instead of just a function?

Question

I don't understand why FingerTree is implemented with the type class Measured.

I'm trying to implement a sequence of monoid that have the default measure the same as the monoid, so I wrote the following.

instance Monoid a => Measured (Sum Int, a) a where
  measure x = (Sum 1, x)

Of course, since FingerTree itself is a Measured, this is impossible as we will get type class overlap.

At what point was abstracting this single function into a type class make sense? Why can't we just define FingerTree so we can feed a measure function to the constructor?

It would also be nice to know if there are ways to overcome this problem. I could just define a new instance for my particular use case each time, but maybe there is a better way.

Answer 1

This is an instance of the general friction between typeclass function resolution and "direct" function resolution. There are many times to favor direct, as you've pointed out here, but often times when it's possible to state particular laws that a typeclass instance must uphold people find it meaningful to use typeclass resolution.

I don't think it's possible to have a "right" answer for which is better, but there are indeed great arguments for using the direct method more frequently.

In this case, the more specificity is needed to help the compiler understand which instance should be resolved. While it's the case that any Monoid can have a "count and combine" Measured instance, it's not clear that this is the canonical instance. Since the class for Measured demands that Measured v a | a -> v we must pick v canonically.

The most likely way to do this is to create a newtype wrapper

newtype Counted a = Counted a
instance Monoid a => Measured (Sum Int, a) (Counted a) where
  measure (Counted x) = (Sum 1, x)

which gives us the required canonicity. This might be more convenient in some instances than passing around the Monoid function dictionary directly.