<p>I am going to answer the question from your title in a slightly facetious way:</p>
<blockquote>
<p>Computable maps are closed under composition, and the identity map is computable, therefore the collection of all computable maps <span class="math-container">$\mathbb{N} \to \mathbb{N}$</span> forms a <em>monoid</em> with respect to composition.</p>
</blockquote>
<p>Perhaps you meant to aks whether there was a <em>monad</em> involved, in which case:</p>
<blockquote>
<p>The category of sets and <em>partial</em> maps is equivalent to the Kleisly category for the lifting monad. The equivalence specializes to a computable setting, such as PER model or more generally a realizability topos. Therefore, the computable partial maps can be seen as effectful maps, where the effect is that of non-termination, as captured by the lifting monad.</p>
</blockquote>
<p>I do not think this is what you asked, but perhaps seeing the answer will make it clearer to you that the audience is having trouble understanding your question.</p>

CC BY-SA 4.0
2020-07-30T17:05:40.903Z
I appreciate you taking a stab at answering the question. You're right that it doesn't answer my question per se, but provides me food for thought to help my hash out the missing pieces in my understanding. For context, this question was an off-shoot of this one on CS.se: https://cs.stackexchange.com/questions/128627/a-monad-is-just-a-monoid-in-the-category-of-endofunctors-whats-the-enlightenme/128628?noredirect=1#comment268849_128628
PhD
CC BY-SA 4.0
2020-07-28T08:12:50.390Z
2020-07-28T08:12:50.390Z
Andrej Bauer
<p>I have been studying some category theory only to understand the &quot;why&quot; behind the various categorical constructs we use (&quot;borrow&quot;) in the world of functional programming.</p>
<p>One of the oft cited <em>maxims</em> is this:</p>
<p><code>A monad is just a monoid in the category of endofunctors</code></p>
<p>Can we structure all programs to be a composition of pure and monadic functions and nothing else? If so, would the resultant &quot;compositional structure&quot; be monoidal?</p>
<p>Is it fair to infer such a &quot;monoidal property&quot; to exist for all programs (i.e., computable functions) ?</p>
<p>It <em>seems</em> that this should be intuitively true, but I'm not sure where (if at all) is a flaw in this inference? What may I be missing?</p>

CC BY-SA 4.0
2020-07-24T12:49:40.827Z
It is not clear what you are asking, at least not to me. What are some precise examples of "monoidal structure" that you speak of? Are you just talking about monads and the fact that the Kleisli category of a monad captures (in some cases) a notion of effectful computation?
Andrej Bauer
CC BY-SA 4.0
2020-07-25T05:59:44.923Z
I too think that the question is unclear.  First of all, you probably mean *monadic* rather than "monoidal", as you seem to be talking about monads whereas the latter adjective usually has [a different meaning in category theory](https://en.wikipedia.org/wiki/Monoidal_category).  And the fact that a monad is a monoid in the the category of endofunctors is not a "maxim", it's a mathematical fact/definition.  Also, if you say that your programming language is represented by a category $C$, then of course you can't go outside of $C$ if you don't go outside of your programming language.
Damiano Mazza
CC BY-SA 4.0
2020-07-25T06:01:47.347Z
And no, cartesian closure has nothing to do with mixing pure and impure functions: it simply means that you may "curry/uncurry" your functions to freely go back and forth between $(A\times B)\to C$ and $A\to B\to C$.  What does your "chain" $C\to C\to C\to\cdots$ refer to?  Are you composing monads?  Do you know that [monads do not compose in general](https://en.wikipedia.org/wiki/Distributive_law_between_monads)?  What in the world is a "meta-reason" and what "loop" are you closing?  It is difficult to tell weather a reasoning is flawed or not when the reasoning itself is so confusing...
Damiano Mazza
CC BY-SA 4.0
2020-07-25T06:02:44.417Z
Finally, category theory is not a model of computation; it is an extremely powerful mathematical language which allows you, among other things, to speak of computation, stateful or functional, without any real preference between the two.  The fact that categories seem more closely related to $\lambda$-calculus than Turing machines is more of a linguistic artifact than a technical reality.
Damiano Mazza
CC BY-SA 4.0
2020-07-28T00:40:05.197Z
@AndrejBauer - To clarify, can any (i.e., every) program be _structured_ as a composition of pure and monadic functions and nothing else? If so, is this result "compositional structure" monoidal?
PhD
CC BY-SA 4.0
2020-07-28T00:42:41.687Z
@DamianoMazza - thanks for the clarification on CCCs. To your other point, I understand Cat is not a model of computation. My question was more around "structure of programs when rewritten from Category Theory POV". I've add the comment above in response to Andrej Bauer - I've also updated the question to reflect this.
PhD
CC BY-SA 4.0
2020-07-28T08:03:39.833Z
Nope, still unclear. You are asking a question about a very well-developed area of PL research which abounds in precise concepts. You should strive to ask your question without using any derision quotes. Words like "monoidal" have a few meanings, all of them precise. If there is some unclarity about how monads are used to model computation, perhaps you should ask a more basic question about that (and judge apprpriately whether the question belongs here or on CS SE). As it stands, your question is not clear, at least not to me.
Andrej Bauer
CC BY-SA 4.0
2020-07-28T08:06:16.300Z
Here's another problem. When you say "all programs are X" that is almost never going to make sense, unless you carefully delimit what you mean by "program". Words like "computation" and "program" are open-ended concepts that develop through time. If you are asking a mathematical question (about things being monadic or monoidal) then you should refer to precise concepts. Fix a programming language and ask a question about it, then at lest we'll have some context. (And we'll discover what many books explain, namely that monads give compositional structure to effectful computation.)
Andrej Bauer
CC BY-SA 4.0
2020-07-29T07:56:30.383Z
I am sorry but I still don't understand what you're asking. The adjective "monoidal" needs to be clarified. If you are asking about whether a certain structure is a monoid, then you need to be precise about this structure, like Andrej says. What is a "program"? What is a "pure function"? What is a "monadic function"?  Also, what do you mean by "rewriting" a program from the point of view of category theory?  You mean seeing a program as a morphism of a category?
Damiano Mazza
CC BY-SA 4.0
2020-07-30T17:02:00.067Z
@DamianoMazza - I understand. My lack of making the terms precise reflects my lack of understanding the category theory domain. I need to _go back to the drawing board_ and think this through.
PhD
<computability><ct.category-theory>
Are all computable functions monoidal from a category theory POV?
PhD
# Are all computable functions monoidal from a category theory POV?

(Asked by: username_0 on 2020-07-23)

I have been studying some category theory only to understand the "why" behind the various categorical constructs we use ("borrow") in the world of functional programming.

One of the oft cited *maxims* is this:

`A monad is just a monoid in the category of endofunctors`

Can we structure all programs to be a composition of pure and monadic functions and nothing else? If so, would the resultant "compositional structure" be monoidal?

Is it fair to infer such a "monoidal property" to exist for all programs (i.e., computable functions) ?

It *seems* that this should be intuitively true, but I'm not sure where (if at all) is a flaw in this inference? What may I be missing?

**Tags:** computability, ct.category-theory

> **Comments:**
> **username_1**: It is not clear what you are asking, at least not to me. What are some precise examples of "monoidal structure" that you speak of? Are you just talking about monads and the fact that the Kleisli category of a monad captures (in some cases) a notion of effectful computation?  
> **username_2**: I too think that the question is unclear.  First of all, you probably mean *monadic* rather than "monoidal", as you seem to be talking about monads whereas the latter adjective usually has [a different meaning in category theory](https://en.wikipedia.org/wiki/Monoidal_category).  And the fact that a monad is a monoid in the the category of endofunctors is not a "maxim", it's a mathematical fact/definition.  Also, if you say that your programming language is represented by a category $C$, then of course you can't go outside of $C$ if you don't go outside of your programming language.  
> **username_2**: And no, cartesian closure has nothing to do with mixing pure and impure functions: it simply means that you may "curry/uncurry" your functions to freely go back and forth between $(A\times B)\to C$ and $A\to B\to C$.  What does your "chain" $C\to C\to C\to\cdots$ refer to?  Are you composing monads?  Do you know that [monads do not compose in general](https://en.wikipedia.org/wiki/Distributive_law_between_monads)?  What in the world is a "meta-reason" and what "loop" are you closing?  It is difficult to tell weather a reasoning is flawed or not when the reasoning itself is so confusing...  
> **username_2**: Finally, category theory is not a model of computation; it is an extremely powerful mathematical language which allows you, among other things, to speak of computation, stateful or functional, without any real preference between the two.  The fact that categories seem more closely related to $\lambda$-calculus than Turing machines is more of a linguistic artifact than a technical reality.  
> **username_0**: @AndrejBauer - To clarify, can any (i.e., every) program be _structured_ as a composition of pure and monadic functions and nothing else? If so, is this result "compositional structure" monoidal?  
> **username_0**: @DamianoMazza - thanks for the clarification on CCCs. To your other point, I understand Cat is not a model of computation. My question was more around "structure of programs when rewritten from Category Theory POV". I've add the comment above in response to username_1 - I've also updated the question to reflect this.  
> **username_1**: Nope, still unclear. You are asking a question about a very well-developed area of PL research which abounds in precise concepts. You should strive to ask your question without using any derision quotes. Words like "monoidal" have a few meanings, all of them precise. If there is some unclarity about how monads are used to model computation, perhaps you should ask a more basic question about that (and judge apprpriately whether the question belongs here or on CS SE). As it stands, your question is not clear, at least not to me.  
> **username_1**: Here's another problem. When you say "all programs are X" that is almost never going to make sense, unless you carefully delimit what you mean by "program". Words like "computation" and "program" are open-ended concepts that develop through time. If you are asking a mathematical question (about things being monadic or monoidal) then you should refer to precise concepts. Fix a programming language and ask a question about it, then at lest we'll have some context. (And we'll discover what many books explain, namely that monads give compositional structure to effectful computation.)  
> **username_2**: I am sorry but I still don't understand what you're asking. The adjective "monoidal" needs to be clarified. If you are asking about whether a certain structure is a monoid, then you need to be precise about this structure, like Andrej says. What is a "program"? What is a "pure function"? What is a "monadic function"?  Also, what do you mean by "rewriting" a program from the point of view of category theory?  You mean seeing a program as a morphism of a category?  
> **username_0**: @DamianoMazza - I understand. My lack of making the terms precise reflects my lack of understanding the category theory domain. I need to _go back to the drawing board_ and think this through.  

---

## 1 answers

### Answer by username_1 on 2020-07-28. Score: 1

I am going to answer the question from your title in a slightly facetious way:

> Computable maps are closed under composition, and the identity map is computable, therefore the collection of all computable maps $\mathbb{N} \to \mathbb{N}$ forms a *monoid* with respect to composition.

Perhaps you meant to aks whether there was a *monad* involved, in which case:

> The category of sets and *partial* maps is equivalent to the Kleisly category for the lifting monad. The equivalence specializes to a computable setting, such as PER model or more generally a realizability topos. Therefore, the computable partial maps can be seen as effectful maps, where the effect is that of non-termination, as captured by the lifting monad.

I do not think this is what you asked, but perhaps seeing the answer will make it clearer to you that the audience is having trouble understanding your question.

> **Comments:**
> **username_0**: I appreciate you taking a stab at answering the question. You're right that it doesn't answer my question per se, but provides me food for thought to help my hash out the missing pieces in my understanding. For context, this question was an off-shoot of this one on CS.se: https://cs.stackexchange.com/questions/128627/a-monad-is-just-a-monoid-in-the-category-of-endofunctors-whats-the-enlightenme/128628?noredirect=1#comment268849_128628  

---

