## Effects.jl

Like a kick in the monads
Author MikeInnes
Popularity
25 Stars
Updated Last
1 Year Ago
Started In
February 2020

# Effects

```] add IRTools#master

An implementation of effect handlers in Julia (aka algebraic effects, free monads etc). Effects can be used for a lot of things (continuations, exceptions, coroutines, backtracking ...). This package aims to provide a way to define effects generally, as well as important examples.

[Caveat Emptor: Julia's compiler is not designed to handle this kind of code and reserves the right to complain / be slow. Also, while everything theoretically composes nicely, this is not thoroughly tested.]

The list monad allows you to write functions as if they return a single result, while actually returning all possible results.

```julia> list() do
choose(1:3)
end
3-element Array{Int64,1}:
1
2
3

julia> list() do
(choose(1:3), choose(1:3))
end
9-element Array{Tuple{Int64,Int64},1}:
(1, 1)
(1, 2)
(1, 3)
(2, 1)
(2, 2)
...```

You can think of `choose(xs)` as being like `rand(xs)` as `backtrack()` like `error()`. A program written like this will either one of a set of valid results, or error out. `list()` gives you the whole set in one go.

Find some Pythagorean triples:

```julia> list() do
N = 20
i = choose(1:N)
j = choose(i:N)
k = choose(j:N)
i^2 + j^2 == k^2 || backtrack()
(i, j, k)
end
6-element Array{Any,1}:
(3, 4, 5)
(5, 12, 13)
...```

This works with control flow etc. For example, we can solve the N-queens problem as follows:

```julia> function nqueens(n)
ps = @Persistent []
for i = 1:n
next = choose(1:n)
next in ps && backtrack() # same row
any(abs(next-p) == (i-i′) for (i′, p) in enumerate(ps)) && backtrack() # same diagonal
ps = push(ps, next)
end
return ps
end

julia> list(() -> nqueens(8))
92-element Array{Any,1}:
[1, 5, 8, 6, 3, 7, 2, 4]
[1, 6, 8, 3, 7, 4, 2, 5]
[1, 7, 4, 6, 8, 2, 5, 3]
...```

## Define a handler

```julia> using Effects

julia> struct Flip end

julia> flip() = effect(Flip())

julia> function binary(f)
@effect begin
f()
(e::Flip, k) -> max(k(true), k(false))
end
end

julia> binary() do
x = flip() ? 10 : 15
y = flip() ? 5  : 10
x-y
end
10```