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.