# Are all computable functions monoidal from a category theory POV? [closed]

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?

• 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 Jul 24 at 12:49
• 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. 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 Jul 25 at 5:59
• 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? 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 Jul 25 at 6:01
• 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 Jul 28 at 8:03
• 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 Jul 28 at 8:06

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.