# How to tell if an effect is algebraic?

I've read Bauer's What is algebraic about algebraic effects and handlers? and he talks about IO being an algebraic effect, even though it doesn't have any equations. In other papers on algebraic effects and handlers, people mention effects that are not algebraic, like backtracking. How does one can tell an algebraic effect apart from a non-algebraic one?

• Backtracking can be algebraic, at least most versions of it. Can you give an exact pointer to these claims? – Andrej Bauer Feb 24 '19 at 18:32
• I was sloppy when writing that. Pretnar's An Introduction to Algebraic Effects and Handlers (on page 14) says backtracking do not respect equations and cannot receive a homomorphic interpretation, so I assumed it wasn't algebraic. Also, given that continuations aren't algebraic, I also assumed asynchrony would not be algebraic as well. Conversation "on the streets" about it often lead to "yeah, but the interesting effects aren't algebraic", hence my question. – Jesper Dahl Feb 25 '19 at 15:16
• Pretnar's point is that the expected equations are not satisfied. This means that by removing them we will get an algebraic effect. – Andrej Bauer Feb 25 '19 at 19:11
• Asynchronous execution is algebraic because the continuations are delimited, like in the example of multi-threading from the "Programming with algebraic effects and handlers". So let it be known in the street that perhaps one should think first. – Andrej Bauer Feb 25 '19 at 19:12
• One possible thing to note is that some of the things that are categorized as not algebraic in some papers on effects actually are algebraic in the sense that you can make sense of the operations in a (countable enriched) Lawvere theory. The example I know of is catching exceptions. So sometimes the classification is not made on a completely rigorous basis (perhaps because it predates the formalism). – Dan Doel Mar 9 '19 at 0:52

The general answer which you do not want to hear is: an effect is algebraic if it can be described using operations and equations. The question is a bit open-ended and gives no hint as to what you're expecting, so perhaps you deserve such a useless answer.

Nevertheless, it's still good to know some typical examples, as they help you develop a feeling for things:

1. Continuations are not algebraic. That's important because there are effects that let you encode continuations, and so those are not aglebraic either. (But be careful about the meaning of "encode").

2. Delimited continuations are algebraic, see Section 6.11 of "Programming with algebraic effects and handlers". Because asynchronuous threads, cooperative multi-threading etc., are a form of delimited continuation, these usually fall into the realm of algebraic effects.

3. If your effect looks like you're passing around state of some sort, then it's likely algebraic.

4. Nondeterministic choice, search, etc., are typically algebraic.

5. Exception-like effects are algebraic (transactions of various sorts are included).