[Agda] Divergence in inference with constructor-headed functions
Brandon Moore
brandon_m_moore at yahoo.com
Wed Jul 27 21:05:51 CEST 2011
Hello
In 2.2.10 the following code seems to cause typechecking
to diverge.
\begin{code}
f : ℕ → Set
f zero = ⊤
f (suc n) = ℕ × f n
enum : (n : ℕ) → f n
enum zero = tt
enum (suc n) = n , enum n
n : ℕ
n = _
test : f n
test = enum (suc n)
\end{code}
This typechecks quickly if the definition
of test is changed to
test = enum n
(If you previously tried to typecheck the code again, the *ghci*
process will still be stuck, and must be killed or interrupted first)
I think the problem is that the body has type ℕ × f n,
and unifying it with the expected type f n invokes the
constructor-headed function specialization to resolve
n to suc n', and the process repeats.
Here is the module header and self-contained definitions
for the code above
\begin{code}
module infbad where
data ⊤ : Set where
tt : ⊤
data ℕ : Set where
zero : ℕ
suc : ℕ → ℕ
data _×_ (A B : Set) : Set where
_,_ : A → B → A × B
\end{code}
Brandon
More information about the Agda
mailing list