Re: [Haskell] Mixing monadic and non-monadic functions
One of Mark Jones's articles suggests something like class Plus a b c | a b -> c where (+) :: a -> b -> c Would instance (Plus a b c, Monad m) => Plus (m a) (m b) (m c) where mx + my = do x <- mx y <- my return (x + y) do what you're looking for? Chad Scherrer Computational Mathematics Group Pacific Northwest National Laboratory "Time flies like an arrow; fruit flies like a banana." -- Groucho Marx ------------------------------------------------------------------ Original message: Hi, Sean's comment (yeah, it was like a billion years ago, just catching up) is something that I've often thought myself. I want the type system to be able to do "automatic lifting" of monads, i.e., since [] is a monad, I should be able to write the following: [1,2]+[3,4] and have it interpreted as "do {a<-[1,2]; b<-[3,4]; return (a+b)}". Also, I would have Reader (+1) + Reader (+4) == Reader (\x -> 2*x+5) The point I want to make is that this is much more general than IO or monads! I think we all understand intuitively what mathematicians mean when they add two sets {1,2}+{3,4} (i.e. { x+y | x\in {1,2}, y\in {3,4}}) or when they add functions (f+g)(x) where f(x)=x+1 and g(x)=x+4 So "automatic lifting" is a feature which is very simple to describe, but which gives both of these notations their intuitive mathematical meaning - not to mention making monadic code much tidier (who wants to spend their time naming variables which are only used once?). I think it deserves more attention. I agree that in its simplest incarnation, there is some ugliness: the order in which the values in the arguments are extracted from their monads could be said to be arbitrary. Personally, I do not think that this in itself is a reason to reject the concept. Because of currying, the order of function arguments is already important in Haskell. If you think of the proposed operation not as lifting, but as inserting `ap`s: return f `ap` x1 `ap` ... `ap` xn then the ordering problem doesn't seem like such a big deal. I mean, what other order does one expect, than one in which the arguments are read in the same order that 'f' is applied to them? Although it is true that in most of the instances where this feature would be used, the order in which arguments are read from their monads will not matter; yet that does not change the fact that in cases where order *does* matter it's pretty damn easy to figure out what it will be. For instance, in print ("a: " ++ readLn ++ "\nb: " ++ readLn) two lines are read and then printed. Does anybody for a moment question what order the lines should be read in? Frederik
On Thu, Sep 08, 2005 at 09:30:34AM -0700, Scherrer, Chad wrote:
One of Mark Jones's articles suggests something like
class Plus a b c | a b -> c where (+) :: a -> b -> c
Would
instance (Plus a b c, Monad m) => Plus (m a) (m b) (m c) where mx + my = do x <- mx y <- my return (x + y)
do what you're looking for?
Hi Chad, I'm not sure exactly what you have in mind. Obviously I want something that applies to all functions, with any number of arguments, and not just (+). Furthermore, it should handle cases like 1+[2,3] where only one value is monadic. Keean Schupke's suggestion sounds more likely to be useful, but I'm still reading it. In any case, a minimum of syntactic overhead is desired. Frederik
------------------------------------------------------------------ Original message:
Hi,
Sean's comment (yeah, it was like a billion years ago, just catching up) is something that I've often thought myself.
I want the type system to be able to do "automatic lifting" of monads, i.e., since [] is a monad, I should be able to write the following:
[1,2]+[3,4]
and have it interpreted as "do {a<-[1,2]; b<-[3,4]; return (a+b)}".
Also, I would have
Reader (+1) + Reader (+4) == Reader (\x -> 2*x+5)
The point I want to make is that this is much more general than IO or monads! I think we all understand intuitively what mathematicians mean when they add two sets
{1,2}+{3,4} (i.e. { x+y | x\in {1,2}, y\in {3,4}})
or when they add functions
(f+g)(x) where f(x)=x+1 and g(x)=x+4
So "automatic lifting" is a feature which is very simple to describe, but which gives both of these notations their intuitive mathematical meaning - not to mention making monadic code much tidier (who wants to spend their time naming variables which are only used once?). I think it deserves more attention.
I agree that in its simplest incarnation, there is some ugliness: the order in which the values in the arguments are extracted from their monads could be said to be arbitrary. Personally, I do not think that this in itself is a reason to reject the concept. Because of currying, the order of function arguments is already important in Haskell. If you think of the proposed operation not as lifting, but as inserting `ap`s:
return f `ap` x1 `ap` ... `ap` xn
then the ordering problem doesn't seem like such a big deal. I mean, what other order does one expect, than one in which the arguments are read in the same order that 'f' is applied to them?
Although it is true that in most of the instances where this feature would be used, the order in which arguments are read from their monads will not matter; yet that does not change the fact that in cases where order *does* matter it's pretty damn easy to figure out what it will be. For instance, in
print ("a: " ++ readLn ++ "\nb: " ++ readLn)
two lines are read and then printed. Does anybody for a moment question what order the lines should be read in?
Frederik
On Thu, Sep 08, 2005 at 01:30:51PM -0700, Frederik Eaton wrote:
On Thu, Sep 08, 2005 at 09:30:34AM -0700, Scherrer, Chad wrote:
One of Mark Jones's articles suggests something like
class Plus a b c | a b -> c where (+) :: a -> b -> c
Would
instance (Plus a b c, Monad m) => Plus (m a) (m b) (m c) where mx + my = do x <- mx y <- my return (x + y)
do what you're looking for?
Hi Chad,
I'm not sure exactly what you have in mind. Obviously I want something that applies to all functions, with any number of arguments, and not just (+). Furthermore, it should handle cases like 1+[2,3] where only one value is monadic. Keean Schupke's suggestion sounds more likely to be useful, but I'm still reading it. In any case, a minimum of syntactic overhead is desired.
I think what he means is that if we had a somewhat better design of the prelude type classes, we would be able to do this in haskell now for most interesting operations. as we could write an instance like instance (Monad m,Num a) => Num (m a) where .. .. of course, we can't do this because Num has Ord and Show as superclasses when it really doesn't need to. (we would have to create a separate class for 'pattern matchable nums' if we got rid of those, but that is no problem other than being non-haskell-98 compatable). Solving this 'class inflexibility' problem in general is something I have given some thought too. I will let everyone know if I figure something out... John -- John Meacham - ⑆repetae.net⑆john⑈
On 2005-09-08, John Meacham <john@repetae.net> wrote:
of course, we can't do this because Num has Ord and Show as superclasses when it really doesn't need to. (we would have to create a separate class for 'pattern matchable nums' if we got rid of those, but that is no problem other than being non-haskell-98 compatable). Solving this 'class inflexibility' problem in general is something I have given some thought too. I will let everyone know if I figure something out...
Has anyone found any problem with your "superclasses" proposal? http://repetae.net/john/recent/out/supertyping.html -- Aaron Denney -><-
Am Donnerstag, 8. September 2005 22:30 schrieb Frederik Eaton:
Hi Chad,
I'm not sure exactly what you have in mind. Obviously I want something that applies to all functions, with any number of arguments, and not just (+). Furthermore, it should handle cases like 1+[2,3] where only one value is monadic. Keean Schupke's suggestion sounds more likely to be useful, but I'm still reading it. In any case, a minimum of syntactic overhead is desired.
Frederik
Hello, I doubt that it is a good thing to extend the language in a way that such far reaching declarations are automatically generated. I would like to have more control about which things are declared and which are not and also in which way the are declared. In addition, I'm against giving a specific class (Monad) a very special position among all classes. One of the advantages of functional programming languages is that the language directly supports very little features but is so powerful that you can define new features by using the language. Maybe, it would be good that those people who want this automatic lifting of functions implement it using Template Haskell. Best regards, Wolfgang
Wolfgang Jeltsch <wolfgang@jeltsch.net> writes:
I'm not sure exactly what you have in mind. Obviously I want something that applies to all functions, with any number of arguments, and not just (+). Furthermore, it should handle cases like 1+[2,3] where only one value is monadic.
I doubt that it is a good thing to extend the language in a way that such far reaching declarations are automatically generated.
I agree. The original request was for something like [1,2] + [3,4] to be automatically lifted into a monad. But surely it is not too difficult to define the required behaviour precisely (and only) where needed, e.g. (+.) = liftM2 (+) [1,2] +. [3,4] Where the functions in question are not infix, you don't even need to define a new name, just use (liftM fn) directly inline! Regards, Malcolm
Malcolm Wallace wrote:
Wolfgang Jeltsch <wolfgang@jeltsch.net> writes:
I'm not sure exactly what you have in mind. Obviously I want something that applies to all functions, with any number of arguments, and not just (+). Furthermore, it should handle cases like 1+[2,3] where only one value is monadic.
I doubt that it is a good thing to extend the language in a way that such far reaching declarations are automatically generated.
I agree. The original request was for something like [1,2] + [3,4] to be automatically lifted into a monad. But surely it is not too difficult to define the required behaviour precisely (and only) where needed, e.g.
(+.) = liftM2 (+)
[1,2] +. [3,4]
Why not make the monad an instance of Num, then you do not proliferate meaningless similar symbols... besides which I am sure all the good ones are used in libraries already (like +. <+> etc) ;) instance (Monad m, Show a) => Show (m a) ... instance (Monad m, Ord a) => Ord (m a) ... instance (Monad m, Num a,Show (m a),Ord (m a)) -> Num (m a) where (+) = liftM2 (+) The instances for Show and Ord can be empty if you don't need the functionality... Regards, Keean.
Keean Schupke wrote:
I'm not sure exactly what you have in mind. Obviously I want something that applies to all functions, with any number of arguments, and not just (+). Furthermore, it should handle cases like 1+[2,3] where only one value is monadic.
Just noticed the 1+[1,2] case... I am not certain whether this is possible - it is outside the scope of the formal definiton of Haskell and may rely on implementation details of the compiler/interpreter.
Effectivly we need to redefine list as a class, then (Num a) can be made an instance of the class... See my implementation of Joy in the HList library. (this lifts numbers into an AST rather than a list) - this however uses type level programming and has problems with non static types (IE you need to use existentials for lists who's values is not known at compile time)... The easy answer is to define a type that contains both singletons and lists... although the type constructors may not look as neat. Regards, Keean.
On 9/9/05, Keean Schupke <k.schupke@imperial.ac.uk> wrote:
Just noticed the 1+[1,2] case... I am not certain whether this is possible - it is outside the scope of the formal definiton of Haskell and may rely on implementation details of the compiler/interpreter.
While this is outside the scope of the current Num class, if we adopt the suggestion to redefine the standard classes using functional dependencies (which is, I think, a useful addition to the standard prelude anyway), we have, for example: class Plus a b c | a b -> c where (+) :: a -> b -> c instance (Plus a b c, Functor f) => a -> f b -> f c where a + fb = fmap (a +) fb and so forth. However, this doesn't generalize obviously (in any way that I see) to generic two argument functions, which seemed to be what Frederik wanted. /g
On 2005-09-09, Keean Schupke <k.schupke@imperial.ac.uk> wrote:
Keean Schupke wrote:
I'm not sure exactly what you have in mind. Obviously I want something that applies to all functions, with any number of arguments, and not just (+). Furthermore, it should handle cases like 1+[2,3] where only one value is monadic.
Just noticed the 1+[1,2] case... I am not certain whether this is possible - it is outside the scope of the formal definiton of Haskell and may rely on implementation details of the compiler/interpreter.
Effectivly we need to redefine list as a class, then (Num a) can be made an instance of the class... See my implementation of Joy in the HList library. (this lifts numbers into an AST rather than a list) - this however uses type level programming and has problems with non static types (IE you need to use existentials for lists who's values is not known at compile time)...
The easy answer is to define a type that contains both singletons and lists... although the type constructors may not look as neat.
I thought the easy answer would be to inject non-monadic values into the monad (assuming one already rejiggered things to do automatic lifting). -- Aaron Denney -><-
By the way, I thought it would be obvious, but a lot of people seem to be missing the fact that I'm not (as Sean, I believe, isn't) requesting limited support for 1 or 2 or 3 argument functions or certain type classes to be applied to monads, or for certain operations to defined on certain types. I know at least how to define type classes and functions. If this is what I wanted I would probably do it myself.
I thought the easy answer would be to inject non-monadic values into the monad (assuming one already rejiggered things to do automatic lifting).
I don't know if this is the right way of looking at it. Do you have an example? My idea is that you should be able to have code like this: -- (a) m3 :: a -> m b m6 = do m1 m2 m3 (p1 (p2 p3 (p4 m4 p5)) p6) m5 - where the m* values are functions returning monads and the p* values are so-called "pure" functions, i.e. functions which don't take monad values or return monad results (so currently the above code won't type-check beacuse of m4) - but have it be interpreted as: -- (b) m3 :: a -> m b m6 = do m1 m2 v <- m4 m3 (p1 (p2 p3 (p4 v p5) p6) m5 Note that in (a), "pure" values are never used where monads are asked for, only the other way around. I think that supporting syntax (a) for semantics (b) should be a feature because: (1) it is (usually) obvious what (a) means; (2) it eliminates the single-use variable 'v' - single-use variables like this occur a lot in monadic Haskell code, and I think they make it harder to read and write; (3) it would support the math-like syntax that I presented in my original message. It might be hard to modify the type checker to get it to work, but I think it is possible, and I see no reason not to be as general as possible. Would it mean treating the 'Monad' class specially? Perhaps, but I don't think this is a reason to avoid it. Further, it is likely that whatever is done to extend the type checker could be given a general interface, which Monad would simply take advantage of, using a meta-declaration in the same spirit as "infixr" etc. Also, I do not think that template haskell is powerful enough to support this, but I'm willing to be proven wrong. Frederik -- http://ofb.net/~frederik/
Despite having a fairly mathematical background, I don't really care for the proposed syntax. myList :: [[Integer]] myList = return [1,2,3,4] Is myList equal to [[1,2,3,4]] or [[1],[2],[3],[4]]? Either interpretation is possible if there is automatic lifting about. If the lifting only occurs when a type error would otherwise have happened, then there will be cases where genuine type errors are happening and being obscured by automatic lifting. This basically takes a type error reported at compile time, which, in the case where it would have been solved by lifting, is easily resolved by simply adding a line to a do-block or by using liftM, and turns it into a potential behavioural error which may only be detected at runtime, and whose source in the code may not be so obvious (since the lifting was unintentional in the first place). Also, a class instance, say of Num for lists (treating them as polynomials/power series) would suddenly turn one valid piece of code, like [1,2,3] + [4,5,6] defined by automatic lifting, into a completely different one, and suddenly silently introduce bugs into previously written code in the module (perhaps written by another author who had intended to use the automatic lifting). I think that's reason enough to make people say what they mean in each case. Automatic lifting is performed in mathematics because it is assumed that the reader is an intelligent human who will be able to infer quite reasonably what is meant in each (often somewhat ambiguous) case. Haskell programs are not written only for humans, but also for the Haskell compiler, which can't be expected to (and quite possibly shouldn't try to) judge the intent of a piece of code. - Cale On 09/09/05, Frederik Eaton <frederik@a5.repetae.net> wrote:
By the way, I thought it would be obvious, but a lot of people seem to be missing the fact that I'm not (as Sean, I believe, isn't) requesting limited support for 1 or 2 or 3 argument functions or certain type classes to be applied to monads, or for certain operations to defined on certain types. I know at least how to define type classes and functions. If this is what I wanted I would probably do it myself.
I thought the easy answer would be to inject non-monadic values into the monad (assuming one already rejiggered things to do automatic lifting).
I don't know if this is the right way of looking at it. Do you have an example?
My idea is that you should be able to have code like this:
-- (a)
m3 :: a -> m b
m6 = do m1 m2 m3 (p1 (p2 p3 (p4 m4 p5)) p6) m5
- where the m* values are functions returning monads and the p* values are so-called "pure" functions, i.e. functions which don't take monad values or return monad results (so currently the above code won't type-check beacuse of m4) - but have it be interpreted as:
-- (b)
m3 :: a -> m b
m6 = do m1 m2 v <- m4 m3 (p1 (p2 p3 (p4 v p5) p6) m5
Note that in (a), "pure" values are never used where monads are asked for, only the other way around.
I think that supporting syntax (a) for semantics (b) should be a feature because: (1) it is (usually) obvious what (a) means; (2) it eliminates the single-use variable 'v' - single-use variables like this occur a lot in monadic Haskell code, and I think they make it harder to read and write; (3) it would support the math-like syntax that I presented in my original message.
It might be hard to modify the type checker to get it to work, but I think it is possible, and I see no reason not to be as general as possible.
Would it mean treating the 'Monad' class specially? Perhaps, but I don't think this is a reason to avoid it. Further, it is likely that whatever is done to extend the type checker could be given a general interface, which Monad would simply take advantage of, using a meta-declaration in the same spirit as "infixr" etc.
Also, I do not think that template haskell is powerful enough to support this, but I'm willing to be proven wrong.
Frederik
-- http://ofb.net/~frederik/ _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
These are good arguments, and I think this is a good direction for the discussion, should it continue.
Despite having a fairly mathematical background, I don't really care for the proposed syntax.
myList :: [[Integer]] myList = return [1,2,3,4]
I'm assuming you mean myList :: [[Integer]] myList = [1,2,3,4]
Is myList equal to [[1,2,3,4]] or [[1],[2],[3],[4]]? Either interpretation is possible if there is automatic lifting about. If the lifting only occurs when a type error would otherwise have happened, then there will be cases where genuine type errors are happening and being obscured by automatic lifting.
Perhaps. The question is whether enough type errors will be left over to keep type checking useful. I'm willing to explore the possibility that there are. This is not the same as an all-purpose, C++-style "cast" operator. It only applies to Monads, and it never makes them disappear, it only introduces and propagates them. The effect on the type system is thus circumscribed. You can only introduce a Monad in "monadic context". I think there may be better examples than the one you gave. To me it it seems intuitive that myList should be [[1,2,3,4]]. It also seems intuitive that this can be turned into a general rule, although I'm not accustomed to this sort of reasoning. By the way, I'm not entirely confident in the definition of "monadic context" that I gave in a message dated "Wed, 7 Sep 2005 23:41:41 -0700".
This basically takes a type error reported at compile time, which, in the case where it would have been solved by lifting, is easily resolved by simply adding a line to a do-block or by using liftM, and turns it into a potential behavioural error which may only be detected at runtime, and whose source in the code may not be so obvious (since the lifting was unintentional in the first place).
This is true, if you see the two values as essentialy different. But if you intended to write [[1,2],[3,4]], and you're complaining that the type system would no longer save you from omitting the outer and middle brackets by accident, then I would say: but even now it doesn't save you from omitting just the middle brackets by accident. You still have to watch what you type. And I would say, furthermore, that many of the errors that the type system currently catches are a result of programs being too far from their specifications, in the present syntax, and that if my proposal succeeds in bringing them closer, then it isn't clear that there won't be a net decrease in errors as a result. Many of the technologies which Haskell researchers are inventing to make programming easier already have this effect - of making errors harder to detect, but compensating by making programs more concise. Strong typing is a great language feature, but it isn't the only one.
Also, a class instance, say of Num for lists (treating them as polynomials/power series) would suddenly turn one valid piece of code, like [1,2,3] + [4,5,6] defined by automatic lifting, into a completely different one, and suddenly silently introduce bugs into previously written code in the module (perhaps written by another author who had intended to use the automatic lifting).
Again, I'm trying to imagine a better example. In this case, personally: even if I weren't forced to, and even if it just wrapped a list, I would create my own polynomial datatype with 'newtype'. Just for the sake of clarity. So it would not be a problem. Am I being obtuse?
... Automatic lifting is performed in mathematics because it is assumed that the reader is an intelligent human who will be able to infer quite reasonably what is meant in each (often somewhat ambiguous) case. Haskell programs are not written only for humans, but also for the Haskell compiler, which can't be expected to (and quite possibly shouldn't try to) judge the intent of a piece of code.
This is a most persuasive observation. And it is often true that these authors we invoke for mathematicians will explicitly "declare" what they mean before adding functions or sets, as I am being asked to do. However, they'll also define explicitly what a homomorphism is, over and over again, separately; for groups, rings, fields, etc. But the fact is that we don't really use separate concepts for homomorphisms on different categories, when we think about them. And if we look closely we can even discover a simple and unambiguous rule uniting them, and we can apply this rule to programming language design. The fact that the general rule was also given to us in the form of different specialized versions, by mathematicians, let alone by programmers, doesn't mean that we shouldn't try to do better. I think the same is true for a large class of mathematical shorthand (and I think that the importance of notation is underrated). I think most such shorthand can be understood simply in terms of lifting, and I hypothesize that we can find an automatic lifting rule along the lines I've described which will not be as ambiguous as you suggest. Frederik
On 09/09/05, Frederik Eaton <frederik@a5.repetae.net> wrote:
By the way, I thought it would be obvious, but a lot of people seem to be missing the fact that I'm not (as Sean, I believe, isn't) requesting limited support for 1 or 2 or 3 argument functions or certain type classes to be applied to monads, or for certain operations to defined on certain types. I know at least how to define type classes and functions. If this is what I wanted I would probably do it myself.
I thought the easy answer would be to inject non-monadic values into the monad (assuming one already rejiggered things to do automatic lifting).
I don't know if this is the right way of looking at it. Do you have an example?
My idea is that you should be able to have code like this:
-- (a)
m3 :: a -> m b
m6 = do m1 m2 m3 (p1 (p2 p3 (p4 m4 p5)) p6) m5
- where the m* values are functions returning monads and the p* values are so-called "pure" functions, i.e. functions which don't take monad values or return monad results (so currently the above code won't type-check beacuse of m4) - but have it be interpreted as:
-- (b)
m3 :: a -> m b
m6 = do m1 m2 v <- m4 m3 (p1 (p2 p3 (p4 v p5) p6) m5
Note that in (a), "pure" values are never used where monads are asked for, only the other way around.
I think that supporting syntax (a) for semantics (b) should be a feature because: (1) it is (usually) obvious what (a) means; (2) it eliminates the single-use variable 'v' - single-use variables like this occur a lot in monadic Haskell code, and I think they make it harder to read and write; (3) it would support the math-like syntax that I presented in my original message.
It might be hard to modify the type checker to get it to work, but I think it is possible, and I see no reason not to be as general as possible.
Would it mean treating the 'Monad' class specially? Perhaps, but I don't think this is a reason to avoid it. Further, it is likely that whatever is done to extend the type checker could be given a general interface, which Monad would simply take advantage of, using a meta-declaration in the same spirit as "infixr" etc.
Also, I do not think that template haskell is powerful enough to support this, but I'm willing to be proven wrong.
Frederik
-- http://ofb.net/~frederik/ _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
On 10/09/05, Frederik Eaton <frederik@a5.repetae.net> wrote:
These are good arguments, and I think this is a good direction for the discussion, should it continue.
Despite having a fairly mathematical background, I don't really care for the proposed syntax.
myList :: [[Integer]] myList = return [1,2,3,4]
I'm assuming you mean
myList :: [[Integer]] myList = [1,2,3,4]
No, the confusion is over whether to lift the return, because the inner and outer monads are the same. It's either return [1,2,3,4] == [[1,2,3,4]], or it's liftM return [1,2,3,4] == [[1],[2],[3],[4]]
Is myList equal to [[1,2,3,4]] or [[1],[2],[3],[4]]? Either interpretation is possible if there is automatic lifting about. If the lifting only occurs when a type error would otherwise have happened, then there will be cases where genuine type errors are happening and being obscured by automatic lifting.
Perhaps. The question is whether enough type errors will be left over to keep type checking useful. I'm willing to explore the possibility that there are. This is not the same as an all-purpose, C++-style "cast" operator. It only applies to Monads, and it never makes them disappear, it only introduces and propagates them. The effect on the type system is thus circumscribed. You can only introduce a Monad in "monadic context".
I think there may be better examples than the one you gave. To me it it seems intuitive that myList should be [[1,2,3,4]]. It also seems intuitive that this can be turned into a general rule, although I'm not accustomed to this sort of reasoning.
By the way, I'm not entirely confident in the definition of "monadic context" that I gave in a message dated "Wed, 7 Sep 2005 23:41:41 -0700".
This basically takes a type error reported at compile time, which, in the case where it would have been solved by lifting, is easily resolved by simply adding a line to a do-block or by using liftM, and turns it into a potential behavioural error which may only be detected at runtime, and whose source in the code may not be so obvious (since the lifting was unintentional in the first place).
This is true, if you see the two values as essentialy different.
But if you intended to write [[1,2],[3,4]], and you're complaining that the type system would no longer save you from omitting the outer and middle brackets by accident, then I would say: but even now it doesn't save you from omitting just the middle brackets by accident. You still have to watch what you type.
Well, the concern isn't so much for explicit lists as such (as errors there are quite visible), but when the lists involved are abstract anyway, perhaps hidden in some chain of compositions.
And I would say, furthermore, that many of the errors that the type system currently catches are a result of programs being too far from their specifications, in the present syntax, and that if my proposal succeeds in bringing them closer, then it isn't clear that there won't be a net decrease in errors as a result. Many of the technologies which Haskell researchers are inventing to make programming easier already have this effect - of making errors harder to detect, but compensating by making programs more concise. Strong typing is a great language feature, but it isn't the only one.
Also, a class instance, say of Num for lists (treating them as polynomials/power series) would suddenly turn one valid piece of code, like [1,2,3] + [4,5,6] defined by automatic lifting, into a completely different one, and suddenly silently introduce bugs into previously written code in the module (perhaps written by another author who had intended to use the automatic lifting).
Again, I'm trying to imagine a better example. In this case, personally: even if I weren't forced to, and even if it just wrapped a list, I would create my own polynomial datatype with 'newtype'. Just for the sake of clarity. So it would not be a problem. Am I being obtuse?
Well, that's true, but many types are instances of Monad and instances of another class, and often not in a way which is compatible with your form of lifting. That's the generic version of the point which I'd hoped would be extracted from the example.
... Automatic lifting is performed in mathematics because it is assumed that the reader is an intelligent human who will be able to infer quite reasonably what is meant in each (often somewhat ambiguous) case. Haskell programs are not written only for humans, but also for the Haskell compiler, which can't be expected to (and quite possibly shouldn't try to) judge the intent of a piece of code.
This is a most persuasive observation.
And it is often true that these authors we invoke for mathematicians will explicitly "declare" what they mean before adding functions or sets, as I am being asked to do. However, they'll also define explicitly what a homomorphism is, over and over again, separately; for groups, rings, fields, etc.
But the fact is that we don't really use separate concepts for homomorphisms on different categories, when we think about them. And if we look closely we can even discover a simple and unambiguous rule uniting them, and we can apply this rule to programming language design. The fact that the general rule was also given to us in the form of different specialized versions, by mathematicians, let alone by programmers, doesn't mean that we shouldn't try to do better.
I think the same is true for a large class of mathematical shorthand (and I think that the importance of notation is underrated). I think most such shorthand can be understood simply in terms of lifting, and I hypothesize that we can find an automatic lifting rule along the lines I've described which will not be as ambiguous as you suggest.
Why not look for a way to do the lifting which is explicit, yet not inconvenient? Monads often do a great job of this on their own. One can already write code with a fair amount of convenience which works across monads and which determines its effects based on its inputs. It may be possible to use template haskell to derive an automatic monad lifter which could be applied in a controlled fashion, and if people really like it, it could be given some special syntax perhaps. Another point which is perhaps important to mention is that the monadification of some code is not really something which is unique. The right level of abstraction is sometimes not to just apply liftMn to everything, but to use something stronger, like MonadPlus, and to be careful about how everything happens. This can come up when producing a nondeterministic abstraction of an initially deterministic algorithm. Full nondeterminism without any optimisation is often not what you want. You might want to work with a subset of the combinations of the inputs that may not at first be obvious, and there are various optimisations which may be necessary to curb combinatorial explosion (even though laziness often does help a lot here). To do this sort of optimisation, you need an instance of MonadPlus (or at least MonadZero, but that's not around anymore). Also, if the whole thing is autolifted, you can't inject these controls into the middle, and end up lifting the code by hand anyway. Careful application of the generic lifting could be very useful, but unrestrained, in many cases could completely fail to be helpful. Also, with multiparameter functions, liftMn isn't always the right thing to apply. Maybe some parameters should be lifted to one monad and others to another, and the results collected in a suitable combination. This sort of thing is hard to do automatically, and it can be difficult to tell. What we probably want is an explicit, but generic, lifting mechanism, which takes care of the boilerplate parts of the lifting, but which we can control with some precision. Doing it automatically everywhere seems like it could often be inconvenient. - Cale
On Sun, Sep 11, 2005 at 01:48:16AM -0400, Cale Gibbard wrote:
On 10/09/05, Frederik Eaton <frederik@a5.repetae.net> wrote:
These are good arguments, and I think this is a good direction for the discussion, should it continue.
Despite having a fairly mathematical background, I don't really care for the proposed syntax.
myList :: [[Integer]] myList = return [1,2,3,4]
I'm assuming you mean
myList :: [[Integer]] myList = [1,2,3,4]
No, the confusion is over whether to lift the return, because the inner and outer monads are the same. It's either return [1,2,3,4] == [[1,2,3,4]], or it's liftM return [1,2,3,4] == [[1],[2],[3],[4]]
I think that Frederik's example is even better. Here you either lift the entire list or each individual number: return [1,2,3,4] or [return 1,return 2,return 3,return 4] After all, return is only a fancy name for liftM0 ;-) Best regards Tomasz
I heartily agree with everything Cale wrote on this topic. In addition, I hereby apologize to Claus for being too lazy to participate in the survey. Regards, Yitz Cale Gibbard wrote:
Despite having a fairly mathematical background, I don't really care for the proposed syntax.
myList :: [[Integer]] myList = return [1,2,3,4]
Is myList equal to [[1,2,3,4]] or [[1],[2],[3],[4]]? Either interpretation is possible if there is automatic lifting about. If the lifting only occurs when a type error would otherwise have happened, then there will be cases where genuine type errors are happening and being obscured by automatic lifting.
This basically takes a type error reported at compile time, which, in the case where it would have been solved by lifting, is easily resolved by simply adding a line to a do-block or by using liftM, and turns it into a potential behavioural error which may only be detected at runtime, and whose source in the code may not be so obvious (since the lifting was unintentional in the first place).
Also, a class instance, say of Num for lists (treating them as polynomials/power series) would suddenly turn one valid piece of code, like [1,2,3] + [4,5,6] defined by automatic lifting, into a completely different one, and suddenly silently introduce bugs into previously written code in the module (perhaps written by another author who had intended to use the automatic lifting).
I think that's reason enough to make people say what they mean in each case. Automatic lifting is performed in mathematics because it is assumed that the reader is an intelligent human who will be able to infer quite reasonably what is meant in each (often somewhat ambiguous) case. Haskell programs are not written only for humans, but also for the Haskell compiler, which can't be expected to (and quite possibly shouldn't try to) judge the intent of a piece of code.
- Cale
On 09/09/05, Frederik Eaton <frederik@a5.repetae.net> wrote:
By the way, I thought it would be obvious, but a lot of people seem to be missing the fact that I'm not (as Sean, I believe, isn't) requesting limited support for 1 or 2 or 3 argument functions or certain type classes to be applied to monads, or for certain operations to defined on certain types. I know at least how to define type classes and functions. If this is what I wanted I would probably do it myself.
I thought the easy answer would be to inject non-monadic values into the monad (assuming one already rejiggered things to do automatic lifting).
I don't know if this is the right way of looking at it. Do you have an example?
My idea is that you should be able to have code like this:
-- (a)
m3 :: a -> m b
m6 = do m1 m2 m3 (p1 (p2 p3 (p4 m4 p5)) p6) m5
- where the m* values are functions returning monads and the p* values are so-called "pure" functions, i.e. functions which don't take monad values or return monad results (so currently the above code won't type-check beacuse of m4) - but have it be interpreted as:
-- (b)
m3 :: a -> m b
m6 = do m1 m2 v <- m4 m3 (p1 (p2 p3 (p4 v p5) p6) m5
Note that in (a), "pure" values are never used where monads are asked for, only the other way around.
I think that supporting syntax (a) for semantics (b) should be a feature because: (1) it is (usually) obvious what (a) means; (2) it eliminates the single-use variable 'v' - single-use variables like this occur a lot in monadic Haskell code, and I think they make it harder to read and write; (3) it would support the math-like syntax that I presented in my original message.
It might be hard to modify the type checker to get it to work, but I think it is possible, and I see no reason not to be as general as possible.
Would it mean treating the 'Monad' class specially? Perhaps, but I don't think this is a reason to avoid it. Further, it is likely that whatever is done to extend the type checker could be given a general interface, which Monad would simply take advantage of, using a meta-declaration in the same spirit as "infixr" etc.
Also, I do not think that template haskell is powerful enough to support this, but I'm willing to be proven wrong.
Frederik
-- http://ofb.net/~frederik/ _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
life is funny, isn't it? so many people so eagerly discussing conversion between non-monadic and monadic code, yet when we asked for your opinions and suggestions on this very topic only a short while ago, we got a total of 4 (four) replies - all quite useful, mind you, so we were grateful, but still one wonders.. we might have assumed that not many people cared after all: http://www.haskell.org//pipermail/haskell/2005-March/015557.html shall I assume that all participants in this discussion have joined the Haskell parade since then, and have proceeded rapidly to the problems of monadic lifting?-) in which case I'd invite you to have a look at that survey and the papers mentioned.
I thought the easy answer would be to inject non-monadic values into the monad (assuming one already rejiggered things to do automatic lifting).
I'd phrase it slightly differently: what (I think) one wants are implicit coercions between monadic and non-monadic types of expressions, where the coercions lift non-monadic values into the monad in question, while embedding monadic computations in the current monad to get a non-monadic result if only that is needed (although one might think of the latter as partially lifting the operation that needs the non-monadic result). only I wouldn't want those implicit coercions to be introduced unless programmers explicitly ask for that (one usually only converts code from non-monadic to monadic once, and while the details of that step might be tiresome and in need of tool-support, the step itself should be explicit - see my comment on (2) below).
Note that in (a), "pure" values are never used where monads are asked for, only the other way around.
that is probably where some would beg to differ - if you lift operations, why not lift values as well?
I think that supporting syntax (a) for semantics (b) should be a feature because: (1) it is (usually) obvious what (a) means; (2) it eliminates the single-use variable 'v' - single-use variables like this occur a lot in monadic Haskell code, and I think they make it harder to read and write; (3) it would support the math-like syntax that I presented in my original message.
(1) "(usually) obvious" is tech-speak for "(perhaps) possible to figure out, though probably not uniquely determined"?-) when mathematicians abuse notation in the "obvious" way, there is usually an assumed context in which the intended abuses are clearly defined (if not, there is another context in which the "obvious" things will go unexpectedly awry). (2) the nice thing about Haskell is that it *distinguishes* between monadic and non-monadic computations, and between evaluation and execution of monadic computations. if you want everything mixed into one soup, ML might be your language of choice (http://portal.acm.org/citation.cfm?id=178047 , if I recall correctly? see the paper discussed in http://lambda-the-ultimate.org/node/view/552 for one application that demonstrates the power/danger of such implicit monads). (3) using math-like syntax for lifted expressions is common practice in some families of Haskell-DSELs, eg. Conal Elliot's Fran. As John pointed out, the predefined class-hierarchy is not really helpful for such endeavours, but if one isn't picky, one may ignore classes not used.. the "trick" is to lift even constants, so when you get to applications, all components are already lifted, and lifting most arithmetic works out fine (Boolean operations are another matter). note, however, that the resulting language, while looking mathematically pure and permitting concise expression of complex circumstances, may not have the reasoning properties you expect..
It might be hard to modify the type checker to get it to work, but I think it is possible, and I see no reason not to be as general as possible.
here I'd agree, although in contrast to you, I'd be talking about a complex refactoring under programmer control, not about an implicitly invoked collection of coercions. I played with that idea after Martin Erwig visited our refactoring project in March, and got to a prototype type-coercion inference system for a very simple functional language, because I found the situation with various existing and, as Erwig/Ren pointed out, apparently unrelated monadification algorithms confusing. apart from the various styles of monadification, which we'd like to permit, and have the programmer select, e.g., by type annotations, there is the slight problem that there are an unbounded number of different monadifications (more if one wants to keep annotations to a minimum), so one needs a sensible bound (one that does not exclude any of the alternatives one might want). one also might want to be able to choose between the alternatives (or tune the system so that taking the first choice works out ok most of the time). oh, and it shouldn't be too inefficient, and it is really a pain to re-implement a type-system just to add a few coercion rules to it (which is why I haven't extended my mini fpl to Haskell yet..). in light of this, perhaps some more participants in this discussion might want to look into contributing their suggestions to our old survey? cheers, claus
On Sat, Sep 10, 2005 at 12:55:15AM +0100, Claus Reinke wrote:
life is funny, isn't it? so many people so eagerly
lazily, in my case
discussing conversion between non-monadic and monadic code,
I'm trying to discuss a new syntax, not code transformations. I agree that the two are related. I'm interested in the latter, but I don't understand it very well. I think of refactoring as an operation that takes source code to source code, i.e. unlike most operations done on source code, refactoring produces output which is meant to be edited by humans. Is this correct? But if it is, doesn't it mean that one would like refactorizations to have some ill-defined "reversibility" property: a refactorization should have an inverse which commutes with simple edits For instance, if I (a) rename a variable, and then (b) introduce a new reference to the renamed variable somewhere, I can later decide to change the name back, reverting (a), without losing the work I did in the meantime in (b). I can do this by applying another rename operation, which will also affect the new reference. Or, if I (a) take a bit of code and remove it to a separate function, and then (b) modify the body of that function, I can later decide to inline the function back into the one place which calls it, thus reverting (a), without losing the modification done in (b). Yet, I don't see how the "monadification" operations you propose could have this property. They are certainly code transformations! But they seem irreversible - once I (a) apply your transformations and (b) edit the output, I can't revert (a) without losing the work done in (b). Changes to the code become tightly coupled, design becomes less tractable.
yet when we asked for your opinions and suggestions on this very topic only a short while ago, we got a total of 4 (four) replies - all quite useful, mind you, so we were grateful, but still one wonders.. we might have assumed that not many people cared after all:
http://www.haskell.org//pipermail/haskell/2005-March/015557.html
It might have been more useful to ask for survey replies to be sent to the list. Often the various opinions of a large number of people can be compressed to a few representative positions. But if respondents can't see what opinions have been expressed so far, then this time-saving compression becomes impossible. That is just my opinion.
shall I assume that all participants in this discussion have joined the Haskell parade since then, and have proceeded rapidly to the problems of monadic lifting?-) in which case I'd invite you to have a look at that survey and the papers mentioned.
I should do that, yes! It's just that I was a bit late, having misplaced my trumpet.
I thought the easy answer would be to inject non-monadic values into the monad (assuming one already rejiggered things to do automatic lifting).
I'd phrase it slightly differently: what (I think) one wants are implicit coercions between monadic and non-monadic types of expressions, where the coercions lift non-monadic values into the monad in question, while embedding monadic computations in the current monad to get a non-monadic result if only that is needed (although one might think of the latter as partially lifting the operation that needs the non-monadic result).
only I wouldn't want those implicit coercions to be introduced unless programmers explicitly ask for that (one usually only converts code from non-monadic to monadic once, and while the details of that step might be tiresome and in need of tool-support, the step itself should be explicit - see my comment on (2) below).
Note that in (a), "pure" values are never used where monads are asked for, only the other way around.
that is probably where some would beg to differ - if you lift operations, why not lift values as well?
Oh, one should do both, I was just giving a case where value-lifting didn't happen, as a counterexample to Aaron's viewpoint.
I think that supporting syntax (a) for semantics (b) should be a feature because: (1) it is (usually) obvious what (a) means; (2) it eliminates the single-use variable 'v' - single-use variables like this occur a lot in monadic Haskell code, and I think they make it harder to read and write; (3) it would support the math-like syntax that I presented in my original message.
(1) "(usually) obvious" is tech-speak for "(perhaps) possible to figure out, though probably not uniquely determined"?-)
when mathematicians abuse notation in the "obvious" way, there is usually an assumed context in which the intended abuses are clearly defined (if not, there is another context in which the "obvious" things will go unexpectedly awry).
(2) the nice thing about Haskell is that it *distinguishes* between monadic and non-monadic computations, and between evaluation and execution of monadic computations. if you want everything mixed into one soup, ML might be your language of choice (http://portal.acm.org/citation.cfm?id=178047 , if I recall correctly? see the paper discussed in http://lambda-the-ultimate.org/node/view/552 for one application that demonstrates the power/danger of such implicit monads).
(3) using math-like syntax for lifted expressions is common practice in some families of Haskell-DSELs, eg. Conal Elliot's Fran. As John pointed out, the predefined class-hierarchy is not really helpful for such endeavours, but if one isn't picky, one may ignore classes not used.. the "trick" is to lift even constants, so when you get to applications, all components are already lifted, and lifting most arithmetic works out fine (Boolean operations are another matter).
note, however, that the resulting language, while looking mathematically pure and permitting concise expression of complex circumstances, may not have the reasoning properties you expect..
At this point I think we have to look at more examples. I'm not convinced that my position is right, but I'm not convinced that that it is wrong either. I just think it's promising, based on my experience. If I were a better person, and had more free time, I would work on producing examples and working things out myself, and perhaps write a paper or something. Of course, experienced people are disagreeing with me, so maybe I should just accept their good judgment! In any case, I'm afraid I don't have much more to contribute, beyond the idea itself.
It might be hard to modify the type checker to get it to work, but I think it is possible, and I see no reason not to be as general as possible.
here I'd agree, although in contrast to you, I'd be talking about a complex refactoring under programmer control, not about an implicitly invoked collection of coercions. I played with that idea after Martin Erwig visited our refactoring project in March, and got to a prototype type-coercion inference system for a very simple functional language, because I found the situation with various existing and, as Erwig/Ren pointed out, apparently unrelated monadification algorithms confusing.
apart from the various styles of monadification, which we'd like to permit, and have the programmer select, e.g., by type annotations, there is the slight problem that there are an unbounded number of different monadifications (more if one wants to keep annotations to a minimum), so one needs a sensible bound (one that does not exclude any of the alternatives one might want). one also might want to be able to choose between the alternatives (or tune the system so that taking the first choice works out ok most of the time). oh, and it shouldn't be too inefficient, and it is really a pain to re-implement a type-system just to add a few coercion rules to it (which is why I haven't extended my mini fpl to Haskell yet..).
Well, I've said a little about why I don't like irreversible refactoring. I've been reading "Notes on the Synthesis of Form" by Christopher Alexander, I think this has helped me understand the process of design in more abstract terms, if you want a reference. I think the source code of a program should be as close to its initial specification as possible. The goal should be to make it as easy to read and modify as it was to write. However, if the design is spread out over write/test/debug cycles, as is often the case in interpreted languages such as perl; or refactor cycles, as you seem to be proposing; then a lot of the decisions and rationales which determine that design will not be visible in the final version of the code - rather, they will be stored in the succession of modifications which have been applied to create this final version. But these modifications are, as it were, difficult to go back and modify. The more a program is produced through a process of accretion or evolution, the more tightly coupled various aspects of its design will be, and the more difficult it will be to change any one of them. Even if most of the design decisions are good ones, eventually the number of unfixable bad decisions will grow until continued development of a particular component becomes untenable. This might happen at a function level or a module level or a program level - but in any case I think the development style in question should be avoided where possible, and made avoidable where feasible. Frederik
On 2005-09-09, Frederik Eaton <frederik@a5.repetae.net> wrote:
I thought the easy answer would be to inject non-monadic values into the monad (assuming one already rejiggered things to do automatic lifting).
I don't know if this is the right way of looking at it. Do you have an example?
In a do block, 1 + [2,3,4] would get turned into liftM2 (+) (return 1) [2, 3, 4] (I actually think this whole thing is a horrible idea, much for the reasons Cale Gibbard puts forward.)
Would it mean treating the 'Monad' class specially? Perhaps, but I don't think this is a reason to avoid it. Further, it is likely that whatever is done to extend the type checker could be given a general interface, which Monad would simply take advantage of, using a meta-declaration in the same spirit as "infixr" etc.
Well, monads are already treated specially -- the whole do syntax. -- Aaron Denney -><-
Am Samstag, 10. September 2005 05:12 schrieb Aaron Denney:
[...]
Well, monads are already treated specially -- the whole do syntax.
But the do syntax isn't a very drastic special treatment of monads. There is a relatively simple syntax-based transformation into code without do expressions. Best wishes, Wolfgang
Am Freitag, 9. September 2005 23:56 schrieb Frederik Eaton:
[...]
Would it mean treating the 'Monad' class specially? Perhaps, but I don't think this is a reason to avoid it.
As far as I can see, your approach would make Haskell a kind of imperative programming language. Side-effects would be hidden in expressions which is a thing I want to see strictly avoided.
[...]
Also, I do not think that template haskell is powerful enough to support this, but I'm willing to be proven wrong.
I suppose that Template Haskell is powerful enough to automatically declare instances of classes like Num for monadic types, based on instances for non-monadic types.
Frederik
Best wishes, Wolfgang
participants (12)
-
Aaron Denney -
Cale Gibbard -
Claus Reinke -
Frederik Eaton -
J. Garrett Morris -
John Meacham -
Keean Schupke -
Malcolm Wallace -
Scherrer, Chad -
Tomasz Zielonka -
Wolfgang Jeltsch -
Yitzchak Gale