[Haskell-cafe] Replacing [a] with (Set c a) in Monad instance.

[Robert Dockins]

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.