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
