Petr Pudlak wrote:

The problem is the (Ord b) condition, which is required for the Map
functions.  When I try to define the monad instance as

instance Monad Distrib where
    return = dreturn
    (>>=)  = dcompose

obviously, I get an error at (>>=):
    Could not deduce (Ord b) from the context.

Is there some way around? Either to somehow define the monad, or to
achieve the same functionality without using Map, which requires Ord
instances?

Not being allowed constraints on the variables for class methods is probably the problem I have most frequently run into recently in Haskell (is there any way to fix this, or does it open up a whole can of worms?).

There is no easy way around it, but for your problem, do you require that the items be kept unique as you go along? Could you not use a list of items with probabilities -- that can potentially contain duplicate items (but all the summed probabilities should add to one at every stage, presumably), and then combine them at the end? i.e. your code would look like:

newtype Distrib a = Distrib { undistrib :: [(a, Float)] }

runDistrib :: Ord a => Distrib a -> Map.Map a Float
runDistrib = Map.fromListWith (+) . undistrib

This would push the Ord constraint to runDistrib, and allow you to leave it off (>>=).

Neil.