[Haskell-cafe] Replacing [a] with (Set c a) in Monad instance.
Robert Dockins
robdockins at fastmail.fm
Wed Jan 31 04:36:48 EST 2007
On Tuesday 30 January 2007 20:06, Bryan Donlan wrote:
> Daniel McAllansmith wrote:
> > Hello.
> >
> > Given:
> >
> > newtype Dist a = D {unD :: [(a,Int)]}
> >
> > instance Monad Dist where
> > return x = D [(x,1)]
> > d >>= f = D [(y,q*p) | (x,p) <- unD d, (y,q) <- unD (f x)]
> > fail _ = D []
> >
> >
> > How would one change Dist to wrap an instance of the (Data.Edison.Set c
> > a) typeclass so that the Monad instance could be implemented in terms of
> > e.g. singleton, unionWith, empty, etc?
>
> I don't know about Data.Edison.Set, but if it's anything like
> base/Data.Set, then there's an Ord constraint on the elements, making it
> impossible to directly transform into a monad.
There are several flavors of set typeclasses in Edison. Some have Ord
constraints and some don't. All of them have an Eq constraint, however, so
the objection still applies. Furthermore, Edison collection classes are
organized as types of kind *, whereas monad instances require kind * -> *.
http://www.eecs.tufts.edu/~rdocki01/docs/edison/Data-Edison-Coll.html
If you instead want to replace your list with one of the Edison sequence
implementations, that should be possible. However, I'm not really sure that
it's going to buy you a lot. From a quick glance, it looks like the regular
list type is going to be the best datastructure for the computational pattern
of this monad, as long as your computations are sufficiently lazy.
> However, Roberto Zunino
> came up with a clever way to bypass this problem with GADTS:
> http://article.gmane.org/gmane.comp.lang.haskell.cafe/18118
>
> You may be able to apply this to your situation, using various Edison
> collections depending on which typeclasses your monad argument implements.
More information about the Haskell-Cafe
mailing list