Re: [Haskell-cafe] Monad instance for Data.Set
On Sun, Mar 30, 2008 at 1:09 PM, Henning Thielemann <[EMAIL PROTECTED]> wrote: > It's like working in the List monad mainly, collapsing duplicates from > time to time, right? Sort of. You can look at it that way and get a basic understanding of what's going on. A slightly more accurate analysis of what is going on is that it is working in ContT Set for a variation of ContT that doesn't require the underlying object to be a full monad, but only a restricted one. In such a monad you could define > mplus :: ContT Set a -> ContT Set a -> ContT Set a > mplus x y = lift $ union (runContT x id) (runContT y id) (not valid haskell code) However, what is actually happening is that we are defining a set of "side-effectful" computations using Prompt, and then observing those computations in a "Set" environment. With this definition you can actually implement the interface for any monad you want; just define the operations in your data type. In this case: > data OrdP m a where >PZero :: OrdP m a >PRestrict :: Ord a => m a -> OrdP m a >PPlus :: Ord a => m a -> m a -> OrdP m a > type SetM = RecPrompt OrdP Every monad provides at least the same operations as the Identity monad; this definition says that SetM is a monad that provides those operations, plus three additional operations: "prompt PZero", "prompt $ PRestrict x", and "prompt $ PPlus x y" of the types shown in the definition of "OrdP". You can then interpret those operations however you want; runSetM defines an observation function that runs the computation and returns its results in a Set, given the restriction that the computation itself returns an Ord type. In order to really understand this, you need to understand the type of "runPromptC": runPromptC :: (r -> ans) -- "pure" result handler -> (forall a. p a -> (a -> ans) -> ans) -- "side effect" handler that gets a continuation -> Prompt p r -- computation to run -> ans "runPromptC" is (almost) just the case operation for a structure of this type: data Prompt p r = Return r | forall a. BindEffect (p a) (a -> Prompt p r) except with the recursive call to runPromptC inlined within BindEffect; given this data type you can define runPromptC easily: runPromptC ret _ (Return r) = ret r runPromptC _ prm (BindEffect p k) = prm p (\a -> runPromptC ret prm (k a)) This definition makes it obvious that the "pure" continuation "ret" is called at the end of the computation, and the "effectful" continuation prm is called to handle any side effects. Exercise 1: Define the function "prompt :: p a -> Prompt p a" on this datatype. Exercise 2: Define an instance of Monad for this datatype. Now you should be able to understand the observation function "runSetM": > runSetM :: Ord r => SetM r -> S.Set r > runSetM = runPromptC ret prm . unRecPrompt where >-- ret :: r -> S.Set r >ret = S.singleton >-- prm :: forall a. OrdP SetM a -> (a -> S.Set r) -> S.Set r >prm PZero _ = S.empty >prm (PRestrict m) k = unionMap k (runSetM m) >prm (PPlus m1 m2) k = unionMap k (runSetM m1 `S.union` runSetM m2) "ret" handles the result of pure computations; that is, those that could have just as easily run in the Identity monad. "prm" handles any effects; in this case the three effects "PZero", "PRestrict" and "PPlus". You could write a different observation/interpretation function that treated the elements as a List, or Maybe, or whatever. Let me know if this makes sense, or if you have any other questions. -- ryan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monad instance for Data.Set
On Tue, 25 Mar 2008, Ryan Ingram wrote: settest :: S.Set Int settest = runSetM $ do x <- mplus (mplus mzero (return 2)) (mplus (return 2) (return 3)) return (x+3) -- fromList [5,6] What this does under the hood is treat the computation on each element of the set separately, except at programmer-specified synchronization points where the computation result is required to be a member of the Ord typeclass. It's like working in the List monad mainly, collapsing duplicates from time to time, right? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monad instance for Data.Set, again
On 3/28/08, Dan Weston <[EMAIL PROTECTED]> wrote: > I'm having trouble embedding unconstrained monads into the NewMonad: > Is there some trick (e.g. newtype boxing/unboxing) to get all the > unconstrained monads automatically instanced? Then the do notation could > be presumably remapped to the new class structure. The usual trick here is to use newtypes. (Yes, it sucks) > newtype OldMonad m = OldMonad m > unwrapMonad :: OldMonad m -> m > unwrapMonad (OldMonad m) = m > instance Monad m => Suitable (OldMonad m) v where > data Constraints (OldMonad m) v = NoConstraints > constraints _= NoConstraints > instance Monad m => NewMonad (OldMonad m) where > newReturn = OldMonad . return > newBind x k = OldMonad $ unwrapMonad x >>= unwrapMonad . k ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monad instance for Data.Set, again
I'm having trouble embedding unconstrained monads into the NewMonad: > {-# LANGUAGE ...,UndecidableInstances #-} > > instance Monad m => Suitable m v where > data Constraints m v = NoConstraints > constraints _= NoConstraints > > instance Monad m => NewMonad m where > newReturn = return > newBind x k = > let list2Constraints = constraints result > result = case list2Constraints of >NoConstraints -> (x >>= k) > in result SetMonad.hs:25:9: Conflicting family instance declarations: data instance Constraints Set val -- Defined at SetMonad.hs:25:9-19 data instance Constraints m v -- Defined at SetMonad.hs:47:9-19 Since Set is not an instance of Monad, there is no actual overlap between (Monad m => m) and Set, but it seems that Haskell has no way of knowing that. Is there some trick (e.g. newtype boxing/unboxing) to get all the unconstrained monads automatically instanced? Then the do notation could be presumably remapped to the new class structure. Dan Wolfgang Jeltsch wrote: Am Montag, 24. März 2008 20:47 schrieb Henning Thielemann: […] Here is another approach that looks tempting, but unfortunately does not work, and I wonder whether this can be made working. module RestrictedMonad where import Data.Set(Set) import qualified Data.Set as Set class AssociatedMonad m a where class RestrictedMonad m where return :: AssociatedMonad m a => a -> m a (>>=) :: (AssociatedMonad m a, AssociatedMonad m b) => m a -> (a -> m b) -> m b instance (Ord a) => AssociatedMonad Set a where instance RestrictedMonad Set where return = Set.singleton x >>= f = Set.unions (map f (Set.toList x)) […] The problem is that while an expression of type (AssociatedMonad Set a, AssociatedMonad Set b) => Set a -> (a -> Set b) -> Set b has type (Ord a, Ord b) => Set a -> (a -> Set b) -> Set b, the opposite doesn’t hold. Your AssociatedMonad class doesn’t provide you any Ord dictionary which you need in order to use the Set functions. The instance declaration instance (Ord a) => AssociatedMonad Set a says how to construct an AssociatedMonad dictionary from an Ord dictionary but not the other way round. But it is possible to give a construction of an Ord dictionary from an AssociatedMonad dictionary. See the attached code. It works like a charm. :-) Best wishes, Wolfgang ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monad instance for Data.Set, again
On Fri, 28 Mar 2008, Wolfgang Jeltsch wrote: But it is possible to give a construction of an Ord dictionary from an AssociatedMonad dictionary. See the attached code. It works like a charm. :-) This is really cool, and with much wider applicability than restricted monads; it gives us a general way to abstract over type class constraints. The NewMonad class is also very straightforward and I think will cause much fewer type-checking headaches and large type signatures than Oleg's solution. Ganesh ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monad instance for Data.Set, again
On Fri, 28 Mar 2008, Wolfgang Jeltsch wrote: But it is possible to give a construction of an Ord dictionary from an AssociatedMonad dictionary. See the attached code. It works like a charm. :-) Yeah, type families! In which GHC release they will be included? Sometimes I wonder how many single type extensions we will see in future or whether there will be one mechanism which subsumes all existing ones in a simple manner. (Full logic programming on type level? Manual determination of the class dictionary to be used?) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monad instance for Data.Set, again
Am Montag, 24. März 2008 20:47 schrieb Henning Thielemann: > […] > Here is another approach that looks tempting, but unfortunately does not > work, and I wonder whether this can be made working. > > module RestrictedMonad where > > import Data.Set(Set) > import qualified Data.Set as Set > > class AssociatedMonad m a where > > class RestrictedMonad m where > return :: AssociatedMonad m a => a -> m a > (>>=) :: (AssociatedMonad m a, AssociatedMonad m b) => > m a -> (a -> m b) -> m b > > instance (Ord a) => AssociatedMonad Set a where > > instance RestrictedMonad Set where > return = Set.singleton > x >>= f = Set.unions (map f (Set.toList x)) > […] The problem is that while an expression of type (AssociatedMonad Set a, AssociatedMonad Set b) => Set a -> (a -> Set b) -> Set b has type (Ord a, Ord b) => Set a -> (a -> Set b) -> Set b, the opposite doesn’t hold. Your AssociatedMonad class doesn’t provide you any Ord dictionary which you need in order to use the Set functions. The instance declaration instance (Ord a) => AssociatedMonad Set a says how to construct an AssociatedMonad dictionary from an Ord dictionary but not the other way round. But it is possible to give a construction of an Ord dictionary from an AssociatedMonad dictionary. See the attached code. It works like a charm. :-) Best wishes, Wolfgang {-# LANGUAGE ExistentialQuantification, MultiParamTypeClasses, FlexibleInstances, TypeFamilies #-} import Data.Set (Set) import qualified Data.Set as Set class Suitable monad val where data Constraints monad val :: * constraints :: monad val -> Constraints monad val class NewMonad monad where newReturn :: (Suitable monad val) => val -> monad val newBind :: (Suitable monad val, Suitable monad val') => monad val -> (val -> monad val') -> monad val' instance (Ord val) => Suitable Set val where data Constraints Set val = Ord val => SetConstraints constraints _ = SetConstraints instance NewMonad Set where newReturn = Set.singleton newBind set1 set2Gen = let set2Constraints = constraints result result = case set2Constraints of SetConstraints -> Set.unions $ map set2Gen $ Set.toList set1 in result ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monad instance for Data.Set
On Tue, 25 Mar 2008, Ryan Ingram wrote: I was experimenting with Prompt today and found that you can get a "restricted monad" style of behavior out of a regular monad using Prompt: I recently developed a similar trick: http://hsenag.livejournal.com/11803.html It uses the regular MonadPlus rather than a custom mplus/mzero, and should work for any restricted monad. Your "mrestrict" is "Embed . unEmbed" in my code (and should be given a shorter name, like "reEmbed"). Of course, mplus and mzero can't optimise, since they don't have an Ord constraint. Cheers, Ganesh ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Monad instance for Data.Set
I was experimenting with Prompt today and found that you can get a "restricted monad" style of behavior out of a regular monad using Prompt: > {-# LANGUAGE GADTs #-} > module SetTest where > import qualified Data.Set as S Prompt is available from http://hackage.haskell.org/cgi-bin/hackage-scripts/package/MonadPrompt-1.0.0.1 > import Control.Monad.Prompt "OrdP" is a prompt that implements MonadPlus for orderable types: > data OrdP m a where >PZero :: OrdP m a >PRestrict :: Ord a => m a -> OrdP m a >PPlus :: Ord a => m a -> m a -> OrdP m a > type SetM = RecPrompt OrdP We can't make this an instance of MonadPlus; mplus would need an Ord constraint. But as long as we don't import it, we can overload the name. > mzero :: SetM a > mzero = prompt PZero > mplus :: Ord a => SetM a -> SetM a -> SetM a > mplus x y = prompt (PPlus x y) "mrestrict" can be inserted at various points in a computation to optimize it; it forces the passed in computation to complete and uses a Set to eliminate duplicate outputs. We could also implement mrestrict without an additional element in our prompt datatype, at the cost of some performance: mrestrict m = mplus mzero m > mrestrict :: Ord a => SetM a -> SetM a > mrestrict x = prompt (PRestrict x) Finally we need an interpretation function to run the monad and extract a set from it: > runSetM :: Ord r => SetM r -> S.Set r > runSetM = runPromptC ret prm . unRecPrompt where >-- ret :: r -> S.Set r >ret = S.singleton >-- prm :: forall a. OrdP SetM a -> (a -> S.Set r) -> S.Set r >prm PZero _ = S.empty >prm (PRestrict m) k = unionMap k (runSetM m) >prm (PPlus m1 m2) k = unionMap k (runSetM m1 `S.union` runSetM m2) unionMap is the equivalent of concatMap for lists. > unionMap :: Ord b => (a -> S.Set b) -> S.Set a -> S.Set b > unionMap f = S.fold (\a r -> f a `S.union` r) S.empty Oleg's test now works without modification: > test1s_do () = do > x <- return "a" > return $ "b" ++ x > olegtest :: S.Set String > olegtest = runSetM $ test1s_do () > -- fromList ["ba"] > settest :: S.Set Int > settest = runSetM $ do >x <- mplus (mplus mzero (return 2)) (mplus (return 2) (return 3)) >return (x+3) > -- fromList [5,6] What this does under the hood is treat the computation on each element of the set separately, except at programmer-specified synchronization points where the computation result is required to be a member of the Ord typeclass. Synchronization points happen at every "mplus" & "mrestrict"; these correspond to a gathering of the computation results up to that point into a Set and then dispatching the remainder of the computation from that Set. -- ryan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe