Opened 6 years ago
Closed 9 months ago
#4370 closed feature request (fixed)
Bring back monad comprehensions
Reported by: | simonpj | Owned by: | |
---|---|---|---|
Priority: | normal | Milestone: | ⊥ |
Component: | Compiler | Version: | 6.12.3 |
Keywords: | Cc: | giorgidze@…, ganesh, ezyang@…, jeroen.weijers@…, bos@…, mail@…, sebf@…, tyler@…, pumpkingod@…, leather@…, anton.nik@…, alex@… | |
Operating System: | Unknown/Multiple | Architecture: | Unknown/Multiple |
Type of failure: | None/Unknown | Test Case: | |
Blocked By: | Blocking: | ||
Related Tickets: | Differential Rev(s): | ||
Wiki Page: |
Description
George Giorgidze writes: My colleagues and I are working on Haskell embedded DSL for data-intensive and data-parallel applications. The idea is to provide the Haskell list prelude combinators to manipulate database-resident data. The combinators are not executed in Haskell runtime, instead they are compiled down to SQL, executed on relational database systems and the results are marshalled back to Haskell for further in-heap processing or generation of new database-able embedded programs.
Although programming with the standard list processing combinators is feasible, the embedded programs are much more concisely formulated using the list comprehension notation, especially, when extended with 'order by' and 'group by' constructs.
Unfortunately, in Haskell, the list comprehension notation is only available for processing lists.
In order to support the list comprehension notation, we have built a quasiquter that desugars the list comprehension notation, but, instead of generating code using the Haskell list prelude combinators the quasiquter generates code that uses list processing combinators from our embedded language.
Although the quasiquoting approach worked for us, it has a number of drawbacks:
- Introduces extra syntactic noise
- Error messages are hard to understand as they refer to enerated code
- Needs to be re-implemented for every list-based embedded language
One way to address the aforementioned drawbacks is to define our queries as a monad (similar to list monad) and use the monad comprehension notation. The do notation can be used but it is less suited for query languages.
Unfortunately monad comprehensions were removed from Haskell, prior to Haskell 98. However, I think that the notation is extremely useful not only for lists, but for other list like data structures, list-based query languages (see above), maybe even for wider range of EDSLs and monads. I think the feature deserves to be supported at least as a GHC language extension.
Thus, I would like to propose to design and implement the monad comprehension notation as a GHC language extension. I am willing to invest some time and contribute to this effort.
One can also look at how recently introduced 'order by' and 'group by' constructs generalise to monad comprehensions. If that works, one could implement even more "stylish" monad comprehension notation.
Feedback from GHC users and developers would be very much appreciated.
- Do you think that this is a good idea?
- Would you use monad comprehensions (if available) for your library/EDSL/application?
- Do you think that it would be hard to integrate this extension into current GHC codebase?
- Have you already thought about how to generalise 'order by' and 'group by' to monad comprehensions?
- Have you already thought about how to address the original objections to the monad comprehension notation?
Attachments (13)
Change History (85)
comment:1 Changed 6 years ago by
Cc: | giorgidze@… added |
---|
comment:2 Changed 6 years ago by
Yes, I think this would be a reasonable thing to implement. Provided it doesn't make the code in the compiler become horrid, I'd be happy to have this as a patch. It should fit in quite smoothly, and should not affect people who don't use it. (I'm assuming you intend it as a language extension. The original objections were indeed solely to do with unexpected error messages.)
As Max says, much of the machinery is there already. But there are quite a lot of deatils to think about.
- In the renamer, there is special case code for
mdo
, but otherwise list comprehensinos and do-notation is handled uniformly. I think we've deprecatedmdo
in favour ofdo {..rec..}
, which would mean we could get rid of the mdo code altogether, but I'm not sure we've reached consensus; see #4148. Cleaning up this corner would be v helpful.
- In the type checker, there is special case code for list comprehensions, separate from do-notation. You could simply use the do-notation code, but that would lose the
group by
andzip
stuff, which only appears in the list comprehension code. So you could:- Disable the group-by stuff when supporting monad comprehensions; but that would be annoying when you really want to use group-by in the same module as a monad comprehension.
- Implement
group by
etc in the monad case too. See Max's comments.
- In the desugarer there is special desguaring code for list comprehensions, to get it into foldr/build form. You could probably still get the same effect by steering the desugaring by the types rather the syntactic form of the comprehension.
Things to watch out for
- Rebindable syntax currently works for do-notation but not for list comprehensions. A natural consequence of the change would be to support rebindable syntax for comprehensions too, which would be a good thing.
- There is a parallel-array comprehension form too, also handled by the same code. eg
[: a+1 | a <- as :]
. We don't want to mess it up.
- More surprisingly, guards on a function definition are also handled by the same code. Eg
f x | Just y <- g x , y>3 = blah
Here the guards are justStmts
, whereStmt
is the primitive component of a comprehension. So again, we don't want to mess them up.
I'm happy to advise on this project, but unlikely to take the initiative.
comment:3 Changed 6 years ago by
Cc: | ganesh added |
---|
comment:4 Changed 6 years ago by
Cc: | ezyang@… added |
---|
comment:5 Changed 6 years ago by
Cc: | jeroen.weijers@… added |
---|
comment:6 follow-up: 7 Changed 6 years ago by
Cc: | bos@… added |
---|
comment:7 Changed 6 years ago by
Cc: | mail@… added |
---|
comment:8 Changed 6 years ago by
Cc: | sebf@… added |
---|
comment:9 Changed 6 years ago by
Owner: | set to nsch |
---|
Thank you for the detailed reply, Simon. I'm currently working for George and his research group and I'm going to take on this task in the next couple of weeks. Those advices will be a great help.
- Nils Schweinsberg
comment:10 Changed 6 years ago by
Cc: | gideon@… added |
---|
comment:11 Changed 6 years ago by
Milestone: | → 7.2.1 |
---|---|
Type: | bug → feature request |
comment:12 Changed 6 years ago by
Cc: | tyler@… added |
---|
comment:13 follow-up: 14 Changed 6 years ago by
I finished the typechecker/desugarer on generators and guards for monad comprehensions (Fun with monad comprehensions) and want to give you a quick summary on what I've done so far. If you have any concerns about those changes, please let me know.
main/DynFlags.lhs
- New
MonadComprehensions
flag.
hsSyn/HsExpr.lhs
- New
MonadComp
context is added to theHsStmtContext
data type. It currently gets aPostTcTable
argument, very simliar to theMDoExpr
context (see the note about typechecking/desugaring below).
- The
ExprStmt
constructor got anotherSyntaxExpr
argument, where theguard
operation is added by the renamer and later on assures that we have an instance ofMonadPlus
in the typechecker.
parser/Parser.y.pp
- Whenever a list comprehension is found and
MonadComprehensions
is turned on, the newMonadComp
context is passed to theHsDo
expression instead of the oldListComprehension
context.
rename/RnExpr.lhs
- New rule in the
rnStmt
function forExprStmt
s inside monad comprehensions, where theguard
function is looked up and added to theExprStmt
. This makes sure that we don't getNot in scope:
guard'` error messages inside otherHsDo
expressions, like do blocks or regular list comprehensions.
typecheck/TcTcExpr.lhs
- New rule in
tcDoStmts
for monad comprehensions. A complete new typechecking functiontcMcStmt
is used to typecheck monad comprehension statements. TheBindStmt
rule is very similiar to the typechecking rule forBindStmt
inside do-blocks, theExprStmt
is typechecked to typebool
(to allow rebindable syntax) and theguard
function (the new argument to theExprStmt
constructor) is typechecked tobool -> res_ty
. TheLetStmt
s haven't been touched and work the same for every context anyway. I'm currently working on theTransformStmt
andGroupStmt
, so they're missing right now.ParStmt
s will require an
- The
body
(as in[ body | .. ]
) is typechecked to the typea
where the resulting type of the whole monad comprehension is typechecked to typem a
. See the note on typechecking/desugaring below.
deSugar/DsExpr.lhs
- New
dsMonadComp
function which is used to desugar monad comprehensions into core expressions. I decided that it would be the easiest way to just create a new typechecking rule and rewrite the whole desugaring part for monad comprehensions since you cannot just translate monad comprehensions into do-blocks/list comprehensions and reuse existing desugarers. However, I was able to reuse (aka copy & paste) a lot of the existing desugaring code of do-blocks (and mdo-blocks).
Typechecking/desugaring
As mentioned above, the body should be typechecked to type a
. However, to be
able to return
this body to the final m a
type I need a typechecked version
of the return
function in the desugarer. Because I don't wanted to modify the
body syntax tree in the typechecker (it lead to some strange looking error
messages etc) I added that PostTcTable
argument to the MonadComp
context.
This PostTcTable
is a list of typechecked functions and their names which can
be used in the desugarer to build core expressions with those functions. This
technic is already used with MDoExpr
s (typecheck/TcMatches.lhs +276 &
deSugar/DsExpr.lhs +818), but I don't know if its the most elegant way to solve
this issue. Any thoughts on this?
comment:14 follow-up: 15 Changed 6 years ago by
Replying to nsch:
If you have any concerns about those changes, please let me know.
hsSyn/HsExpr.lhs
- New
MonadComp
context is added to theHsStmtContext
data type. It currently gets aPostTcTable
argument, very simliar to theMDoExpr
context (see the note about typechecking/desugaring below).
I'm afraid that the PostTcTable
in MDoExpr
is misleading. As you'll see, it's the only use of PostTcTable
and it shouldn't really be there. Instead each individual BindStmt
or ExprStmt
carries its own evidence. eg RecStmt
has mfix
and return
, etc. One reason for this is that in principle the monad doesn't need to stay the same throughout! Eg someone wanted
(>>=) :: m1 a -> (a -> m2 b) -> m2 b
So you should find you can do without the PostTcTable
on MonadComp
altogether.
- The
ExprStmt
constructor got anotherSyntaxExpr
argument, where theguard
operation is added by the renamer and later on assures that we have an instance ofMonadPlus
in the typechecker.
OK, but only for ExprStmts
that are within a MonadComp
. Make sure this is documented in the type declaration.
rename/RnExpr.lhs
- New rule in the
rnStmt
function forExprStmt
s inside monad comprehensions, where theguard
function is looked up and added to theExprStmt
.
Here you mean "guard
is looked up only for monad comprehensions", I assume?
In other cases, the guard
field stays as bottom?
Actually, on reflection, consider this.
do notation: do { e ; Q } --> e >> do { Q } monad comp: [ e | g; Q ] --> guard g >> [ e | Q ]
Which suggests that you can typecheck the ExprStmt
of a monad comprhension
in the above way, and then attach a SyntaxExpr
of ( (>>) . guard ) to the ExprStmt
.
Then you'd only need the one field. The (>>)
and guard
would be looked up
(they are rebindable) but the compose operation (.)
is the real built-in one,
not rebindable. This would be much neater than having two fields, one of which
is usually bottom.
(I think you suggested this before.)
The
BindStmt
rule is very similiar to the typechecking rule forBindStmt
inside do-blocks, theExprStmt
is typechecked to typebool
(to allow rebindable syntax) and theguard
function (the new argument to theExprStmt
constructor) is typechecked tobool -> res_ty
. TheLetStmt
s haven't been touched and work the same for every context anyway. I'm currently working on theTransformStmt
andGroupStmt
, so they're missing right now.
Do you think you could write the documentation first? We'll need it sooner or later, and soonre is better. In particular, the story that a monad comprension type-checks just as if you were typechecking the desugared version. So we need to give the desugaring in the manual. Something like
[ e | p <- r; Q ] --> r >>= (\p -> [e | Q])
and so on for each form. That's the easiest way to explain how TransformStmt
and GroupStmt
behave in monad comprehensions; and once it's written down, it'll be easier to
understand the code. This desugaring table should appear in the user manual.
As mentioned above, the body should be typechecked to type
a
. However, to be able toreturn
this body to the finalm a
type I need a typechecked version of thereturn
function in the desugarer. Because I don't wanted to modify the body syntax tree in the typechecker (it lead to some strange looking error messages etc) I added thatPostTcTable
argument to theMonadComp
context.
I can see why you want it there, because the HsDo
constructor looks like this:
| HsDo (HsStmtContext Name) -- The parameterisation is unimportant -- because in this context we never use -- the PatGuard or ParStmt variant [LStmt id] -- "do":one or more stmts (LHsExpr id) -- The body; the last expression in the -- 'do' of [ body | ... ] in a list comp PostTcType -- Type of the whole expression
So you want a SyntaxExpr
to accompany hte LHsExpr
. But just as you only
need the guard
operator on the ExprStmts
in a monad comprehension, so you only
need the return
operator for monad comprehensions. So for the latter case it
makes some sense to have it on the MonadComp
constructor.
So, I suggest you nuke the PostTcTable
on MonadComp
, and replace it with
one SyntaxExpr
for return
.
comment:15 follow-up: 16 Changed 6 years ago by
Replying to simonpj:
I'm afraid that the
PostTcTable
inMDoExpr
is misleading. As you'll see, it's the only use ofPostTcTable
and it shouldn't really be there.
I'll get ridd of it. I didn't like it anyway. :)
Here you mean "
guard
is looked up only for monad comprehensions", I assume?
Yes.
In other cases, the
guard
field stays as bottom?
Yes.
Actually, on reflection, consider this.
do notation: do { e ; Q } --> e >> do { Q } monad comp: [ e | g; Q ] --> guard g >> [ e | Q ]Which suggests that you can typecheck the
ExprStmt
of a monad comprhension in the above way, and then attach aSyntaxExpr
of ( (>>) . guard ) to theExprStmt
. Then you'd only need the one field. The(>>)
andguard
would be looked up (they are rebindable) but the compose operation(.)
is the real built-in one, not rebindable. This would be much neater than having two fields, one of which is usually bottom.
I actually tried that, but I cannot typecheck that ((>>) . guard)
function in the typechecker using tcSyntaxOp
since it results in some GHC panic error message on runtime. It's a bit difficult to reproduce right now since it requires quite a few changes - but if you think the exact error message would be helpful I can get it.
However, I'm not sure if this is the right way to typecheck this expression, but using tcMonoExpr
is obvisouly wrong and I didn't see any other usefull functions.
Do you think you could write the documentation first?
I'll work on that. Thanks for the examples.
comment:16 follow-ups: 17 18 Changed 6 years ago by
I actually tried that, but I cannot typecheck that
((>>) . guard)
function in the typechecker usingtcSyntaxOp
since it results in some GHC panic error message on runtime. It's a bit difficult to reproduce right now since it requires quite a few changes - but if you think the exact error message would be helpful I can get it.
No, I wasn't clear enough. I meant:
- Typecheck
(>>)
usingtcSyntaxOp
just as you are doing now, producinge_bind
- Ditto
guard
, producinge_guard
- Now construct the expression
(\x. e_bind (e_guard x))
, or(e_bind . e_guard)
, whichever is easier, and stick that in theExprStmt
. For the latter you'll need to add the three type arguments to(.)
.
Do not attempt to typecheck ((>>) . guard)
, because the programmer didn't write that, and we don't want type error messages to mention that program fragment.
Does that make more sense?
comment:17 Changed 6 years ago by
Jeroen and I have written down desugaring rules for basic and SQL-like monad comprehensions. The rules were written by generalising SQL-like list comprehension translation rules given in the paper called "Comprehensive Comprehensions".
The desuguaring rules for monad comprehensions are using only monadic bind, return, guard and mzip combiantors. This can be useful for Nils as he implements "then" and "then group" constructs. Of course, the rules that precisely mirror the implementation can also be devised once the translation is implemented.
The combinator mzip is a method of MonadZip
class that is a subclass of Monad
for those monads that support zipping. Just like monad comprehension guards which are only allowed for MonadPlus
instances (already implemented by Nils), parallel (zip) monad comprehensions would only be allowed for monads that are in MonadZip
. Later, in this trac ticket, I will post proposal defining MonadZip
class together with the (monadic version of) zip laws that MonadZip
instances should satisfy.
The monad comprehension desugaring rules are obtained by performing the following generalisations on the translation given in the paper:
- replace
map
withmmap
that is defined asmmap f ma = ma >>= (return . f)
- replace
concat
withjoin
that is defined asjoin ma = ma >>= id
- replace
if g then [()] else []
withguard g
- replace
zip
withmzip
- inline the definitions of
mmap
andjoin
Here are the rules:
-- Variables : x and y -- Expressions : e, f and g -- Patterns : w -- Qualifiers : p, q and r [ e | q ] = [| q |] >>= (return . (\q_v -> e)) -- (.)_v rules, note that _v is a postfix rule application (w <- e)_v = w (let w = d)_v = w (g)_v = () (p , q)_v = (p_v,q_v) (p | v)_v = (p_v,q_v) (q, then f)_v = q_v (q, then f by e)_v = q_v (q, then group by e using f)_v = q_v (q, then group using f)_v = q_v -- [|.|] rules [| w <- e |] = e [| let w = d |] = return d [| g |] = guard g [| p, q |] = ([| p |] >>= (return . (\p_v -> [| q |] >>= (return . (\q_v -> (p_v,q_v)))))) >>= id [| p | q |] = mzip [| p |] [| q |] [| q, then f |] = f [| q |] [| q, then f by e |] = f (\q_v -> e) [| q |] [| q, then group by e using f |] = (f (\q_v -> e) [| q |]) >>= (return . (unzip q_v)) [| q, then group using f |] = (f [| q |]) >>= (return . (unzip q_v)) -- unzip (.) rules. Note that unzip is a desugaring rule (i.e., not a function to be included in the generated code) unzip () = id unzip x = id unzip (w1,w2) = \e -> ((unzip w1) (e >>= (return .(\(x,y) -> x))), (unzip w2) (e >>= (return . (\(x,y) -> y))))
Note that then group by e
case is missing. The SQL-like list comprehensions use groupWith
(see GHC.Exts module) as a default when using
clause is absent. Maybe we should have a class providing default grouping method for certain monads. Another (possibly less attractive) option is to always require grouping function.
comment:18 Changed 6 years ago by
Replying to simonpj:
No, I wasn't clear enough. I meant:
- Typecheck
(>>)
usingtcSyntaxOp
just as you are doing now, producinge_bind
- Ditto
guard
, producinge_guard
- Now construct the expression
(\x. e_bind (e_guard x))
, or(e_bind . e_guard)
, whichever is easier, and stick that in theExprStmt
. For the latter you'll need to add the three type arguments to(.)
.
Then I don't understand you. How/where am I supposed to look those functions up? I thought that should be done in the renamer?
At the moment this is what I do:
First, look up the names of those two functions. Pass them to the typechecker via the ExprStmt
.
-- rename/RnExpr.lhs rnStmt (MonadComp _) (L loc (ExprStmt expr _ _ _)) thing_inside -- ... ; (then_op, fvs1) <- lookupSyntaxName thenMName ; (guard_op, fvs3) <- lookupSyntaxName guardMName -- ... ; return (([L loc (ExprStmt expr' then_op guard_op placeHolderType)], thing), ...
Then typecheck everything, using tcSyntaxOp
and pass the typechecked versions to the desugarer:
-- typecheck/TcMatches.lhs tcMcStmt _ (ExprStmt rhs then_op guard_op _) res_ty thing_inside -- ... ; guard_op' <- tcSyntaxOp MCompOrigin guard_op (mkFunTy test_ty rhs_ty) ; then_op' <- tcSyntaxOp MCompOrigin then_op (mkFunTys [rhs_ty, new_res_ty] res_ty) -- ... ; return (ExprStmt rhs' then_op' guard_op' rhs_ty, thing) }
And in the desugarer I finally put both functions and the "thing" together:
-- deSugar/DsListComp.lhs go (ExprStmt rhs then_exp guard_exp _) stmts = do { rhs' <- dsLExpr rhs ; guard_exp' <- dsExpr guard_exp ; then_exp' <- dsExpr then_exp ; rest <- goL stmts ; return $ mkApps then_exp' [ mkApps guard_exp' [rhs'] , rest ] }
Of course, I could compose both functions right away in the typechecker, but I'd still need to look them up in the renamer. Or are you suggesting to me to do all three steps at once?
comment:19 Changed 6 years ago by
Drat, I'd forgotten that the renamer does one step and the typechecker the next. That is annoying; I can't see a neat way to do this. Oh well, it's not a big deal. What you have done seems fine. Please document (in the data type declaration) the fact that the 'guard' field is used only for monad comprehensions, and is otherwise bottom.
comment:20 Changed 6 years ago by
Today, George and I have written down a number of proposals that concern generalisation of SQL-like list comprehensions to monad comprehensions. We also briefly discussed the proposals with Torsten.
The proposals mainly involve library additions (GHC.Exts could be one option). Feedback from Haskell community members who expressed their interest in the ongoing work on the monad comprehension extension by signing up to this trac ticket would be very much appreciated.
Note that in the following we assume the type class hierarchy of the current Haskell Prelude where Monad is not defined as a subclass of Functor.
The SQL-like list comprehension notation provides 'then group by e' clause. Note that 'using f' clause is omitted. This means that default groupWith function (defined in GHC.Exts module) is used for grouping. In other words 'then group by e' is equivalent to 'then group by e using groupWith'.
--| The groupWith function uses the user supplied function which projects an element out of every list element in order to first sort the input list and then to form groups by equality on these projected elements.
groupWith :: Ord b => (a -> b) -> [a] -> [[a]]
Obviously this function is only suitable as a default grouping function for lists.
In the following we outline a number of options of supporting default grouping functions for the monad comprehension notation.
(OPTION 1) MonadGroup type class WITHOUT restrictions on the type t of projected out values allowing MonadGroup instances to introduce restrictions on t.
class Monad m => MonadGroup m t where mgroupWith :: (a -> t) -> m a -> m (m a)
Here we propose not to have any restrictions on the type t, as this will limit the usability of the class. This class will not impose any extra laws as is done by the Monad, MonadPlus and MonadZip (see below) classes. The class is defined to merely introduce a default grouping function for certain monads.
Note that we defined the type class as a multiparameter type class, so that instances can put restrictions on the variable t (when flexible instances are enabled). With flexible instance enabled one could use the groupWith function introduced by the SQL like list comprehensions, which requires Ord t (makes sense for lists). One would only require Eq t for sets, for example.
Using this class `q, then group by e' is desugared into:
mgroupWith (\q_v -> e) [| q |] >>= (return . unzip q_v)
(OPTION 2) MonadGroup typeclass WITH the Eq restriction on the type t of projected out values and additional requirements on what mgroupWith should actually return.
class (Monad m, Eq t) => MonadGroup m t where mgroupWith :: (a -> t) -> m a -> m (m a)
Here the type t
is constraint to be a member of the Eq class. With this extra requirement in place one can formulate a law that requires that an instance provides a function that actually performs grouping. Something along the lines:
r = mgroupWith f e 1.) forall c `from` r. (forall e1, e2 `from` c. f e1 == f e2) 2.) forall c1, c2 `from` r. (not (Exists e1 `from` c1, e2 `from` c2. c1 /= c2. f e1 == f e2))
The first law states that all elements in one group
must yield the same value when applied to f.
The second law states that no two elements from two different groups may yield the same value when applied to f.
Unlike the implementation of SQL-like list comprehensions where the groupWith function also performs sorting we don't think it's necessary to require this in general, or formalise this in a law as this would exclude unordered collections (such as Sets).
One can also ask whether such restrictions (including Eq constrain) should be placed on functions in the using clause as well (i.e., non-default grouping functions).
The following three options are somewhat more far fetched. We nevertheless mention them for completeness.
(OPTION 3) Always require explicit grouping function for monad comprehensions
(OPTION 4) Use whatever mgroupWith function is in scope without introducing a new type class.
(OPTION 5) Remove the special identifier 'group' from the monad comprehension syntax and by using typed directed translation apply current 'then group' translation rules when the grouping function f returns a value of type m a -> m (m a).
But this option would add even more magic to the notation as the type of the function f would change the types of the already bound variables. Currently this is done with the use of the explicit special identifier 'group' .
We would prefer option 1 currently, we are however open to suggestions. Option 2 adds a law that we feel will, for certain cases, be overly restricting. Therefor it may be acceptable to trade the ease of reasoning (the laws from option 2) for general usability (option 1). There is in this scenario nothing preventing users to write instances that obey to the above two laws for cases where this makes sense (such as lists).
Furthermore we propose a MonadZip class that is used for parallel monad comprehensions.
We propose the following class:
class Monad m => MonadZip m where mzip :: m a -> m b -> m (a,b) mzip = mzipWith (,) mzipWith :: (a -> b -> c) -> m a -> m b -> m c mzipWith f ma mb = mmap (uncurry f) (mzip ma mb)
where mmap and munzip are defined as:
mmap :: Monad m => (a -> b) -> m a -> m b mmap f ma = ma >>= (return . f) munzip :: Monad m => m (a,b) -> (m a, m b) munzip mab = (mmap fst mab, mmap snd mab)
with the following two laws:
-- Naturality : mmap (f *** g) (mzip ma mb) = mzip (mmap f ma) (mmap g mb)
and
-- Information Preservation: mmap (const ()) ma = mmap (const ()) mb ==> munzip (mzip ma mb) = (ma, mb)
This laws are just monadic versions of the laws given in the Max's earlier post with one change: we only require information preservation law to be enforced for structures of same shape (or actions of same effect in monadic terminology).
The laws leave the behaviour of mzip unspecified when the two structures are of different shape. The MonadZip instance may implement a "cut of behaviour" similar to zip function on lists or fail.
We are open for comments on the proposals above.
comment:21 Changed 6 years ago by
I've just got rid of that SyntaxTable
on MDoExpr
. As discussed above, it's a relic, and getting rid of it tidied up the code quite a bit. You'll want to pull the patch before recording yours
Wed Dec 22 05:22:10 PST 2010 simonpj@microsoft.com * Tidy up rebindable syntax for MDo For a long time an 'mdo' expression has had a SyntaxTable attached to it. However, we're busy deprecating SyntaxTables in favour of rebindable syntax attached to individual Stmts, and MDoExpr was totally inconsistent with DoExpr in this regard. This patch tidies it all up. Now there's no SyntaxTable on MDoExpr, and 'modo' is generally handled much more like 'do'. There is resulting small change in behaviour: now MonadFix is required only if you actually *use* recursion in mdo. This seems consistent with the implicit dependency analysis that is done for mdo. Still to do: * Deal with #4148 (this patch is on the way) * Get rid of the last remaining SyntaxTable on HsCmdTop M ./compiler/deSugar/Coverage.lhs -6 +1 M ./compiler/deSugar/DsArrows.lhs -2 +2 M ./compiler/deSugar/DsExpr.lhs -36 +32 M ./compiler/hsSyn/HsExpr.lhs -12 +7 M ./compiler/hsSyn/HsUtils.lhs -1 +1 M ./compiler/parser/Parser.y.pp -1 +3 M ./compiler/rename/RnBinds.lhs -1 +1 M ./compiler/rename/RnExpr.lhs -39 +15 M ./compiler/rename/RnExpr.lhs-boot -1 +1 M ./compiler/typecheck/TcHsSyn.lhs -14 +4 M ./compiler/typecheck/TcMatches.lhs -21 +7 M ./compiler/typecheck/TcRnDriver.lhs -1 +2
comment:22 Changed 6 years ago by
I made a few changes in order to get rid of that SyntaxTable
as well:
| HsDo (HsStmtContext Name) -- The parameterisation is unimportant -- because in this context we never use -- the PatGuard or ParStmt variant [LStmt id] -- "do":one or more stmts (LHsExpr id) -- The body; the last expression in the -- 'do' of [ body | ... ] in a list comp (SyntaxExpr id) -- The 'return' function, see Note -- [Monad Comprehensions] PostTcType -- Type of the whole expression
| TransformStmt [LStmt idL] -- Stmts are the ones to the left of the 'then' [idR] -- After renaming, the IDs are the binders occurring -- within this transform statement that are used after it (LHsExpr idR) -- "then f" (Maybe (LHsExpr idR)) -- "by e" (optional) (SyntaxExpr idR) -- The 'return' function for inner monad -- comprehensions and... (SyntaxExpr idR) -- ...the '(>>=)' operator. -- See Note [Monad Comprehensions] | GroupStmt [LStmt idL] -- Stmts to the *left* of the 'group' -- which generates the tuples to be grouped [(idR, idR)] -- See Note [GroupStmt binder map] (Maybe (LHsExpr idR)) -- "by e" (optional) (Either -- "using f" (LHsExpr idR) -- Left f => explicit "using f" (SyntaxExpr idR)) -- Right f => implicit; filled in with 'groupWith' (SyntaxExpr idR) -- The 'return' function for inner monad -- comprehensions and... (SyntaxExpr idR) -- ...the '(>>=)' operator. -- See Note [Monad Comprehensions]
Note [Monad Comprehensions] ~~~~~~~~~~~~~~~~~~~~~~~~~~~ Monad comprehensions require seperate 'return' and '>>=' functions. These functions are stored in the 'HsDo' expression and 'GroupStmt'/'TransformStmt' statements. The 'return' function is used to "lift" the body of the monad comprehension: [ body | stmts ] -> stmts >>= \env -> return body In 'then ..' and 'then group ..' statements, the 'return' function is required for nested monad comprehensions, for example a simple 'TransformStmt'... [ body | stmts, then f, rest ] -> f [ env | stmts ] >>= \env' -> [ body | rest ] ...will desugar the same way as above, thus requiring to call 'return' on 'env' again. In any other context than 'MonadComp', both fields for 'return' and '>>=' will stay bottom.
Does that sound reasonable?
comment:23 Changed 6 years ago by
A note on my comment above:
I would prefer to use the MonadComp
context to store the return
function instead of the HsDo
expression. But unfortunately the HsStmtContext
in the HsDo
expression has the argument Name
instead of id
. This makes it impossible to lookup/typecheck/desugar return
correctly, since all those steps require different types. However, changing this type from Name
to the more general id
requires a *lot* of changes everywhere in the code - and I'm not sure if that's worth it. In fact, it requires so many changes that I'd suggest to open a separate ticket if you really want us to put that return
function into the MonadComp
context instead of the HsDo
expression.
comment:24 Changed 6 years ago by
I agree about HsStmtContext
. However I have another idea to suggest about HsDo
, for you to consider.
At the moment, the last qualifier in a do-block is pulled out as the "body" of the do, so that HsDo
has two arguments:
- The
[Stmt]
list - The final
HsExpr
which is the "body"
Now, the last qualifier is a bit special, because it must be an expression, not a binding form. But only a bit. My thought is this:
- Remove the
HsExpr
field of theHsDo
constructor; instead that field simply becomes the last item in the[Stmt]
. - For do-blocks, insist that the last
Stmt
in the list is anExprStmt
. (This could be done in the renamer.) - For list comprehensions, add a new
Stmt
constructor,ReturnStmt
, which carries thereturn
rebindable-syntax term. (The one you dislike attaching toHsDo
.) - The last
Stmt
for aListComp
orMonadComp
must be aReturnStmt
. Moveover,ReturnStmt
would only be allowed forListComp
andMonadComp
. We already have constraints of that kind. For example,TransformStmt
isn't allowed in parallel arrays.
I think that things used to be like this, and in a fit of mistaken zeal I thought it'd be neater to pull out the final Stmt
specially, but I now think that was probably a bad plan.
How does that sound? There would be a fair bit of knock-on changes, but it'd be pretty rountine refactoring I think. It might be worth making this change, validating, and then adding your stuff on top, as a second patch.
Simon
comment:25 Changed 6 years ago by
Ok, I've been working on that a bit and have a couple of questions...
First, am I suppossed to use the existing ExprStmt
for the last statement of
a HsDo
expression or add a separate BodyStmt
? The reason I ask is that
those 2 other arguments to ExprStmt
are pretty much redundant in our body
context as we a) don't need (>>) anymore since we're already at the last
statements and b) always carry around the type of the expression anyway, thus
needing no extra PostTcType (atleast I think so...). And in addition to those
two points an extra BodyStmt
would make it easier to distinguish the
BodyStmt
from a usual ExprStmt
.
Second question is about the typechecking/desugaring functions which don't
explicitely accept a HsDo
expression. Currently they usually get 2 arguments,
the first one beeing the statements, the second one the body. Am I supposed to
change these aswell, or will something like
-- compiler/typecheck/TcExpr.lhs tcExpr (HsDo do_or_lc stmts _) res_ty = tcDoStmts do_or_lc stmts' body res_ty where (stmts', L _ (ExprStmt body _ _)) = (init stmts, last stmts)
be ok aswell?
comment:26 Changed 6 years ago by
I didn't highlight enough above, but my suggestion is to add a new Stmt
constructor, namely ReturnStmt
to use as the last Stmt
of a block. Rather than using ExprStmt
which, as you say, isn't really right. Oh, if you prefer to call it BodyStmt
that's fine too.
Re second point, yes, the whole idea would be to remove the body
argument from tcExpr
and instead have it deal only with a [Stmt]
.
Make sense?
comment:27 Changed 6 years ago by
Cc: | pumpkingod@… added |
---|
comment:28 Changed 6 years ago by
I have a more technical question about the core language generation in the
desugarer. I'm trying to use a function from the GHC.Exts library to simplify
core generation a bit and since I only lookup the functions Id
I have to
manually apply all the types etc. to the function. The code looks something
like this:
do { [..] ; mmap_id <- dsLookupGlobalId mmapName -- new function from GHC.Exts ; let -- Apply types & arguments to 'mmap' tupleElem n = mkApps (Var mmap_id) -- Types: -- mmap :: forall (m :: * -> *) a b. Monad m => .. [ Type m_ty, Type a_ty, Type b_ty -- Arguments: , .. ] ; [..] }
But that expression is missing one more type argument for that Monad m =>
predicate, which leads to the following error (for a simple example with lists
and integers):
C:\Users\Nils\dev\hiwi\ghc\inplace\bin>ghc-stage2.exe -dcore-lint mc_group.hs [2 of 2] Compiling Main ( mc_group.hs, mc_group.o ) *** Core Lint errors : in result of Desugar *** <no location info>: In the expression: GHC.Exts.mmap @ [] @ (GHC.Types.Int, GHC.Types.Int) @ GHC.Types.Int (\ (ds_dqc :: (GHC.Types.Int, GHC.Types.Int)) -> case ds_dqc of _ { (ds_dq9, _) -> ds_dq9 }) Argument value doesn't match argument type: Fun type: GHC.Base.Monad [] => ((GHC.Types.Int, GHC.Types.Int) -> GHC.Types.Int) -> [(GHC.Types.Int, GHC.Types.Int)] -> [GHC.Types.Int] Arg type: (GHC.Types.Int, GHC.Types.Int) -> GHC.Types.Int Arg: \ (ds_dqc :: (GHC.Types.Int, GHC.Types.Int)) -> case ds_dqc of _ { (ds_dq9, _) -> ds_dq9 }
Comparing this core dump with other core dumps, it's clear that there should be
another argument GHC.Base.$fMonad[]
(for this example) to the mmap
function, but I don't know what kind of argument that is and how to get it. So
my question is pretty simple: What function will get me that missing argument?
comment:29 Changed 6 years ago by
Cc: | leather@… added |
---|
comment:30 Changed 6 years ago by
The fact that you want to construct the dictionary argument to mmap in the desugarer is suspicious. It's the type checker that builds dictionary values, and rightly so because doing so can fail, if there isn't a suitable instance; and the need for such an instance might influence the infrerred type of the function.
As you know, the general plan is to attache overloaded methods to the syntax tree, and many Stmts
have such methods attached (SyntaxExpr
).
Can't you use the same approach? Maybe if you explain more of what you are doing?
Simon
comment:31 Changed 6 years ago by
The main reason I did it like that is, that we need separate mmap
functions
for each variable used in a group statement and one more for the statement
itself. For example, a monad comprehension like this:
[ x+y+z | x <- (someList_x :: [Int]) , y <- (someList_y :: [String]) , z <- (someList_z :: [SomeData]) , then group by x ]
would build up a context of 4 different mmaps
:
mmap_x :: ((Int, String, SomeData) -> Int) -> [(Int, String, SomeData)] -> [Int] mmap_y :: ((Int, String, SomeData) -> String) -> [(Int, String, SomeData)] -> [String] mmap_z :: ((Int, String, SomeData) -> SomeData) -> [(Int, String, SomeData)] -> [SomeData] mmap_unzip :: ([(Int, String, SomeData)] -> ([Int, String, SomeData])) -> [[(Int, String, SomeData)]] -> [([Int], [String], [SomeData])]
(see translation rules, mmap
is basicly the same as liftM
or just m >>= return . f
)
So, looking up each of those statements, typechecking it and storing it in a
list of SyntaxExpr
wouldn't be the nicest solution. Even more since there
actually is nothing to "check" on those types - we know all of them already and
the typechecker shouldn't ever fail on those functions if the rest is correct.
Currently, list comprehensions use the same approach. They lookup map
to
desugar group statements (see deSugar/DsListComp.lhs
, line 147+) and apply
the types by hand to that function. Obviously, they don't run into the same
issue, since map
doesn't require a dictionary.
Would it be possible to use (somehow "extract" it) that dictionary of those bind/return functions used by the comprehension (and not the group statement itself)? If not I'd propose to change (unless you have another idea):
-- hsSyn/HsExpr.lhs | GroupStmt -- ... [(idR, idR)] -- See Note [GroupStmt binder map] -- ...
into a list of [(idR, idR, SyntaxExpr idR)]
, where the SyntaxExpr
would be
bottom for everything but monad comprehensions, and add another field
SyntaxExpr idR
to the GroupStmt
for the final mmap unzip ..
call.
comment:32 Changed 6 years ago by
I think what you want the type checker to do is to give you a term, attached to the GroupStmt
of type
imap :: forall a b. (a->b) -> m a -> m b
where m
is the type of the monad. Then you can instantiate this imap
in the desugarer, with explicit applications, just as is done with plain map
now.
So the type checker need only produce one term, with the above type. That should not be hard.
Simon
comment:33 Changed 6 years ago by
That looks sweet, but how would you typecheck that? My naiv implementation
-- Type check 'mmap' with 'forall a b. (a -> b) -> m_ty a -> m_ty b' ; mmap_op' <- tcSyntaxOp MCompOrigin mmap_op $ mkForAllTy alphaTyVar $ mkForAllTy betaTyVar $ (alphaTy `mkFunTy` betaTy) `mkFunTy` (m_ty `mkAppTy` alphaTy) `mkFunTy` (m_ty `mkAppTy` betaTy)
fails on compilation:
Couldn't match expected type `forall a b. (a -> b) -> [a] -> [b]' with actual type `(a -> b) -> m a -> m b' In a stmt of a monad comprehension: then group by x using groupWith
comment:34 Changed 6 years ago by
Never mind my last post. I got it figured out. Late night work's paying off - monad comprehensions finally support the group
statement. :)
comment:35 Changed 6 years ago by
Good news! I'm almost done with the implementation. Monad comprehensions now support:
- Binding statements:
[ x + y | x <- Just 1, y <- Just 2 ]
=>Just 3
- Guards:
[ x | x <- [1..5], x <= 3 ]
=>[1,2,3]
- Transform statements:
[ x | x <- [1..5], then take 2 ]
=>[1,2]
- Grouping statements:
[ x | x <- [1,1,2,2,3,3], then group by x ]
=>[[1,1],[2,2],[3,3]]
- Parallel/zip statements:
[ (x,y) | x <- [1,2] | y <- [3,4] ]
=>[(1,3),(2,4)]
All these features are enabled by default if you use the MonadComprehensions
language flag. Note, that there are different requirements for some of those statements:
- Guards require a
MonadPlus
instance since it's usingguard
fromControl.Monad
- Grouping requires a
MonadGroup
instance, a new type class which we added to thebase
package (unless you use a different grouping function viathen group by x using ..
) - Parallel statements require a
MonadZip
instance, another new type class for thebase
package.
At least for now, both new type classes were put into base
since they're
supposed to be used by the endusers (people might come up with their own
groupable/zipable monads). If you have any concerns with that I could move them
out of base
into another package of course.
In the next couple of days I'll clean up the code a bit, add/complete the documentation, add some tests to the testsuite and finally merge our working repo with current head before I sent in those patches (you want git patches, right?).
As usual - if you have any concerns, please let me know!
comment:36 Changed 6 years ago by
That sounds good. Well done! From the sound of it you managed to follow my suggestions in the exchanges above? Anyway I'll take a look when you have the patches ready. Do highlight any bits you feel are less than beautiful, in case I can think of a nicer way to do it.
Simon
comment:37 Changed 6 years ago by
Hmmm, I found one more strange bug. Maybe you could help me understanding it, I can't really see why/where it happens.
The error occurs when I try to load a .hs file with one single grouping statement in ghci:
{-# LANGUAGE MonadComprehensions #-} foo = [ a | a <- [5], then group by a ] :: [[Int]]
The error message itself is pretty long, so I posted it on a pastebin: http://npaste.de/y9/
The strange thing is, that I can compile that file just fine (after adding a main = print foo
) and it passes the core validation -dcore-lint
. I can also define that statement directly in ghci:
Prelude> :set -XMonadComprehensions Prelude> let foo = [ x | x <- [5], then group by x ] Prelude> foo [[5]]
But for some reason, I can not load it from a file. All other statements work as expected, and as far as I can tell I haven't touched any ghci code. At least none that should be somehow special for grouping statements.
If it is of any help, I posted a diff of my current changes on my pastebin: http://npaste.de/yB/ This diff won't apply to current HEAD, and it's not final at all. Just to give you a quick summary of what I've done so far.
comment:38 Changed 6 years ago by
I suggest you add -dcore-lint
to your ghci
command line too.
Without being able to reproduce it's hard for me to comment. It's certainly very wierd that it's ok in GHCi but not in batch mode.
Simon
comment:40 Changed 6 years ago by
comment:41 Changed 6 years ago by
OK, thats weird. I'll wait until you've got a patch I can reproduce it with.
comment:42 Changed 6 years ago by
You should be able to apply these two patches to ghc.git and the base (darcs) package.
The base patch is pretty much final, the compiler patch is almost done (some comments still use the old zipM
name instead of the new mzip
etc), but you should be able to see if you can reproduce the error we were talking about.
However, we didn't manage to test this with the latest HEAD because of #4990 and #4991, but it worked fine with the version a couple of days ago…
Changed 6 years ago by
Attachment: | 0001-Monad-Comprehensions-ticket-4370.patch added |
---|
Changed 6 years ago by
Attachment: | group_zip.patch added |
---|
comment:43 Changed 6 years ago by
I just did a rebuild with the darcs repo and everything did work as expected (we were using git before). I'll upload the darcs patch for the compiler aswell.
So to test this you should:
- Apply the
group_zip.patch
patch to the base library and - apply the
monad-comprehension-alpha.patch
patch to the main ghc repo.
There should be no conflicts/errors.
Changed 6 years ago by
Attachment: | monad-comprehensions-alpha.patch added |
---|
comment:44 Changed 6 years ago by
Status: | new → patch |
---|
comment:45 Changed 6 years ago by
The user guide documentation is done, patch attached.
A compiled version is available at: http://n-sch.de/hdocs/ghc/html/users_guide/syntax-extns.html#monad-comprehensions
comment:46 Changed 6 years ago by
This patch adds MonadComprehensions
to the Language.Haskell.Extension
library of the Cabal
package and fixes the only test in the testsuite that got broken by my monad comprehension patch (T4437).
It also fixes some of the references to the user guide.
Changed 6 years ago by
Attachment: | mc-user-guide.patch added |
---|
comment:47 Changed 6 years ago by
Thanks for all your work here. I'm travelling at the moment, and then the ICFP deadline presses, but I'll review can commit your patches for the upcoming 7.2 release.
One thing: earlier in the ticket you give the desugaring rules. Could you transfer them to a GHC wiki page, linked from the "Contributed documentation" section of http://hackage.haskell.org/trac/ghc/wiki/Commentary? To make sense of it you, probably want to cut/paste a summary of the goal, and an overview of the implementation. Nothing too detailed, becuase documentation separate from code tends to go out of date. Just a road-map of where to look for the changes, and any "watch out for this" points you tripped over. Worth pointing back to this roadmap and the desugaring rules from comments in the code.
Simon
comment:48 Changed 6 years ago by
Patch for the testsuite added. One note: I've added a expected_broken_for(4370, ['ghci','hpc'])
flag to all tests wich use the grouping statement, since ghci still fails with grouping statements…
I also fixed a few bugs in the compiler (mostly minor bugs in the error messages) and will upload the new version aswell.
Unless somebody comes up with a solution to that ghci error I'd suggest to apply these patches and open a separate bug ticket, so someone with the necessary expertise will be able to fix it. I will continue to try to fix that ghci bug, but currently I don't see why this happens at all (ghci even generates different core code, see http://npaste.de/zV/ (ghci) vs http://npaste.de/zW/ (ghc) – the >>=
on line 31 of the ghci code makes no sense at all…).
So, to commit these patches you should apply...
monad-comprehensions-final.patch
andmc-user-guide.patch
to the main repomc-testsuite.patch
to the testsuitegroup_zip.patch
to thebase
packagemc-cabal-extensions.patch
to theCabal
package
The alpha version and that git commit can be ignored.
And just to let you know, I'll be on vacations next week, so I won't be able to do any work. I'll add that wiki entry when I come back.
Changed 6 years ago by
Attachment: | monad-comprehensions-final.patch added |
---|
Changed 6 years ago by
Attachment: | mc-testsuite.patch added |
---|
comment:49 Changed 6 years ago by
So, any news? Have you had the time to take a look at my patches? It's been a while since the last update and I just thought I'd ask whether or not you forgot about it? :)
- Nils
comment:50 Changed 6 years ago by
No, I have not looked at them. But neither have I forgotten. The ICFP deadline was 24 March and I was totally focused on that. April is also ridiculously busy. The first two weeks of May are much better. We plan to release GHC 7.2 sometime in mid to late May, and it will have your stuff in it by hook or by crook.
Simon
comment:51 Changed 6 years ago by
I migrated all patches to git and resolved some conflicts. I also added a munzip to the Control.Monad.Zip
module which is convenient to have and also is refered to in our paper.
Files will get attached, the old ones should be ignored (there's no way to delete them?). Patching should be done via git am <file>
where <file>
is
ghc-0001-monad-comprehensions-compiler.patch
andghc-0002-monad-comprehensions-user-guide.patch
in the ghc git root directorytestsuite-0001-monad-comprehensions-test-suite.patch
in thetestsuite
git directorybase-0001-monad-comprehensions-Group-and-Zip-monad.patch
in thelibraries/base
git directoryCabal-0001-monad-comprehensions-cabal-extensions.patch
in thelibraries/Cabal
git directory
Changed 6 years ago by
Attachment: | Cabal-0001-monad-comprehensions-cabal-extensions.patch added |
---|
(git) patch for Cabal library
Changed 6 years ago by
Attachment: | base-0001-monad-comprehensions-Group-and-Zip-monad.patch added |
---|
(git) patch for base library
Changed 6 years ago by
Attachment: | ghc-0001-monad-comprehensions-compiler.patch added |
---|
(git) patch for compiler (1/2)
Changed 6 years ago by
Attachment: | ghc-0002-monad-comprehensions-user-guide.patch added |
---|
(git) patch for compiler (2/2)
Changed 6 years ago by
Attachment: | testsuite-0001-monad-comprehensions-test-suite.patch added |
---|
(git) patch for testsuite
comment:52 Changed 6 years ago by
Oh, apologies; I should have mentioned that I rolled up my sleeves three days ago and did the migration myself. I'm deep in hacking mode now.
Simon
comment:53 Changed 6 years ago by
Cool ok. :) Although you might want to use my base-patch anyway since it got that extra "munzip" function in it which is missing in the previous patches (or you add it by hand of course).
comment:54 Changed 6 years ago by
Resolution: | → fixed |
---|---|
Status: | patch → closed |
OK. I've merged the monad-comprehension branch with the master! Hooray. Check it out and see if it works for you. Thanks for your work on this.
I have not done anything about updating Cabal to know about MonadComprehensions. I'm not sure what the protocol for that is.
Simon
comment:55 Changed 6 years ago by
Nils, if you felt up to it, it would be a fine thing to have a page on the Hsakell Wiki describing monad comprehensions and what you can do with the. There's plenty of precedent for this; see "Collaborative documentation" at http://haskell.org/haskellwiki/GHC. With a relatively complex feature the user-manual documentation isn't that helpful, whereas on a more discursive page you can give lots of examples. You could use your blog post as a basis.
BTW can you check the changes I made to the user manual to ensure I didn't get anything wrong? Thanks.
Simon
comment:56 Changed 6 years ago by
Nils and Simon, thanks for the fantastic work that made the monad comprehensions extension available in GHC.
Currently, I am working on a new version of Database Supported Haskell (DSH) that is based on monad comprehensions (the original motivation posted above in this trac ticket). We are also developing other instructive examples that use the monad comprehension notation.
I will post the examples and other related material in a couple of weeks time on the wiki page that was started by Nils: http://hackage.haskell.org/trac/ghc/wiki/MonadComprehensions
Cheers, George
comment:57 Changed 6 years ago by
Hurrah. I'm glad it is proving useful. I always wonder which of GHC's features are used, and how much!
comment:58 Changed 6 years ago by
The userguide looks fine, I have just one more question. Last time I checked "MonadComprehensions" didn't allow transform or parallel statements by default. Did you change that on purpose or did I forgot to test that properly before sending in those patches?
GHCi, version 7.1.20110504: http://www.haskell.org/ghc/ :? for help Prelude> :set -XMonadComprehensions Prelude> [ x | x <- [1..], then take 5 ] <interactive>:0:19: Unexpected transform statement in a monad comprehension Use -XTransformListComp Prelude> [ x+y | x <- [1,2] | y <- [1,2] ] <interactive>:0:18: Unexpected parallel statement in a monad comprehension Use -XParallelListComp
Those errors shouldn't occur…
I currently cannot get the latest version to see whether or not this is already fixed (my local git is messed up somehow), but I guess it's not. :)
comment:59 follow-up: 60 Changed 6 years ago by
I intended it. It seems reasonable that
-XMonadComprehensions
makes list comprehensions be interpreted as monad comprehensions-XTransformListComp
adds the SQL-like comprehension support, to either list or monad comprehensions- Ditto for
-XParallelListComp
Admittedly TransformListComp
then is not necessarily about list comprehensions. Maybe is should be TransformComp
; and similarly for ParallelComp
?
That woudl be doable; we'd have to go through a cycle of deprecation to encourage people to adopt the new flag name.
Does the logic make sense though?
Simon
comment:61 Changed 6 years ago by
Owner: | nsch deleted |
---|---|
Resolution: | fixed |
Status: | closed → new |
Currently, the munzip function is not a member of the MonadZip class. It has the following type signature and definition:
munzip :: MonadZip m => m (a,b) -> (m a, m b) munzip mab = (liftM fst mab, liftM snd mab)
When developing monad comprehension examples for various MonadZip instances, I found that it is useful to allow a MonadZip instance to provide more efficient unzipping function.
I suggest we make the munzip function a member of the MonadZip class by using the current definition as a default implementation. The laws that the munzip member should satisfy is already documented in the module.
The small patch that is attached to this trac ticket implements the proposed change.
Cheers, George
Changed 6 years ago by
Attachment: | 0001-Move-the-munzip-function-in-the-Zip-type-class.patch added |
---|
Make the munzip function a member of the Zip type class
comment:62 Changed 6 years ago by
I have developed a few examples that use RebindableSyntax in combination with MonadComprehensions. Everything worked as expected for standard comprehensions (i.e., for the generator and filter clauses). Unfortunately I was not able to use RebindableSyntax with extended comprehensions (i.e., with the then and then group clauses).
Here I will just give one example that makes use of monad comprehensions as set comprehensions. The example demonstrates how to use MonadComprehensions with RebindableSyntax and highlights problems that I have encountered when rebinding the fmap and mgroupWith functions used in the desugaring translation of monad comprehensions extended with the "then group" clause. I remember the problems were not present with the patch by Nils, but I can not say that with absolute certainty as I am not able to reproduce that version of GHC at the moment.
OK let me jump to the example straight away. I will start with the language pragmas and necessary import statements:
{-# LANGUAGE RebindableSyntax, MonadComprehensions, TransformListComp #-} module Main where import Prelude (Eq, Ord, IO, String, Bool (..), Integer, map, fromInteger, print, odd, undefined, error) import qualified Data.Set as Set import Data.Set (Set) import GHC.Exts (groupWith)
Now let us rebind the monadic combinators that are used in the desugaring translation of standard comprehensions to the set specific versions (I could as well use Ganesh's rmonad package and RMonad instance defined in the package).
return :: a -> Set a return = Set.singleton (>>=) :: (Ord a, Ord b) => Set a -> (a -> Set b) -> Set b s >>= f = Set.fold Set.union Set.empty (Set.map f s) (>>) :: (Ord a, Ord b) => Set a -> Set b -> Set b s1 >> s2 = s1 >>= (\ _ -> s2) guard :: Bool -> Set () guard False = Set.empty guard True = Set.singleton () fail :: String -> Set a fail = error
Now we can use standard monad comprehensions as set comprehensions:
set1 :: Set Integer set1 = Set.fromList [0 .. 9] set2 :: Set Integer set2 = [ x | x <- set1, odd x]
So far everything works as expected for standard monad comprehensions.
Now let us attempt to use monad comprehensions extended with the "then group" clause for sets. Let me rebind the fmap and mgroupWith functions:
fmap :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b fmap = Set.map mgroupWith :: (Ord a, Ord b) => (a -> b) -> Set a -> Set (Set a) mgroupWith f s = Set.fromList (map Set.fromList (groupWith f (Set.toList s)))
and consider the following example that makes use of the "then group" clause:
set3 :: Set (Set Integer) set3 = [ x | x <- set1, then group by x]
For this example the GHC type checker produces the following errors:
Set.hs:41:25: No instances for (Ord a, Ord b) arising from a use of `fmap' In the expression: fmap In a stmt of a monad comprehension: then group by x In the expression: [x | x <- set1, then group by x] Set.hs:41:25: No instance for (Ord a) arising from a use of `mgroupWith' In the expression: mgroupWith In a stmt of a monad comprehension: then group by x In the expression: [x | x <- set1, then group by x]
The GHC type checker does not allow constrains to be imposed on the type contained by the monad when the fmap and mgroupWith functions are rebinded.
Simon and Nils, is it possible to relax the restriction when the RebindableSyntax extension is turned on?
Your input on this issue would be very much appreciated as it may pave the way for more useful applications and help to clarify the GHC documentation on rebindable syntax.
Thanks in advance, George
comment:63 Changed 6 years ago by
Milestone: | 7.4.1 → 7.2.1 |
---|---|
Priority: | normal → high |
Status: | new → patch |
comment:64 Changed 6 years ago by
Owner: | set to simonpj |
---|
OK I have applied the munzip change. Ian can you merge? That leaves George's question still to be attended to.
Simon
commit 2ceacbc35d9c5f4bc6cbcfa46f64d333f9dc53c7 Author: George Giorgidze <giorgidze@gmail.com> Date: Mon Jul 4 21:01:12 2011 +0200 Move the munzip function in the Zip type class; >--------------------------------------------------------------- Control/Monad/Zip.hs | 14 ++++++++++---- 1 files changed, 10 insertions(+), 4 deletions(-) diff --git a/Control/Monad/Zip.hs b/Control/Monad/Zip.hs index 8c431bd..9d71a53 100644 --- a/Control/Monad/Zip.hs +++ b/Control/Monad/Zip.hs @@ -3,6 +3,7 @@ -- | -- Module : Control.Monad.Zip -- Copyright : (c) Nils Schweinsberg 2011, +-- (c) George Giorgidze 2011 -- (c) University Tuebingen 2011 -- License : BSD-style (see the file libraries/base/LICENSE) -- Maintainer : libraries@haskell.org @@ -40,8 +41,13 @@ class Monad m => MonadZip m where mzipWith :: (a -> b -> c) -> m a -> m b -> m c mzipWith f ma mb = liftM (uncurry f) (mzip ma mb) -instance MonadZip [] where - mzip = zip + munzip :: m (a,b) -> (m a, m b) + munzip mab = (liftM fst mab, liftM snd mab) + -- munzip is a member of the class because sometimes + -- you can implement it more efficiently than the + -- above default code. See Trac #4370 comment by giorgidze -munzip :: MonadZip m => m (a,b) -> (m a, m b) -munzip mab = (liftM fst mab, liftM snd mab) +instance MonadZip [] where + mzip = zip + mzipWith = zipWith + munzip = unzip
comment:65 Changed 6 years ago by
Milestone: | 7.2.1 → _|_ |
---|---|
Owner: | simonpj deleted |
Priority: | high → normal |
Status: | patch → new |
George, concerning your question, the trouble is that (as the user manual says) we check that the fmap
function in scope has type
fmap :: forall a b. (a->b) -> n a -> n b
Why those foralls? Because we are going to apply fmap
to lots of different arguments. See Section 4.4 of http://research.microsoft.com/en-us/um/people/simonpj/papers/list-comp/list-comp.pdf for a discussion of why we ask for polymorphism.
So I don't know how to give you what you want here... but I can also see your problem.
In short, its not just an implementation bug; there's something substantial to think about here. I'll re-open the ticket, to keep track of the question, but I'm not sure how to proceed.
comment:66 Changed 6 years ago by
Cc: | anton.nik@… added |
---|
comment:67 Changed 4 years ago by
does some of the constraint kinds / poly kinds machinery allow the remainder of this ticket to be addressed?
comment:68 Changed 4 years ago by
Cc: | alex@… added |
---|
comment:69 Changed 22 months ago by
Cc: | gideon@… removed |
---|
comment:70 Changed 9 months ago by
Differential Rev(s): | → Phab:D2247 |
---|---|
Status: | new → patch |
comment:71 Changed 9 months ago by
bgamari, is this the right ticket?
Also, I wish we wouldn't reopen issues with mega-threads like this one. Monad comprehensions were indeed added and you have to get to comment:62 to find out what the open part of this ticket is. Much easier for posterity if the remaining piece is split out into its own ticket once the comment thread has become very long.
comment:72 Changed 9 months ago by
Differential Rev(s): | Phab:D2247 |
---|---|
Resolution: | → fixed |
Status: | patch → closed |
Of dear, indeed it isn't; sorry for the noise.
Max replies:
They do: see the comments by Michael Adams at http://haskell.org/haskellwiki/Simonpj/Talk:ListComp. Last I checked, the code there was slightly buggy but correct in spirit.
What doesn't generalise is the zip comprehensions extension:
The required operator ::
m a -> m b -> m (a, b)
is that of the ZipList applicative functor, not that of the standard applicative functor for lists. Probably to generalise this you need a new typeclass like this one (copied from my own library):It probably needs some extra laws to say how it interacts with the Monad operators.
Pretty easy IMHO. The list comprehensions are already half-set up for this job, and you should be able to reuse lots of the code that handles the monad notation desugaring.
See above.
I thought it was rejected because it caused newbies to get confusing type error messages: they expected *list* error messages but got errors mentioning a scary *Monad* thing. Personally I'm not sure how to solve that, but if it's only available as an extension this won't cause a problem.