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!

Is there any reason why you can’t make specialized smart constructors for the types you’d use Prob for? Like pInt = POrd :: Tree Int Rational -> Prob Int. I don’t see there being much utility to picking the right constructor for a given data type. It doesn’t save a user that much code or time. That said, this is still an interesting question. Just wanted to offer this comment in case you thought the prob function was necessary. — cole
– cole, Commented Sep 10, 2020 at 5:03
There isn't actually any requirement here, I'm just playing around with the type system and seeing what's possible. I'm basically trying to write a module, define its interface and use it afterwards pretending I don't know anything about the implementation! — ymegdiche
– ymegdiche, Commented Sep 10, 2020 at 8:06

chi · Accepted Answer · 2020-09-10 07:39:32Z

3

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.

answered Sep 10, 2020 at 7:39

chi

117k4 gold badges143 silver badges230 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

leftaroundabout Over a year ago

I absolutely agree that this is the proper way to do it, however it should still be mentioned that overlapping instances do provide a way to kind of decide based on whether or not an instance exists.

dfeuer Over a year ago

@leftaroundabout, how's that? Don't they just let you decide based on inequality?

leftaroundabout Over a year ago

Yes, that's why I wrote “kind of”.

chi Over a year ago

@leftaroundabout I don't think they can solve this specific problem, though. Can they?

leftaroundabout Over a year ago

@chi what I mean is just, you could add instance {-# OVERLAPPABLE #-} BC a where bestC = BCNone and then only the types that actually use Ord-optimisation would need to get instances; any other type would automatically be usable but without optimisation. Not saying this is a big advantage or even a good idea at all, but it does make a decision based on whether or not an (“explicit”) instance for a type exists – albeit not whether Eq and Ord exists, but whether instance BC exists.

|

Collectives™ on Stack Overflow

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

1 Answer 1

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related