Hi, thanks to all for all the helpful answers and references. Maybe I'll try to collect them into a wiki page, if I have time. It looks like that I'm not the only one facing this problem and many people know different tricks how to handle it.
Yes, I was thinking about using lists of pairs instead of Maps. But since I expect to have just a little distinct elements, but many >>= operations, lists would probably grow to an enormous sizes, while Maps will remain quite small. The most intriguing idea for me was wrapping my pseudo-monad into the continuation monad. I didn't have time to think it over, but I wondered if the same (or similar) trick could be used to applicative functors (which are not monads) or arrows. (I found out that J. Hughes faced a similar problem in his paper "Programming with Arrows" (p.42), but not with monads but arrows.) Now I can enjoy playing with probabilities :-). Maybe having complex numbers instead of Floats in the Distrib type would be a nice way how to simulate (at least some) quantum computations. RMonad also seems quite promising, and it looks like a more general solution, but I had no time to try it out yet. With best regards, Petr On Fri, Nov 06, 2009 at 07:08:10PM +0100, Petr Pudlak wrote: > Hi all, > > (This is a literate Haskell post.) > > I've encountered a small problem when trying to define a specialized > monad instance. Maybe someone will able to help me or to tell me that > it's impossible :-). > > To elaborate: I wanted to define a data type which is a little bit > similar to the [] monad. Instead of just having a list of possible > outcomes of a computation, I wanted to have a probability associated > with each possible outcome. > > A natural way to define such a structure is to use a map from possible > values to numbers, let's say Floats: > > > module Distribution where > > > > import qualified Data.Map as M > > > > newtype Distrib a = Distrib { undistrib :: M.Map a Float } > > Defining functions to get a monad instance is not difficult. > "return" is just a singleton: > > > dreturn :: a -> Distrib a > > dreturn k = Distrib (M.singleton k 1) > > Composition is a little bit more difficult, but the functionality is > quite natural. (I welcome suggestions how to make the code nicer / more > readable.) However, the exact definition is not so important. > > > dcompose :: (Ord b) => Distrib a -> (a -> Distrib b) -> Distrib b > > dcompose (Distrib m) f = Distrib $ M.foldWithKey foldFn M.empty m > > where > > foldFn a prob umap = M.unionWith (\psum p -> psum + prob * p) umap > > (undistrib $ f a) > > 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? > > Thanks a lot, > Petr > _______________________________________________ > Haskell-Cafe mailing list > Haskell-Cafe@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe