Typeclass Trouble with Haskell Probability Monad

Question

I am trying to write a monad for discrete random variables in haskell. The type class looks something like this:

{- LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}

class (Num w, Monad m) => MonadDiscrete w m where
  sample :: [(a, w)] -> m a

I'd like to make two instances of this. The first is like the list monad:

newtype Discrete w a = Discrete [(a, w)]

instance (Num w) => Monad (Discrete w) where
  ...

instance (Num w) => MonadDiscrete w (Discrete w) where
  sample = Discrete

The second is using the PRNG in MonadRandom:

instance (MonadRandom m) => MonadDiscrete Rational m where
  sample = fromList

However, if I try to do something like:

x :: (Num w, MonadDiscrete w m) => m String
x = sample [("x", 1)]

GHC gives me an error:

Could not deduce (MonadDiscrete w0 m) arising from the ambiguity check for it' from the context (MonadDiscrete w m) bound by the inferred type forit': MonadDiscrete w m => m [Char] at :7:1-17 The type variable w0' is ambiguous Possible fix: add a type signature that fixes these type variable(s) Note: there are several potential instances: instance Num w => MonadDiscrete w (Discrete w) -- Defined at lib/Discrete.hs:64:10 instance Control.Monad.Random.Class.MonadRandom m => MonadDiscrete Rational m -- Defined at lib/Discrete.hs:58:10 When checking thatit' has the inferred type `forall w (m :: * -> *). MonadDiscrete w m => m [Char]' Probable cause: the inferred type is ambiguous

I've tried all sorts of things including adding FunDeps or making w an associated type, but all fail.

Could you fix your code sample? The instance for MonadDiscrete (Discrete w) needs another type parameter... That said, have you tried disambiguating the constant 1 in x, like so: (1::Int)? — yatima2975

Cactus Cactus · Accepted Answer · 2014-11-12T08:00:27

The problem is that the declaration

class (Num w, Monad m) => MonadDiscrete w m where
    sample :: [(a, w)] -> m a

doesn't express the fact that for a given discrete probability monad, the choice of the type to represent weights is fixed. For example, in your Discrete example, for any choice of w, the Discrete w monad can only deal with probability weights of type w.

Because this is not expressed in the above declaration, it is possible to define two MonadDiscrete instances that only differ in the choice of w, but not in the choice of m. This means in the definition of sample, the MonadDiscrete instance cannot be resolved from m alone.

The proper way to solve this is to use a functional dependency or a MonadDiscrete-associated type family to express the fact that the choice of m uniquely determines the choice of w. Here's an example that uses functional dependencies:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FunctionalDependencies #-}

class (Num w, Monad m) => MonadDiscrete w m | m -> w where
    sample :: [(a, w)] -> m a

newtype Discrete w a = Discrete [(a, w)]

instance (Num w) => Monad (Discrete w)
instance (Num w) => MonadDiscrete w (Discrete w)

x :: (Num w, MonadDiscrete w m) => m String
x = sample [("x", 1)]

Because m determines w, even though w doesn't occur in the type of x, it can still be uniquely resolved, so the correct MonadDiscrete instance can be picked.

Here's the same solution using type families:

{-# LANGUAGE TypeFamilies, FlexibleContexts #-}

class (Num (Weight m), Monad m) => MonadDiscrete m where
    type Weight m :: *
    sample :: [(a, Weight m)] -> m a

newtype Discrete w a = Discrete [(a, w)]

instance (Num w) => Monad (Discrete w)

instance (Num w) => MonadDiscrete (Discrete w) where
    type Weight (Discrete w) = w
    sample = undefined

x :: (MonadDiscrete m) => m String
x = sample [("x", 1)]

This one feels a bit different, because here instead of spelling out the dependency, we simply say that part of being a MonadDiscrete instance is saying what type is representing Weights.

Typeclass Trouble with Haskell Probability Monad

2 Answers