[Haskell-cafe] a problem defining a monad instance

[Petr Pudlak]

    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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe