Replacing [a] with (Set c a) in Monad instance.
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? Thanks Daniel
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. 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.
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.
On Wednesday 31 January 2007 22:36, Robert Dockins wrote:
On Tuesday 30 January 2007 20:06, Bryan Donlan wrote: 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.
Currently some external code is not lazy so the stack gets blown. My knee-jerk reaction was to try and reduce the state space by exploiting symmetries. I'll try sticking with the list and making things more lazy, and hopefully still be able to collapse the symmetric cases.
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.
Thanks for the links, I'll have a look at them if I have no luck with increasing the laziness. Cheers Daniel
participants (3)
-
Bryan Donlan -
Daniel McAllansmith -
Robert Dockins