Generic programming via effects : <p>In the Idris <a href="https://github.com/idris-lang/Idris-dev/blob/master/libs/effects/Effects.idr" rel="noreferrer">Effects</a> library effects are represented as</p>

<pre><code>||| This type is parameterised by:
||| + The return type of the computation.
||| + The input resource.
||| + The computation to run on the resource given the return value.
Effect : Type
Effect = (x : Type) -&gt; Type -&gt; (x -&gt; Type) -&gt; Type
</code></pre>

<p>If we allow resources to be values and swap the first two arguments, we get (the rest of the code is in Agda)</p>

<pre><code>Effect : Set -&gt; Set
Effect R = R -&gt; (A : Set) -&gt; (A -&gt; R) -&gt; Set
</code></pre>

<p>Having some basic type-context-membership machinery</p>

<pre><code>data Type : Set where
  nat : Type
  _⇒_ : Type -&gt; Type -&gt; Type

data Con : Set where
  ε   : Con
  _▻_ : Con -&gt; Type -&gt; Con

data _∈_ σ : Con -&gt; Set where
  vz  : ∀ {Γ}   -&gt; σ ∈ Γ ▻ σ
  vs_ : ∀ {Γ τ} -&gt; σ ∈ Γ     -&gt; σ ∈ Γ ▻ τ
</code></pre>

<p>we can encode lambda terms constructors as follows:</p>

<pre><code>app-arg : Bool -&gt; Type -&gt; Type -&gt; Type
app-arg b σ τ = if b then σ ⇒ τ else σ

data TermE : Effect (Con × Type) where
  Var   : ∀ {Γ σ  } -&gt; σ ∈ Γ -&gt; TermE (Γ , σ     )  ⊥     λ()
  Lam   : ∀ {Γ σ τ} -&gt;          TermE (Γ , σ ⇒ τ )  ⊤    (λ _ -&gt; Γ ▻ σ , τ            )
  App   : ∀ {Γ σ τ} -&gt;          TermE (Γ , τ     )  Bool (λ b -&gt; Γ     , app-arg b σ τ)
</code></pre>

<p>In <code>TermE i r i′</code> <code>i</code> is an output index (e.g. lambda abstractions (<code>Lam</code>) construct function types (<code>σ ⇒ τ</code>) (for ease of description I'll ignore that indices also contain contexts besides types)), <code>r</code> represents a number of inductive positions (<code>Var</code> doesn't (<code>⊥</code>) receive any <code>TermE</code>, <code>Lam</code> receives one (<code>⊤</code>), <code>App</code> receives two (<code>Bool</code>) — a function and its argument) and <code>i′</code> computes an index at each inductive position (e.g. the index at the first inductive position of <code>App</code> is <code>σ ⇒ τ</code> and the index at the second is <code>σ</code>, i.e. we can apply a function to a value only if the type of the first argument of the function equals the type of the value).</p>

<p>To construct a real lambda term we must tie the knot using something like a <a href="https://github.com/agda/agda-stdlib/blob/master/src/Data/W.agda" rel="noreferrer"><code>W</code></a> data type. Here is the definition:</p>

<pre><code>data Wer {R} (Ψ : Effect R) : Effect R where
  call : ∀ {r A r′ B r′′} -&gt; Ψ r A r′ -&gt; (∀ x -&gt; Wer Ψ (r′ x) B r′′) -&gt; Wer Ψ r B r′′
</code></pre>

<p>It's the indexed variant of the Oleg Kiselyov's <a href="http://okmij.org/ftp/Haskell/extensible/more.pdf" rel="noreferrer"><code>Freer</code></a> monad (effects stuff again), but without <code>return</code>. Using this we can recover the usual constructors:</p>

<pre><code>_&lt;∨&gt;_ : ∀ {B : Bool -&gt; Set} -&gt; B true -&gt; B false -&gt; ∀ b -&gt; B b
(x &lt;∨&gt; y) true  = x
(x &lt;∨&gt; y) false = y

_⊢_ : Con -&gt; Type -&gt; Set
Γ ⊢ σ = Wer TermE (Γ , σ) ⊥ λ()

var : ∀ {Γ σ} -&gt; σ ∈ Γ -&gt; Γ ⊢ σ
var v = call (Var v) λ()

ƛ_ : ∀ {Γ σ τ} -&gt; Γ ▻ σ ⊢ τ -&gt; Γ ⊢ σ ⇒ τ
ƛ b = call Lam (const b)

_·_ : ∀ {Γ σ τ} -&gt; Γ ⊢ σ ⇒ τ -&gt; Γ ⊢ σ -&gt; Γ ⊢ τ
f · x = call App (f &lt;∨&gt; x)
</code></pre>

<p>The whole encoding is very similar to the <a href="https://github.com/effectfully/DataData/blob/master/Container/Indexed.agda#L75" rel="noreferrer">corresponding encoding</a> in terms of <a href="http://strictlypositive.org/indexed-containers.pdf" rel="noreferrer">indexed containers</a>: <code>Effect</code> corresponds to <code>IContainer</code> and <code>Wer</code> corresponds to <code>ITree</code> (the type of Petersson-Synek Trees). However the above encoding looks simpler to me, because you don't need to think about things you have to put into shapes to be able to recover indices at inductive positions. Instead, you have everything in one place and the encoding process is really straightforward.</p>

<p>So what am I doing here? Is there some real relation to the indexed containers approach (besides the fact that this encoding has the same <a href="http://mazzo.li/epilogue/index.html%3Fp=324.html" rel="noreferrer">extensionality problems</a>)? Can we do something useful this way? One natural thought is to built an effectful lambda calculus as we can freely mix lambda terms with effects, since a lambda term is itself just an effect, but it's an external effect and we either need other effects to be external as well (which means that we can't say something like <code>tell (var vz)</code>, because <code>var vz</code> is not a value — it's a computation) or we need to somehow internalize this effect and the whole effects machinery (which means I don't know what).</p>

<p><a href="https://github.com/effectfully/random-stuff/blob/master/Wer.agda" rel="noreferrer">The code used</a>.</p>
