[Haskell-cafe] a problem defining a monad instance

[Petr Pudlak]

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

[Neil Brown]

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.

[Sjoerd Visscher]

You cannot make it an instance of Monad, but you can use do syntax:

{-# LANGUAGE NoImplicitPrelude #-}
module Distribution where

import Prelude hiding (return, (>>=))

import qualified Data.Map as M

newtype Distrib a = Distrib { undistrib :: M.Map a Float } deriving Show

return :: a -> Distrib a

return k = Distrib (M.singleton k 1)

(>>=) :: (Ord b) => Distrib a -> (a -> Distrib b) -> Distrib b
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)

test = do
a <- Distrib $ M.fromList [(1, 1), (2, 1)]
b <- Distrib $ M.fromList [(10, 1), (20, 1)]
return (a + b)

Sjoerd

--
Sjoerd Visscher
sjo...@w3future.com

[Miguel Mitrofanov]

The usual continuation trick:

fromDistrib :: Ord a => Distrib a -> Cont (Distrib r) a
fromDistrib da = Cont (\c -> dcompose da c)
toDistrib :: Cont (Distrib r) r -> Distrib r
toDistrib (Cont f) = f dreturn

"Cont anything" is a monad.

[Jason Dagit]

On Fri, Nov 6, 2009 at 10:19 AM, Neil Brown <nc...@kent.ac.uk> wrote:

> 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?).
>

I believe this paper is intended to propose a solution:
http://tomschrijvers.blogspot.com/2009/11/haskell-type-constraints-unleashed.html

Jason

[Jake McArthur]

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.

This is the same reason we do not have e.g. a Monad instance for Set.
One solution is a concept of "restricted" monads, and one implementation
of restricted monads is given here:
http://okmij.org/ftp/Haskell/types.html#restricted-datatypes

- Jake

[Brent Yorgey]

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 :-).

See the rmonad package on Hackage, which solves exactly this problem:

http://hackage.haskell.org/package/rmonad

-Brent

[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:

[Henning Thielemann]

On Fri, 6 Nov 2009, 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.

http://hackage.haskell.org/package/probability

> 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

This won't work and is the common problem of a Monad instance for
Data.Set.
http://www.randomhacks.net/articles/2007/03/15/data-set-monad-haskell-macros

There is however an idea of how to solve this using existential
quantification and type families:
http://code.haskell.org/~thielema/category-constrained/src/Control/Constrained/Monad.hs