How to change the behavior of the function based on class constraints in Haskell?

Question

I have a data type that represents a collection of values paired with a probability. At first, the implementation was just to use good old lists, but as you can imagine, this can be inefficient (for example, I use a Tree instead of a list to store ordered values)

After some research, I thought about using GADTs

data Tree a b = Leaf | Node {left::Tree a b, val :: (a, b), right :: Tree a b}

data Prob a where
  POrd   ::Ord a => Tree a Rational -> Prob a
  PEq    ::Eq a => [(a, Rational)] -> Prob a
  PPlain ::[(a, Rational)] -> Prob a

So far, so good. I'm now stuck at trying to create a smart constructor for my new data type, that takes [(a,Rational)] and depending on the constraints of a, chooses the correct constructor for Prob. Basically:

prob :: [(a, Rational)] -> Prob a
-- chooses the "best" constructor based on the constraints of a

Is this at all possible? If not, how should I go about designing something better? Am I missing something?

Thanks!

Answer 1

There is no way to perform a check of the form "is type T in class C?" in Haskell. The issue here is that it is hard to answer negatively to such question and allow separate compilation: T could be in C in the scope of one module but not in the scope of another one, causing a rather fragile semantics.

To ensure consistency, Haskell only allows to require a constraint, and raise an compile time error otherwise.

As far as I can see, the best you can do is to use another custom type class, which tells you which case is the best one. E.g.

{-# LANGUAGE AllowAmbiguousTypes, TypeApplications, ScopedTypeVariables #-}

data BestConstraint a where
   BCOrd  :: Ord a => BestConstraint a
   BCEq   :: Eq a => BestConstraint a
   BCNone :: BestConstraint a

class BC a where
   bestC :: BestConstraint a

instance BC Int where bestC = BCOrd
-- ... etc.
instance BC a => BC [a] where
   bestC = case bestC @a of
       BCOrd  -> BCOrd
       BCEq   -> BCEq
       BCNone -> BCNone

prob :: forall a . BestConstraint a => [(a, Rational)] -> Prob a
prob xs = case bestC @a of
    BCOrd  -> POrd ....  -- build the tree
    BCEq   -> PEq xs
    BCNone -> PPlain xs

You will have to provide an instance for any type you want to use, though.