<p>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.</p>

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

<ol>
<li><p>Continuations are <em>not</em> 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").</p></li>
<li><p>Delimited continuations are algebraic, see Section 6.11 of <a href="https://arxiv.org/pdf/1203.1539v1.pdf" rel="noreferrer">"Programming with algebraic effects and handlers"</a>. Because asynchronuous threads, cooperative multi-threading etc., are a form of delimited continuation, these usually fall into the realm of algebraic effects.</p></li>
<li><p>If your effect looks like you're passing around state of some sort, then it's likely algebraic.</p></li>
<li><p>Nondeterministic choice, search, etc., are typically algebraic.</p></li>
<li><p>Exception-like effects are algebraic (transactions of various sorts are included).</p></li>
<li><p>Anything that looks like communication (I/O, reader monad) is algebraic.</p></li>
<li><p>Probabilistic programming is algebraic.</p></li>
</ol>

<p>Most useful effects fall under one of these cases. If I forgot anything, I am sure people will remind me in the comments.</p>

CC BY-SA 4.0
2019-02-25T19:14:37.947Z
I updated the delimited continuations example to point out that threads and thread-like effects are algebraic.
Andrej Bauer
CC BY-SA 4.0
2019-02-26T12:31:02.147Z
What about local state i.e. ML's ref type where you can dynamically allocate references? Or the special case of fresh name generation.
Max New
CC BY-SA 4.0
2019-02-26T14:03:55.437Z
Fresh name generation (and the related question of dynamically created instances of effects) is perhaps the most interesting "open" problem. We do not really have a good account of these, I think. In Eff we had *resources* which did what ML references do, but that was not theoretically satisfying. However, it's clear that in essence the nature of references is some mix of algebraic effects and fresh name generation. Fresh name generation, however, is special and requires something extra. Of course, people have attacked this topic, but the final word is not in yet, in my opinion.
Andrej Bauer
CC BY-SA 4.0
2019-02-26T20:32:05.103Z
I think a good answer to this question would be to say how to show effects are *not* algebraic. I think continuations are not because of size issues, but are there any other examples?
Max New
CC BY-SA 4.0
2019-02-27T19:03:40.700Z
What do you mean by "show effects"?
Jesper Dahl
CC BY-SA 4.0
2019-02-27T20:36:26.710Z
"How to show that effects are not algebraic."
Andrej Bauer
CC BY-SA 4.0
2019-02-24T18:39:46.683Z
2019-02-25T19:14:11.307Z
2019-02-25T19:14:11.307Z
Andrej Bauer
<p>I've read Bauer's <a href="https://arxiv.org/abs/1807.05923" rel="noreferrer">What is algebraic about algebraic effects and handlers?</a> 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?</p>

CC BY-SA 4.0
2019-02-24T18:32:27.257Z
Backtracking can be algebraic, at least most versions of it. Can you give an exact pointer to these claims?
Andrej Bauer
CC BY-SA 4.0
2019-02-25T15:16:33.237Z
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
CC BY-SA 4.0
2019-02-25T19:11:26.663Z
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
CC BY-SA 4.0
2019-02-25T19:12:47.243Z
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
CC BY-SA 4.0
2019-03-09T00:52:04.350Z
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
<pl.programming-languages>
How to tell if an effect is algebraic?
Jesper Dahl
# How to tell if an effect is algebraic?

(Asked by: username_0 on 2019-02-24)

I've read Bauer's [What is algebraic about algebraic effects and handlers?](https://arxiv.org/abs/1807.05923) 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?

**Tags:** pl.programming-languages
> **Comments:**
> **username_1**: Backtracking can be algebraic, at least most versions of it. Can you give an exact pointer to these claims?  
> **username_0**: 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.  
> **username_1**: Pretnar's point is that the expected equations are not satisfied. This means that by *removing* them we will get an algebraic effect.  
> **username_1**: 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.  
> **username_2**: 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).  

---

## 1 answers

### Answer by username_1 on 2019-02-24. Score: 10 | Accepted answer

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"](https://arxiv.org/pdf/1203.1539v1.pdf). 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).
6. Anything that looks like communication (I/O, reader monad) is algebraic.
7. Probabilistic programming is algebraic.

Most useful effects fall under one of these cases. If I forgot anything, I am sure people will remind me in the comments.

> **Comments:**
> **username_1**: I updated the delimited continuations example to point out that threads and thread-like effects are algebraic.  
> **username_3**: What about local state i.e. ML's ref type where you can dynamically allocate references? Or the special case of fresh name generation.  
> **username_1**: Fresh name generation (and the related question of dynamically created instances of effects) is perhaps the most interesting "open" problem. We do not really have a good account of these, I think. In Eff we had *resources* which did what ML references do, but that was not theoretically satisfying. However, it's clear that in essence the nature of references is some mix of algebraic effects and fresh name generation. Fresh name generation, however, is special and requires something extra. Of course, people have attacked this topic, but the final word is not in yet, in my opinion.  
> **username_3**: I think a good answer to this question would be to say how to show effects are *not* algebraic. I think continuations are not because of size issues, but are there any other examples?  
> **username_0**: What do you mean by "show effects"?  
> **username_1**: "How to show that effects are not algebraic."  

---

