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
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, 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
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
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 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
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
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
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
[Haskell-cafe] Monad instance for Data.Set, again
The blog article http://www.randomhacks.net/articles/2007/03/15/data-set-monad-haskell-macros describes a variant of the Monad class which allows to restrict the type of the monadic result, in order to be able to make Data.Set an instance of Monad (requiring Ord constraint for the monadic result). The same problem arises for container data structures with restricted element types, where the element type restriction depends on the implementation of the container structure (such as UArray). It would be cumbersome to have several class parts, even more, type constraints in type signatures may reveal implementation details. E.g. constraint (Container c x y z) might be needed for a 'zipWith' function, whereas (Container c y x z) is needed if you use 'zipWith' with swapped arguments. 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)) GHC says: RestrictedMonad.hs:21:13: Could not deduce (Ord b) from the context (RestrictedMonad Set, AssociatedMonad Set a, AssociatedMonad Set b) arising from use of `Data.Set.unions' at RestrictedMonad.hs:21:13-22 Probable fix: add (Ord b) to the class or instance method `RestrictedMonad.=' In the definition of `=': = x f = Data.Set.unions (map f (Data.Set.toList x)) In the definition for method `RestrictedMonad.=' In the instance declaration for `RestrictedMonad Set' ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Monad instance for Data.Set
The following code solves exactly the problem of implementing (restricted) MonadPlus in terms of Data.Set: http://okmij.org/ftp/Haskell/DoRestrictedM.hs The code is written to demonstrate the do-notation. We write the monadic code as usual: test1s_do () = do x - return a return $ b ++ x and then instantiate it for Maybe String: test1sr_do :: Maybe String test1sr_do = unRM $ test1s_do () -- Just ba or for Data.Set: test2sr_do :: Set.Set String test2sr_do = unSM $ test1s_do () -- fromList [ba] It seems GHC 6.10 will support the do-notation even for the generalized monads. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
