[Agda] Termination checker on commutative functions

Jacek Karwowski jac.karwowski at gmail.com
Thu Oct 31 01:59:18 CET 2019


Hi,

I'm trying to write a commutative function over some type, and not repeat
the code in the process.

The toy example is as follows:
```
module _ where

open import Data.Nat

data Int : {i : Size} -> Set where
  Pos : (x : ℕ) -> Int
  Neg : (x : ℕ) -> Int

_⊕_ : Int -> Int -> Int
Pos x ⊕ Pos y = Pos (x + y)
Neg x ⊕ Neg y = Neg (x + y)
Pos x ⊕ Neg zero = Pos x
Pos zero ⊕ Neg y = Neg y
Pos (suc x) ⊕ Neg (suc y) = (Pos x) ⊕ (Neg y)
--- problematic call
Neg x ⊕ Pos y = (Pos y) ⊕ (Neg x)
```
In the example above, termination checker complains about the last call,
since it is not a structural recursion.

(Of course, real types can (and do) have more than two constructors, the
constructors are recursive, etc.)

The naive, manual way I see would be to introduce an explicit order on the
constructors by some external function, and then call ⊕ passing this
parameter over:

```
ord : Int -> ℕ
ord (Pos _) = 0
ord (Neg _) = 1

_⊕_ : {s : ℕ} -> (x : Int) -> {s ≡ ord x} -> Int -> Int
Pos x ⊕ Pos y = Pos (x + y)
Neg x ⊕ Neg y = Neg (x + y)
Pos x ⊕ Neg zero = Pos x
Pos zero ⊕ Neg y = Neg y
Pos (suc x) ⊕ Neg (suc y) = _⊕_ {zero} (Pos x) {refl} (Neg y)
--- problematic call
_⊕_ {suc zero} (Neg x) (Pos y) = _⊕_ {zero} (Pos y) {refl} (Neg x)
```
but this ends up being very ugly and hard to read.

What is the idiomatic way of handling these types of situations,
introducing as little code overhead as possible?

Thanks,
Jacek
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.chalmers.se/pipermail/agda/attachments/20191030/50fe01c8/attachment.html>


More information about the Agda mailing list