Le Mon, 15 Oct 2012 15:12:28 +0200, Benjamin Franksen a écrit :

Ertugrul Söylemez wrote:

...

damodar kulkarni 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 non-categorical 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 non-categorical 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).

On Mon, Oct 15, 2012 at 11:33 AM, Jake McArthur wrote:

On Mon, Oct 15, 2012 at 7:59 AM, Ertugrul Söylemez 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 Arrow-style combinators: f &=& g = runKleisli $ Kleisli f &&& Kleisli g print <=< const getLine &=& const getLine $ ()

On Mon, Oct 15, 2012 at 10:05 PM, damodar kulkarni wrote:

@Jake

...

In my opinion, this is not as nice as the do-notation 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.

=> g) x = f x >>= g'. The function cannot be inspected to get the result except by applying it. I suppose one _can_ write (>=>)

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 Eilenberg-Moore 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 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

Le Tue, 16 Oct 2012 09:51:29 -0400, Jake McArthur a écrit :

On Mon, Oct 15, 2012 at 11:29 PM, Dan Doel 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'.

Le Tue, 16 Oct 2012 11:22:08 -0400, Daniel Peebles 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 wrote:

...

Le Tue, 16 Oct 2012 09:51:29 -0400, Jake McArthur a écrit :

...

On Mon, Oct 15, 2012 at 11:29 PM, Dan Doel 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'.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Le Tue, 16 Oct 2012 11:58:44 -0400, Dan Doel a écrit :

On Tue, Oct 16, 2012 at 10:37 AM, AUGER Cédric 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)" comma-category. 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

Dan Doel wrote:

On Tue, Oct 16, 2012 at 10:37 AM, AUGER Cédric 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.

Right. Mathematical /conventions/ can and should be questioned. Sometimes they are not appropriate to the application domain. Sometimes the conventions are just stupid or obsolete even in a purely mathematical context (a well-known example is the extra "syntax sugar" for binomial coefficients, but there are worse ones), and you still find them in modern text books. Talk about "backwards compatibility"... My preference for Kleisli composition is because it makes the monad laws so much easier to write down and understand. Everywhere it is said that >>= must be "associative" and then the laws are written down for >>= and return and it is very hard to see what this "lambda grave" has to do with associativity or units. When I started with Haskell, this was all I could find. It was years later that I stumbled over a text that explained it with

=> and suddenly it all became simple and clear and I finally understood the monad laws!

=> in terms of >>= and vice versa, so that you can still use >>= as the

So, maybe >>= is the better primitive operation w.r.t. implementation, but IMO >=> is *much* more efficient w.r.t. understanding the monad laws. Since it is natural to explain the laws of a class using only class methods, I would prefer if >=> was added to the class with default implementations for primitive operation when implementing an instance. Cheers -- Ben Franksen () ascii ribbon campaign - against html e-mail /\ www.asciiribbon.org - against proprietary attachments

Le Wed, 24 Oct 2012 12:36:52 +0700, Kim-Ee Yeoh a écrit :

On Tue, Oct 16, 2012 at 9:37 PM, AUGER Cédric wrote:

...

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).

Auger:

Your emails keep invoking "the mathematical point of view" as if it were something unique and universal.

It is not my wish to be a troller. So please keep or don't keep your point of view on that matter, and I'll keep mine. bind is an injection of a Kleisli category to the Hask category to allow composition, return is the identity of that same Kleisli category. I do not pretend to be useless, just that the name "Monad" does not fit very well. I do not want to fight the people who have chosen this name, which has spread to many other paradigms. I just say that it is not very fortunate.

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.

Once again that set is not uninteresting, just the name does not fit very well. And for your comment on proofs, I am perfectly aware of the Curry Howard correspondance, and that proofs given by Haskell programs are not very interesting from a mathematical point of view (beside the fact that this system is unsound, ie. any statement [ie. a type] can be proved [ie. admits a program of that type], due to the "undefined" value [I do not want to enter a new troll of wether "undefined" is or is not a value, if the word value does not please you, replace it]).

I don't understand your dogmatism about return and join being canonically the best monad definition in all possible mathematics.

I am not that dogmatic, if I need to write a program on Haskell, I won't cry because I will produce some "IO stuff".

That's truly a quantifier that beggars imagination.

-- Kim-Ee

On Tue, Oct 16, 2012 at 9:37 PM, AUGER Cédric wrote:

...

Le Tue, 16 Oct 2012 09:51:29 -0400, Jake McArthur a écrit :

...

On Mon, Oct 15, 2012 at 11:29 PM, Dan Doel 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'.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

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 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) _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

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 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 s.j.thompson@kent.ac.uk | M +44 7986 085754 | W www.cs.kent.ac.uk/~sjt

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Andreas Abel <>< Du bist der geliebte Mensch. Theoretical Computer Science, University of Munich Oettingenstr. 67, D-80538 Munich, GERMANY andreas.abel@ifi.lmu.de http://www2.tcs.ifi.lmu.de/~abel/

The particular case from which the former is a generalization: *instance Monad m => Monoid (a -> a) where* * mappend = (.)* * mempty = id* * * Here the monoid is defined for the functions within the set of values of type a. There are no null elements. 2012/10/24 Alberto G. Corona

What hiders according with my experience, the understanding of this generalization are some mistakes. two typical mistakes from my side was to consider an arrow as a function, and the consideration of m as a kind of container, which it is not from the point of view of category theory.

a -> m b

instead of as a container, 'm b' must be considered as the set of elements of type b (wrapped within some constructor) plus zero or more null elements of the monad 'm', Such are elements like, for example, Nothing, the empty list or Left . so that:

null >>= f= null and f >>= \x -> null= null

in the other side (->) is an arrow of category theory, not a function.That means that there may be weird additional things that functions are not be permitted to have. For example, from an element in the set of 'a' may depart many arrows to elements of 'b'. This permits the nondeterminism of the list monad.

A function like this:

repeatN :: Int -> a -> [a]

can have two interpretations: one functional interpretation, where repeatN is a pure function with results in the list container. The other is the category interpretation, where 'repeatN n' is a morphism that produces n arrows from the set of the Strings to the set of String plus the empty set, The list container is a particular case of container that hold the result of this nondeterministic morphism (other instantiations of this nondeterministic monad would be a set monad or whatever monad build using a multielement container. The container type is not the essence. the essence it is the nondeterministic nature, which, in haskell practical terms, needs a multielement container to hold the multiple results).

so the monadic re-ínterpretation of the repeatN signature is:

repeatN ::Int -> a -> a + {[]}

Here the empty list is the null element of the list monad

in the same way: functional signature: a -> Maybe b monadic interpretation: a -> b + {Nothing}

functional signature: a -> Either c b monadic interpretation: a -> b + {Left c}

So when i see m b in the context of a monad, I think on nothing more that the set of values of type b (wrapped within some constructor) plus some null elements (if they exist).

so in essence

a -> m b

is a -> (b + some null elements)

that´s a generalisation of a -> b

where -> is an arrow, not a function (can return more than one result, can return different things on each computation etc)

And this instance of monoid show how kleisly is the composition and return is the identity element

*instance Monad m => Monoid (a -> m a) where* * mappend = (>=>)* * mempty = return* * *

According with the above said, 'a -> m a' must be understood as the set of monadic endomorphisms in a:

a -> a +{null elements of the monad m}

Which is, in essence, a -> a

2012/10/16 Simon Thompson

...

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 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 s.j.thompson@kent.ac.uk | M +44 7986 085754 | W www.cs.kent.ac.uk/~sjt

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Alberto.

-- Alberto.

Tony Morris wrote:

As a side note, I think a direct superclass of Functor for Monad is not a good idea, just sayin'

class Functor f where fmap :: (a -> b) -> f a -> f b

class Functor f => Apply f where (<*>) :: f (a -> b) -> f a -> f b

class Apply f => Bind f where (=<<) :: (a -> f b) -> f a -> f b

class Apply f => Applicative f where unit :: a -> f a

class (Applicative f, Bind f) => Monad f where

Same goes for Comonad (e.g. [] has (=<<) but not counit) ... and again for Monoid, Category, I could go on...

Hi Tony even though I dismissed your mentioning this on the Haskell' list, I do have to admit that the proposal has a certain elegance. However, before I buy into this scheme, I'd like to see some striking examples for types with natural (or at least useful) Apply and Bind instances that cannot be made Applicative resp. Monad. Also, it is not clear to me what laws should hold for them. Cheers -- Ben Franksen () ascii ribbon campaign - against html e-mail /\ www.asciiribbon.org - against proprietary attachments

Brent Yorgey wrote:

On Thu, Nov 29, 2012 at 03:52:58AM +0100, Ben Franksen wrote:

...

Tony Morris wrote:

...

As a side note, I think a direct superclass of Functor for Monad is not a good idea, just sayin'

class Functor f where fmap :: (a -> b) -> f a -> f b

class Functor f => Apply f where (<*>) :: f (a -> b) -> f a -> f b

class Apply f => Bind f where (=<<) :: (a -> f b) -> f a -> f b

class Apply f => Applicative f where unit :: a -> f a

class (Applicative f, Bind f) => Monad f where

Same goes for Comonad (e.g. [] has (=<<) but not counit) ... and again for Monoid, Category, I could go on...

Hi Tony

even though I dismissed your mentioning this on the Haskell' list, I do have to admit that the proposal has a certain elegance. However, before I buy into this scheme, I'd like to see some striking examples for types with natural (or at least useful) Apply and Bind instances that cannot be made Applicative resp. Monad.

Try writing an Applicative instances for (Data.Map.Map k). It can't be done, but the Apply instance is (I would argue) both natural and useful.

I see. So there is one example. Are there more? I'd like to get a feeling for the abstraction and this is hard if there is only a single example.

...

Also, it is not clear to me what laws should hold for them.

http://hackage.haskell.org/package/semigroupoids defines all of these and specifies laws, presumably derived in a principled way.

Ok. I was not surprised to see that there are not many laws for the classes without unit. Cheers -- Ben Franksen () ascii ribbon campaign - against html e-mail /\ www.asciiribbon.org - against proprietary attachments

Lists! The finite kind. This could mean Seq for instance. On Nov 30, 2012 9:53 AM, "Brent Yorgey" wrote:

On Fri, Nov 30, 2012 at 02:33:54AM +0100, Ben Franksen wrote:

...

Brent Yorgey wrote:

...

On Thu, Nov 29, 2012 at 03:52:58AM +0100, Ben Franksen wrote:

...

Tony Morris wrote:

...

As a side note, I think a direct superclass of Functor for Monad is not a good idea, just sayin'

class Functor f where fmap :: (a -> b) -> f a -> f b

class Functor f => Apply f where (<*>) :: f (a -> b) -> f a -> f b

class Apply f => Bind f where (=<<) :: (a -> f b) -> f a -> f b

class Apply f => Applicative f where unit :: a -> f a

class (Applicative f, Bind f) => Monad f where

Same goes for Comonad (e.g. [] has (=<<) but not counit) ... and again for Monoid, Category, I could go on...

Hi Tony

even though I dismissed your mentioning this on the Haskell' list, I do have to admit that the proposal has a certain elegance. However, before I buy into this scheme, I'd like to see some striking examples for types with natural (or at least useful) Apply and Bind instances that cannot be made Applicative resp. Monad.

Try writing an Applicative instances for (Data.Map.Map k). It can't be done, but the Apply instance is (I would argue) both natural and useful.

I see. So there is one example. Are there more? I'd like to get a feeling for the abstraction and this is hard if there is only a single example.

Any data type which admits structures of arbitrary but *only finite* size has a natural "zippy" Apply instance but no Applicative (since pure would have to be an infinite structure). The Map instance I mentioned above falls in this category. Though I guess I'm having trouble coming up with other examples, but I'm sure some exist. Maybe Edward knows of other examples.

-Brent

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Gershom Bazerman wrote:

On 11/30/12 10:44 AM, Dan Doel wrote:

...

Lists! The finite kind.

This could mean Seq for instance.

On Nov 30, 2012 9:53 AM, "Brent Yorgey" mailto:byorgey@seas.upenn.edu> wrote:

Any data type which admits structures of arbitrary but *only finite* size has a natural "zippy" Apply instance but no Applicative (since pure would have to be an infinite structure). The Map instance I mentioned above falls in this category. Though I guess I'm having trouble coming up with other examples, but I'm sure some exist.

Maybe

...

Edward knows of other examples.

Another common case would be an embedded DSL representing code in a different language, targeting a different platform (or even an FPGA or the like), etc. You can apply `OtherLang (a -> b)` to an `OtherLang a` and get an `OtherLang b`, but you clearly can't promote (or "lower," I guess) an arbitrary Haskell function into a function in your target language. This is the same reason that GArrows remove the `arr` function (http://www.cs.berkeley.edu/~megacz/garrows/).

A fine example! And I am getting the drift... yes, this could be a useful abstraction. Now, on to Bind: the standard finite structure example for Bind is most probably the substitution thingy, i.e. if m :: m a, f :: a -> m b, then m

...

= f means replace all elements x :: a in m with f x and then flatten the result so it's an m b again. Like concatMap for lists, right? So, there is no return for that in the Map case for exactly the same reason as with Apply: the unit would have have value id for every possible key, so cannot be finite.

So what about an example for Bind\\Monad that is not yet another variation of the finite structure theme? Cheers -- Ben Franksen () ascii ribbon campaign - against html e-mail /\ www.asciiribbon.org - against proprietary attachments