Hi,
The Monad class makes us define bind (>>=) and unit (return) for our monads. Why the Kleisli composition (>=>) or (<=<) is not made a part of Monad class instead of bind (>>=)? Is there any historical reason behind this? The bind (>>=) is not as elegant as (>=>), at least as I find it. Am I missing something?  Damodar _______________________________________________ HaskellCafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskellcafe 
damodar kulkarni <[hidden email]> wrote:
> The Monad class makes us define bind (>>=) and unit (return) for our > monads. > > Why the Kleisli composition (>=>) or (<=<) is not made a part of Monad > class instead of bind (>>=)? > > Is there any historical reason behind this? > > The bind (>>=) is not as elegant as (>=>), at least as I find it. > > Am I missing something? do x < getLine y < getLine print (x, y) using only Kleisli composition (without cheating). Through cheating (doing noncategorical stuff) it's possible to implement (>>=) in terms of (<=<), but as said that's basically breaking the abstraction. Greets, Ertugrul  Not to be or to be and (not to be or to be and (not to be or to be and (not to be or to be and ... that is the list monad. _______________________________________________ HaskellCafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskellcafe signature.asc (853 bytes) Download Attachment 
Ertugrul Söylemez wrote:
> damodar kulkarni <[hidden email]> wrote: >> The Monad class makes us define bind (>>=) and unit (return) for our >> monads. >> >> Why the Kleisli composition (>=>) or (<=<) is not made a part of Monad >> class instead of bind (>>=)? >> >> Is there any historical reason behind this? >> >> The bind (>>=) is not as elegant as (>=>), at least as I find it. >> >> Am I missing something? > > Try to express > > do x < getLine > y < getLine > print (x, y) > > using only Kleisli composition (without cheating). Through cheating > (doing noncategorical stuff) it's possible to implement (>>=) in terms > of (<=<), but as said that's basically breaking the abstraction. What do you mean with "cheating" / "doing noncategorical stuff"? m >>= f = (const m >=> f) () f >=> g = \x > f x >>= g How does the first definition "break the abstraction" while the second does not? Cheers  Ben Franksen () ascii ribbon campaign  against html email /\ www.asciiribbon.org  against proprietary attachments _______________________________________________ HaskellCafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskellcafe 
Le Mon, 15 Oct 2012 15:12:28 +0200,
Benjamin Franksen <[hidden email]> a écrit : > Ertugrul Söylemez wrote: > > damodar kulkarni <[hidden email]> wrote: > >> The Monad class makes us define bind (>>=) and unit (return) for > >> our monads. > >> > >> Why the Kleisli composition (>=>) or (<=<) is not made a part of > >> Monad class instead of bind (>>=)? > >> > >> Is there any historical reason behind this? > >> > >> The bind (>>=) is not as elegant as (>=>), at least as I find it. > >> > >> Am I missing something? > > > > Try to express > > > > do x < getLine > > y < getLine > > print (x, y) > > > > using only Kleisli composition (without cheating). Through cheating > > (doing noncategorical stuff) it's possible to implement (>>=) in > > terms of (<=<), but as said that's basically breaking the > > abstraction. > > What do you mean with "cheating" / "doing noncategorical stuff"? > > m >>= f = (const m >=> f) () > > f >=> g = \x > f x >>= g > > How does the first definition "break the abstraction" while the > second does not? > > Cheers It does not really break the categorical stuff, but I think that bind has better its place rather than being replaced by the Kleisli arrow. I am quite new to Haskell, so I do not know its history, but for the categorical point of view, bind would better have received the signature "∀ α β, (α→Mβ) → (Mα→Mβ)", expressing 'M' as a functor from Kleisli(M) category to the Hask category, sending each morphism "α→Mβ" from "α" to "β" in Kleisli category, to a morphism "Mα→Mβ" in the Hask category. As you may have already read, the usual point of view of monads in mathematic is not with (return, bind) but (return, join) [return is usually noted ε and is called the unit, and join is usually noted μ and called multiplication]. In this context, "return : ∀ α, (α→Mα)" and "join : ∀ α, (MMα→Mα)" are called natural transformations and must respect some additionnal rules (called monad laws). If you do not know what a natural transformation is, this is some definition (in a Haskell context). Consider two functors S and T, "f: ∀ α, (Sα→Tα)" is a natural transformation from S to T, if for any types "t1" and "t2" and any pure function "g: t1→t2", we following egality holds: "f.(fmap g)=(fmap g).f" For instance when S is the identity functor, and T is the functor associated to the monad, you must have "return.(fmap g) = (fmap g).return". Now, I do not really know why "bind" is used rather than "join". I guess that join is not very common in practice, so we would have to write "join (fmap f) x" each time we would like to write "bind x f". Another reason may be history, and the last one would be efficiency (I guess that "bind" correspond better to machine models than "join"). In any case, "join" has a simpler type than "bind" (only one type variable), which in turn is simpler than your Kleisli arrow (you need 3 type variables). It would be rather awful to expand each of your Kleisli arrows with "const" as you said. Of course you wouldn't have to do it, but for efficient compilation, as I guess that in most cases "bind" can be rather efficiently implemented, while "kleisli" would not, I fear some minor performance issues with "bind" defined in terms of "kleisli". Once again I am not a Haskell expert. For the small story, the concept of Monad is strongly linked to the one of Adjunction (although adjunctions in Haskell are probably not very commonly used and easy to define). The composition of a left and a right adjunction gives a Monad, and given a Monad, we can build an adjunction. One of the adjunction you can build is using … the Kleisli category (see Wikipedia). _______________________________________________ HaskellCafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskellcafe 
In reply to this post by Ertugrul Söylemez
On Mon, Oct 15, 2012 at 7:59 AM, Ertugrul Söylemez <[hidden email]> wrote:
> Try to express > > do x < getLine > y < getLine > print (x, y) > > using only Kleisli composition (without cheating). In my opinion, this is not as nice as the donotation version, but at least it's compositional: print <=< (<$> getLine) . (,) <=< const getLine $ () I do think there is value in favoring Kleisli composition for a lot of code. Unfortunately, however, it doesn't tend to work out so nicely for IO.  Jake _______________________________________________ HaskellCafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskellcafe 
On Mon, Oct 15, 2012 at 11:33 AM, Jake McArthur <[hidden email]> wrote:
> On Mon, Oct 15, 2012 at 7:59 AM, Ertugrul Söylemez <[hidden email]> wrote: >> Try to express >> >> do x < getLine >> y < getLine >> print (x, y) >> >> using only Kleisli composition (without cheating). My previous answer didn't do the Kleisli style much justice. It could look a bit nicer with more Arrowstyle combinators: f &=& g = runKleisli $ Kleisli f &&& Kleisli g print <=< const getLine &=& const getLine $ () _______________________________________________ HaskellCafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskellcafe 
@Jake
In my opinion, this is not as nice as the donotation version, but at That's an important point you have made, as Haskellers value code composition so much. If code composition is the "holy grail", why not encourage the monadic code, too, to be compositional? Nicety can wait; some syntax sugar might take care of it. And as you have pointed out, arrows make a superior choice in this regard, but they are rather newer to monads. @ AUGER Cédric It would be rather awful to expand each of your Kleisli arrows with "const" as you said. The const is required in this example because we are dealing with getLine (as getLine can return different strings at different times without taking any argument). Again, some syntactic sugar would have taken care of this "const" thing. Correct me if I am wrong. and thanks for responses. Damodar On Mon, Oct 15, 2012 at 9:09 PM, Jake McArthur <[hidden email]> wrote:
_______________________________________________ HaskellCafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskellcafe 
On Mon, Oct 15, 2012 at 10:05 PM, damodar kulkarni
<[hidden email]> wrote: > @Jake > > >> In my opinion, this is not as nice as the donotation version, but at >> least it's compositional: > > > That's an important point you have made, as Haskellers value code > composition so much. > If code composition is the "holy grail", why not encourage the monadic code, > too, to be compositional? Nicety can wait; some syntax sugar might take care > of it. > > And as you have pointed out, arrows make a superior choice in this regard, > but they are rather newer to monads. I'm uncertain where this, "compositional means written as the composition of functions," thing started. But it is not what I, and I'm sure any others mean by the term, "compositional." For instance, one of the key properties of denotational semantics is that they are compositional. But this does not mean that the semantics is written as the composition of functions. Perhaps it could be, but that is a rather superficial criterion. What it means is that the semantics of compound expressions are merely functions of the semantics of the constituent pieces, so one can stick together well understood pieces to get well understood wholes, and the whole does not have to be analyzed as an entire unit. Now, one can give almost anything a compositional semantics in this sense, by denoting things by pieces that pass context along. And this is a reason to avoid effects and whatnot. But this is true whether one writes things as a pipeline of functions or as some other sort of expression. Context may be threaded through a series of expressions, or through a series of composed functions. Choosing either way of writing makes no difference. So I don't really care whether people write their code involving monads as the composition of Kleisli arrows, except for which makes the code look nicer. And the arrow option does not always do so, especially when one must artificially extend things of type 'M a' into constant functions. Kleisli arrows aren't the end all and be all of monads (if you read books on the math end, the EilenbergMoore category tends to be emphasized far more, and the Kleisli category might not even be presented in the same way as it typically is amongst Haskellers). As for why (>>=) is a good primitive.... For one, it works very nicely for writing statement sequences without any sugar (for when you want to do that): getLine >>= \x > getLine >>= \y > print (x, y) For two, it corresponds to the nice operation of substitution of an expression for a variable (which is a large part of what monads are actually about in category theory, but doesn't get a lot of play in Haskell monad tutorials). For three, I can't for the life of me think of how anyone would write (>=>) as a primitive operation _except_ for writing (>>=) and then '(f >=> g) x = f x >>= g'. The function cannot be inspected to get the result except by applying it. I suppose one _can_ write (>=>) directly. For instance: data Free f a = Pure a  Roll (f (Free f a)) (g >=> h) x = case g x of Pure b > h b Roll f > Roll $ fmap (id >=> h) f But the (id >=> h) is there because we want to put (>>= h) and don't have it. The g is sort of an illusion. We use it to get an initial value, but all our recursive calls use g = id, so we're subsequently defining (>>=) in disguise. (And, amusingly, we're even using polymorphic recursion, so if this isn't in a class, or given an explicit type signature, inference will silently get the wrong answer.) So, there are good reasons for making (>>=) primitive, and not really any (that I can see) for making (>=>) more than a derived function. I'd be down with putting join in the class, but that tends to not be terribly important for most cases, either.  Dan _______________________________________________ HaskellCafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskellcafe 
On Mon, Oct 15, 2012 at 11:29 PM, Dan Doel <[hidden email]> wrote:
> I'm uncertain where this, "compositional means written as the > composition of functions," thing started. But it is not what I, and > I'm sure any others mean by the term, "compositional." You're right. It's a rather recent, as far as I can tell, overloading of the word that I inadvertently picked up. The meaning of this overloading, at least as I understand and intended it, is that it forms a category. I will try to avoid this use of the word in the future. > For three, I can't for the life of me think of how anyone would write > (>=>) as a primitive operation _except_ for writing (>>=) and then '(f >>=> g) x = f x >>= g'. The function cannot be inspected to get the > result except by applying it. This is a good point. > I'd be down with putting join in the class, but that tends to not be > terribly important for most cases, either. Join is not the most important, but I do think it's often easier to define than bind. I often find myself implementing bind by explicitly using join.  Jake _______________________________________________ HaskellCafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskellcafe 
In reply to this post by damodar kulkarni
Le Tue, 16 Oct 2012 07:35:34 +0530,
damodar kulkarni <[hidden email]> a écrit : > @Jake > > In my opinion, this is not as nice as the donotation version, but at > > least it's compositional: > > > That's an important point you have made, as Haskellers value code > composition so much. > If code composition is the "holy grail", why not encourage the monadic > code, too, to be compositional? Nicety can wait; some syntax sugar > might take care of it. > > And as you have pointed out, arrows make a superior choice in this > regard, but they are rather newer to monads. > > @ AUGER Cédric > > It would be rather awful to expand each of your Kleisli arrows with > > > "const" as you said. > > > > The const is required in this example because we are dealing with > getLine (as getLine can return different strings at different times > without taking any argument). Again, some syntactic sugar would have > taken care of this "const" thing. > > Correct me if I am wrong. We were not dealing with getLine in particular. The point was about knowing if >>= could be defined in terms of >=>. The const is necessary for the general case. So I think that an implicit question was why wouldn't we have: class Monad m where return :: a > m a kleisli :: (a > m b) > (b > m c) > (a > m c) bind = \ x f > ((const x) >=> f) () join = id>=>id :: (m (m a) > m a) (Sorry, I do not remember the correct Haskell syntax, I am a beginner, but I do not have touched the language for some time…) That is "bind" would have a default construction (like "join" has got its one now). The definition of "join" would become rather nice this way ^^ Not redefining the "join" and "bind" function would lead to expand them with "\ x f > (const x) >=> f" and "id>=>id", that is what I meant, and found it awful for "bind". Of course I do not say that Kleisli is a bad idea. I even think it is better to use it when you want composition, or you want to do the initial given example (readString >=> putString, or something like that, I do not really remember). But I do not think defining Monads from Kleisli (or Talgebras, for the other adjunction construction) would be very nice. On the other hand, I guess that the class Monad could contain the definition of Kleisli arrows. But as we have instances ArrowApply a => Monad (ArrowMonad a) and Monad m => Arrow (Kleisli m), I do not think we lack some functionnality. > > and thanks for responses. > > Damodar > > On Mon, Oct 15, 2012 at 9:09 PM, Jake McArthur > <[hidden email]>wrote: > > > On Mon, Oct 15, 2012 at 11:33 AM, Jake McArthur > > <[hidden email]> wrote: > > > On Mon, Oct 15, 2012 at 7:59 AM, Ertugrul Söylemez <[hidden email]> > > > wrote: > > >> Try to express > > >> > > >> do x < getLine > > >> y < getLine > > >> print (x, y) > > >> > > >> using only Kleisli composition (without cheating). > > > > My previous answer didn't do the Kleisli style much justice. It > > could look a bit nicer with more Arrowstyle combinators: > > > > f &=& g = runKleisli $ Kleisli f &&& Kleisli g > > > > print <=< const getLine &=& const getLine $ () > > > > _______________________________________________ > > HaskellCafe mailing list > > [hidden email] > > http://www.haskell.org/mailman/listinfo/haskellcafe > > _______________________________________________ HaskellCafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskellcafe 
In reply to this post by Jake McArthur
Le Tue, 16 Oct 2012 09:51:29 0400,
Jake McArthur <[hidden email]> a écrit : > On Mon, Oct 15, 2012 at 11:29 PM, Dan Doel <[hidden email]> wrote: > > I'd be down with putting join in the class, but that tends to not be > > terribly important for most cases, either. > > Join is not the most important, but I do think it's often easier to > define than bind. I often find myself implementing bind by explicitly > using join. join IS the most important from the categorical point of view. In a way it is natural to define 'bind' from 'join', but in Haskell, it is not always possible (see the Monad/Functor problem). As I said, from the mathematical point of view, join (often noted μ in category theory) is the (natural) transformation which with return (η that I may have erroneously written ε in some previous mail) defines a monad (and requires some additionnal law). As often some points it out, Haskellers are not very right in their definition of Monad, not because of the bind vs join (in fact in a Monad either of them can be defined from the other one), but because of the functor status of a Monad. A monad, should always be a functor (at least to fit its mathematical definition). And this problem with the functor has probably lead to the use of "bind" (which is polymorphic in two type variables) rather than "join" (which has only one type variable, and thus is simpler). The problem, is that when 'm' is a Haskell Monad which does not belong to the Functor class, we cannot define 'bind' in general from 'join'. That is in the context where you have: return:∀ a. a → (m a) join:∀ a. (m (m a)) → (m a) x:m a f:a → (m b) you cannot define some term of type 'm b', since you would need to use at the end, either 'f' (and you would require to produce a 'a' which would be impossible), or 'return' (and you would need to produce a 'b', which is impossible), or 'join' (and you would need to produce a 'm (m b)', and recursively for that you cannot use return which would make you go back to define a 'm b' term) For that, you need the 'fmap' operation of the functor. return:∀ a. a → (m a) join:∀ a. (m (m a)) → (m a) fmap:∀ a b. (a→b) → ((m a)→(m b)) x:m a f:a → (m b) in this context defining a term of type 'm b' is feasible (join (fmap f x)), so that you can express "bind = \ x f > join (fmap f x)". To sum up, mathematical monads are defined from 'return' and 'join' as a mathematical monad is always a functor (so 'fmap' is defined, and 'bind', which is more complex than 'join' can be defined from 'join' and 'fmap'). Haskell does not use a very good definition for their monads, as they may not be instance of the Functor class (although most of them can easily be defined as such), and without this 'fmap', 'join' and 'return' would be pretty useless, as you wouldn't be able to move from a type 'm a' to a type 'm b'. _______________________________________________ HaskellCafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskellcafe 
Although I agree that Functor should be a superclass of Monad, the two methods of the Monad typeclass _are_ sufficient to make any instance into a Functor in a mechanical/automatic way. The language may not know it, but return/bind is equivalent in power to fmap/return/join. Apart from bind being easier to use for the things we typically do with monads in programs, using bind is actually more "succinct" in that it doesn't require three primitive operations.
I'm not saying bind is a better primitive than join/fmap, but "mathematicians do it this way, therefore it's better" doesn't seem like a particularly convincing argument either. And for a more philosophical question, is something not a functor just because we don't have a Functor instance for it? If we agree that the Monad class (with no Functor superclass) does implicitly form a Functor with liftM, then I don't really see what the problem is, apart from the inconvenience of not being able to use fmap.
On Tue, Oct 16, 2012 at 10:37 AM, AUGER Cédric <[hidden email]> wrote: Le Tue, 16 Oct 2012 09:51:29 0400, _______________________________________________ HaskellCafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskellcafe 
Le Tue, 16 Oct 2012 11:22:08 0400,
Daniel Peebles <[hidden email]> a écrit : > Although I agree that Functor should be a superclass of Monad, the two > methods of the Monad typeclass _are_ sufficient to make any instance > into a Functor in a mechanical/automatic way. The language may not > know it, but return/bind is equivalent in power to fmap/return/join. > Apart from bind being easier to use for the things we typically do > with monads in programs, using bind is actually more "succinct" in > that it doesn't require three primitive operations. Succintness is not the point for me. For me, the point is primitiveness/elementaryness. For instance bind has type "m a → (a → m b) → m b" [2 type variables, one functionnal argument, one 'scalar' argument] whereas join has type "m (m a) → m a" [1 type variable, one 'scalar' argument] and fmap has type "(a → b) → (m a → m b)" [2 type variables, one functionnal argument, one 'scalar' argument] So here, 'join' is definitely more simple than 'bind'. 'fmap' and 'bind' are about same complexity (although we can consider 'fmap' slightly simpler as its functionnal argument has type 'a→b' and not 'a→m b'). Having one single powerfull function is often overkill, and you will probably require more simple functions which you will get by feeding your big function with dummy ones (such as 'id' or 'const'), and you may lose some efficiency. I do not know if you have studied the S, K, I system of combinators. It is a system which is equivalent to λcalculus if I well remember. There are supercombinators system which requires only one combinator, but almost nobody bother with them as they lead to define too ugly terms. > > I'm not saying bind is a better primitive than join/fmap, but > "mathematicians do it this way, therefore it's better" doesn't seem > like a particularly convincing argument either. I never said that, just that the "Monad" name is somehow not very appropriate. > And for a more > philosophical question, is something not a functor just because we > don't have a Functor instance for it? If we agree that the Monad > class (with no Functor superclass) does implicitly form a Functor > with liftM, then I don't really see what the problem is, apart from > the inconvenience of not being able to use fmap. I forgot about the liftM, so ok, the name is not that inapropriate, although you have to wrap your stuff in the WrappedMonad… > > On Tue, Oct 16, 2012 at 10:37 AM, AUGER Cédric <[hidden email]> > wrote: > > > Le Tue, 16 Oct 2012 09:51:29 0400, > > Jake McArthur <[hidden email]> a écrit : > > > > > On Mon, Oct 15, 2012 at 11:29 PM, Dan Doel <[hidden email]> > > > wrote: > > > > I'd be down with putting join in the class, but that tends to > > > > not be terribly important for most cases, either. > > > > > > Join is not the most important, but I do think it's often easier > > > to define than bind. I often find myself implementing bind by > > > explicitly using join. > > > > join IS the most important from the categorical point of view. > > In a way it is natural to define 'bind' from 'join', but in > > Haskell, it is not always possible (see the Monad/Functor problem). > > > > As I said, from the mathematical point of view, join (often noted μ > > in category theory) is the (natural) transformation which with > > return (η that I may have erroneously written ε in some previous > > mail) defines a monad (and requires some additionnal law). As often > > some points it out, Haskellers are not very right in their > > definition of Monad, not because of the bind vs join (in fact in a > > Monad either of them can be defined from the other one), but > > because of the functor status of a Monad. A monad, should always be > > a functor (at least to fit its mathematical definition). And this > > problem with the functor has probably lead to the use of > > "bind" (which is polymorphic in two type variables) rather than > > "join" (which has only one type variable, and thus is simpler). The > > problem, is that when 'm' is a Haskell Monad which does not belong > > to the Functor class, we cannot define 'bind' in general from > > 'join'. > > > > That is in the context where you have: > > > > return:∀ a. a → (m a) > > join:∀ a. (m (m a)) → (m a) > > x:m a > > f:a → (m b) > > > > you cannot define some term of type 'm b', since you would need to > > use at the end, either 'f' (and you would require to produce a 'a' > > which would be impossible), or 'return' (and you would need to > > produce a 'b', which is impossible), or 'join' (and you would need > > to produce a 'm (m b)', and recursively for that you cannot use > > return which would make you go back to define a 'm b' term) > > > > For that, you need the 'fmap' operation of the functor. > > > > return:∀ a. a → (m a) > > join:∀ a. (m (m a)) → (m a) > > fmap:∀ a b. (a→b) → ((m a)→(m b)) > > x:m a > > f:a → (m b) > > > > in this context defining a term of type 'm b' is feasible (join > > (fmap f x)), so that you can express "bind = \ x f > join (fmap f > > x)". > > > > To sum up, mathematical monads are defined from 'return' and 'join' > > as a mathematical monad is always a functor (so 'fmap' is defined, > > and 'bind', which is more complex than 'join' can be defined from > > 'join' and 'fmap'). Haskell does not use a very good definition for > > their monads, as they may not be instance of the Functor class > > (although most of them can easily be defined as such), and without > > this 'fmap', 'join' and 'return' would be pretty useless, as you > > wouldn't be able to move from a type 'm a' to a type 'm b'. > > > > _______________________________________________ > > HaskellCafe mailing list > > [hidden email] > > http://www.haskell.org/mailman/listinfo/haskellcafe > > _______________________________________________ HaskellCafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskellcafe 
In reply to this post by AUGER Cédric
On Tue, Oct 16, 2012 at 10:37 AM, AUGER Cédric <[hidden email]> wrote:
> join IS the most important from the categorical point of view. > In a way it is natural to define 'bind' from 'join', but in Haskell, it > is not always possible (see the Monad/Functor problem). > > As I said, from the mathematical point of view, join (often noted μ in > category theory) is the (natural) transformation which with return (η > that I may have erroneously written ε in some previous mail) defines a > monad (and requires some additionnal law). This is the way it's typically presented. Can you demonstrate that it is the most important presentation? I'd urge caution in doing so, too. For instance, there is a paper, Monads Need Not Be Endofunctors, that describes a generalization of monads to monads relative to another functor. And there, bind is necessarily primary, because join isn't even well typed. I don't think it's written by mathematicians per se (rather, computer scientists/type theorists). But mathematicians have their own particular interests that affect the way they frame things, and that doesn't mean those ways are better for everyone. > As often some points it out, > Haskellers are not very right in their definition of Monad, not because > of the bind vs join (in fact in a Monad either of them can be defined > from the other one), but because of the functor status of a Monad. A > monad, should always be a functor (at least to fit its mathematical > definition). And this problem with the functor has probably lead to the > use of "bind" (which is polymorphic in two type variables) rather than > "join" (which has only one type variable, and thus is simpler). > The problem, is that when 'm' is a Haskell Monad which does not belong > to the Functor class, we cannot define 'bind' in general from 'join'. I don't think Functor being a superclass of Monad would make much difference. For instance, Applicative is properly a subclass of Functor, but we don't use the minimal definition that cannot reproduce fmap on its own: class Functor f => LaxMonoidal f where unit :: f () pair :: f a > f b > f (a, b) Instead we use a formulation that subsumes fmap: fmap f x = pure f <*> x Because those primitives are what we actually want to use, and it's more efficient to implement those directly than to go through some set of fully orthogonal combinators purely for the sake of mathematical purity. And this goes for Monad, as well. For most of the monads in Haskell, the definition of join looks exactly like a definition of (>>= id), and it's not very arduous to extend that to (>>= f). But if we do define join, then we must recover (>>=) by traversing twice; once for map and once for join. There are some examples where join can be implemented more efficiently than bind, but I don't actually know of any Haskell Monads for which this is the case. And as I mentioned earlier, despite many Haskell folks often not digging into monads as done by mathematicians much (and that's fine), (>>=) does correspond to a nice operation: variable substitution. This is true in category theory, when you talk about algebraic theories, and it's true in Haskell when you start noticing that various little languages are described by algebraic theories. But from this angle, I see no reason why it's _better_ to split variable substitution into two operations, first turning a tree into a tree of trees, and then flattening. It'd be nice if all Functor were a prerequisite for Monad, but even then there are still reasons for making (>>=) a primitive.  Dan _______________________________________________ HaskellCafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskellcafe 
Le Tue, 16 Oct 2012 11:58:44 0400,
Dan Doel <[hidden email]> a écrit : > On Tue, Oct 16, 2012 at 10:37 AM, AUGER Cédric <[hidden email]> > wrote: > > join IS the most important from the categorical point of view. > > In a way it is natural to define 'bind' from 'join', but in > > Haskell, it is not always possible (see the Monad/Functor problem). > > > > As I said, from the mathematical point of view, join (often noted μ > > in category theory) is the (natural) transformation which with > > return (η that I may have erroneously written ε in some previous > > mail) defines a monad (and requires some additionnal law). > > This is the way it's typically presented. Can you demonstrate that it > is the most important presentation? What do you mean by demonstrate? If you do not want to fit the mathematical presentation, then I have nothing to demonstrate, you have your point of view, I have mine and they differ. Now, if you want to fit the mathematical presentation, then a monad is an endofunctor with two natural transformations (η=return and μ=join) satisfying some laws. (when I write 'natural' I mean the mathematical definition of natural, not its common definition as something on which we think immediately, or something which is obvious). A natural transformation from S to T (where S and T are functors from a category C to a category D) is for each object 'x' of C, a morphism from S x to T x satisfying some property. return is a natural transformation from the "Id" functor to the "M" functor (where M is the monad), while join is a natural transformation from the "MM" functor to the "M" functor. If you want to express bind, that would be a natural transformation from a functor F to a functor G from "C*×C" (where C* is the opposite category of C) to the "(Id↓M)" commacategory. F would be defined as (a,b)↦Hom(a, M b) φ:Hom(a',a)×ψ:Hom(b,b')↦λ (f:Hom(a,M b)). (M ψ)∘f∘φ while G would be defined as (a,b)↦Hom(M a, M b) φ:Hom(a',a)×ψ:Hom(b,b')↦λ (f:Hom(M a, M b)). (M ψ)∘f∘(M φ) well, I guess it would be possible to define a monad with 'bind' as a natural transformation, but how complex it would be where 'join' is so simple. Plus 'return' and 'join' can be nicely composed to get the monad laws. > I'd urge caution in doing so, too. For instance, there is a paper, > Monads Need Not Be Endofunctors, that describes a generalization of > monads to monads relative to another functor. Yes, so these are not monads. Your paper being written on 15 pages is some indication that it is more complex than simple monads. I will take a look on your relative adjunctions to understand what it exactly is. > And there, bind is > necessarily primary, because join isn't even well typed. I don't think > it's written by mathematicians per se (rather, computer > scientists/type theorists). But mathematicians have their own > particular interests that affect the way they frame things, and that > doesn't mean those ways are better for everyone. Once again, I never said that Monads with 'join' rather than 'bind' are better in all points. I only said that it better fits the mathematical point of view. Also note, that there is no true wall between sciences. Lot of things being interesting in some scientific domain can also be seen as interesting in some other scientific domain. > > > As often some points it out, > > Haskellers are not very right in their definition of Monad, not > > because of the bind vs join (in fact in a Monad either of them can > > be defined from the other one), but because of the functor status > > of a Monad. A monad, should always be a functor (at least to fit > > its mathematical definition). And this problem with the functor has > > probably lead to the use of "bind" (which is polymorphic in two > > type variables) rather than "join" (which has only one type > > variable, and thus is simpler). The problem, is that when 'm' is a > > Haskell Monad which does not belong to the Functor class, we cannot > > define 'bind' in general from 'join'. > > I don't think Functor being a superclass of Monad would make much > difference. For instance, Applicative is properly a subclass of > Functor, but we don't use the minimal definition that cannot reproduce > fmap on its own: > > class Functor f => LaxMonoidal f where > unit :: f () > pair :: f a > f b > f (a, b) > > Instead we use a formulation that subsumes fmap: > > fmap f x = pure f <*> x > My background on that matter is not strong enough to discuss that point, I never used that stuff. > Because those primitives are what we actually want to use, and it's > more efficient to implement those directly than to go through some set > of fully orthogonal combinators purely for the sake of mathematical > purity. That is not a problem of purity, that is a problem of simplicity. > > And this goes for Monad, as well. For most of the monads in Haskell, > the definition of join looks exactly like a definition of (>>= id), > and it's not very arduous to extend that to (>>= f). But if we do > define join, then we must recover (>>=) by traversing twice; once for > map and once for join. There are some examples where join can be > implemented more efficiently than bind, but I don't actually know of > any Haskell Monads for which this is the case. > > And as I mentioned earlier, despite many Haskell folks often not > digging into monads as done by mathematicians much (and that's fine), > (>>=) does correspond to a nice operation: variable substitution. This > is true in category theory, when you talk about algebraic theories, > and it's true in Haskell when you start noticing that various little > languages are described by algebraic theories. But from this angle, I > see no reason why it's _better_ to split variable substitution into > two operations, first turning a tree into a tree of trees, and then > flattening. Shouldn't variable substitution be done by mapping? > > It'd be nice if all Functor were a prerequisite for Monad, but even > then there are still reasons for making (>>=) a primitive. I do not mean the contrary, and I am very sorry if all readers consider me as a troll. > >  Dan _______________________________________________ HaskellCafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskellcafe 
On Tue, Oct 16, 2012 at 1:19 PM, AUGER Cédric <[hidden email]> wrote:
What do you mean by demonstrate? If you do not want to fit the I think the point is that Monad is not part of Haskell to satisfy mathematical (or categorical) purity, but to solve a particular set of problems. Those problems are best addressed with bind, and join works rather less well for them. Since one of those problems involves interfacing with the world outside of the program, an inefficient but categorically/mathematically more "pure" solution may not be a viable option in practice.
Alternative Preludes which focus on other purposes are a dime a dozen; if you want a categorically pure Monad, nothing stops you from writing one and using it. brandon s allbery kf8nh sine nomine associates
unix/linux, openafs, kerberos, infrastructure http://sinenomine.net _______________________________________________ HaskellCafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskellcafe 
In reply to this post by AUGER Cédric
I think the version below (with a Functor or Applicative superclass)
is clearly the right answer if we were putting the prelude together from a clean slate. You can implement whichever is easiest for the particular monad, use whichever is most appropriate to the context (and add optimized versions if you prove to need them). I see no advantage in any other specific proposal, except the enormous advantage held by the status quo that it is already written, already documented, already distributed, and already coded to. Regarding mathematical "purity" of the solutions, "this is in every way isomorphic to a monad, but we aren't calling it a monad because we are describing it a little differently than the most common way to describe a monad in category theory" strikes me as *less* mathematically grounded than "we are calling this a monad because it is in every way isomorphic to a monad." On Tue, Oct 16, 2012 at 7:03 AM, AUGER Cédric <[hidden email]> wrote: > > So I think that an implicit question was why wouldn't we have: > > class Monad m where > return :: a > m a > kleisli :: (a > m b) > (b > m c) > (a > m c) > bind = \ x f > ((const x) >=> f) () > join = id>=>id :: (m (m a) > m a) > _______________________________________________ > HaskellCafe mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/haskellcafe _______________________________________________ HaskellCafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskellcafe 
Not sure I really have anything substantial to contribute, but it's certainly true that if you see a > m b as a generalisation of the usual function type, a > b, then return generalises the identity and kleisli generalises function composition. This makes the types pretty memorable (and often the definitions too). Simon On 16 Oct 2012, at 20:14, David Thomas <[hidden email]> wrote: >> class Monad m where >> return :: a > m a >> kleisli :: (a > m b) > (b > m c) > (a > m c) Simon Thompson  Professor of Logic and Computation School of Computing  University of Kent  Canterbury, CT2 7NF, UK [hidden email]  M +44 7986 085754  W www.cs.kent.ac.uk/~sjt _______________________________________________ HaskellCafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskellcafe 
When I teach my students Haskell's monads, I never put "Kleisli" into my
mouth. I tell them that monads are for sequencing effects; and the sequencing is visible clearly in (>>) :: IO a > IO b > IO b (>>=) :: IO a > (a > IO b) > IO b but not in fmap :: (a > b) > IO a > IO b join :: IO (IO a) > IO a To me, print 1 >> print 2 looks natural, and print 1 >>= const (print 2) still understandable, but join $ fmap (const (print 2)) (print 1) rather not (I needed ghci to get this example right). I would not want to introduce category theory or Kleisli composition just to teach my students some effectful Haskell programming. Cheers, Andreas On 16.10.2012 21:45, Simon Thompson wrote: > > Not sure I really have anything substantial to contribute, but it's certainly true that if you see > > a > m b > > as a generalisation of the usual function type, a > b, then return generalises the identity and > kleisli generalises function composition. This makes the types pretty memorable (and often the > definitions too). > > Simon > > > On 16 Oct 2012, at 20:14, David Thomas <[hidden email]> wrote: > >>> class Monad m where >>> return :: a > m a >>> kleisli :: (a > m b) > (b > m c) > (a > m c) > > Simon Thompson  Professor of Logic and Computation > School of Computing  University of Kent  Canterbury, CT2 7NF, UK > [hidden email]  M +44 7986 085754  W www.cs.kent.ac.uk/~sjt > > > _______________________________________________ > HaskellCafe mailing list > [hidden email] > http://www.haskell.org/mailman/listinfo/haskellcafe >  Andreas Abel <>< Du bist der geliebte Mensch. Theoretical Computer Science, University of Munich Oettingenstr. 67, D80538 Munich, GERMANY [hidden email] http://www2.tcs.ifi.lmu.de/~abel/ _______________________________________________ HaskellCafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskellcafe 
Administrator

In reply to this post by AUGER Cédric
On Tue, Oct 16, 2012 at 9:37 PM, AUGER Cédric <[hidden email]> wrote:
As I said, from the mathematical point of view, join (often noted μ in Auger: Your emails keep invoking "the mathematical point of view" as if it were something unique and universal.
Mathematical definitions are created and adopted to the extent that they give rise to interesting, meaningful proofs. Coding in Haskell is precisely proving theorems in a branch of constructive mathematics. Its practitioners have found one set of monad definitions more intuitive and sensible when working on such proofs than another such set.
I don't understand your dogmatism about return and join being canonically the best monad definition in all possible mathematics. That's truly a quantifier that beggars imagination. On Tue, Oct 16, 2012 at 9:37 PM, AUGER Cédric <[hidden email]> wrote: Le Tue, 16 Oct 2012 09:51:29 0400, _______________________________________________ HaskellCafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskellcafe 
Free forum by Nabble  Edit this page 