[Agda] mutual recursion on vectors?
Kenichi Asai
asai at is.ocha.ac.jp
Sun Jun 21 08:05:17 CEST 2015
One can easily write a function that recurse over a natural number:
f1 : ℕ → ℕ
f1 zero = zero
f1 (suc x) = f1 x
Given an argument m, it returns zero after m recursive calls. For two
argument function, one can define:
mutual
f2a : ℕ → ℕ → ℕ
f2a zero zero = zero
f2a zero (suc y) = f2b zero y
f2a (suc x) y = f2a x y
f2b : ℕ → ℕ → ℕ
f2b zero zero = zero
f2b (suc x) zero = f2a x zero
f2b x (suc y) = f2b x y
where f2a is called recursively when its first argument decreases
(with the second argument unchanged), and f2b is called recursively
when its second argument decreases (with the first argument unchanged).
Given arguments m1 and m2, it returns zero after m1+m2 recursive calls.
Can I generalize this to n argument case?
fn : {n : ℕ} → (index : Fin n) → Vec ℕ n → ℕ
fn {n} index v = {!!}
Namely, given an index and a vector of n numbers, it defines n
functions mutually recursively. fn i will be called recursively when
its ith argument decreases (with all the other arguments unchanged).
Given a vector of n numbers, m0, ..., m_{n-1}, it returns zero after
m0 + ... + m_{n-1} recursive calls.
It appears I can define it by adding an extra argument keeping the
sum of all the numbers. But then I lose the mutual recursive
structure: even if sum is not zero, I don't know which of the n
numbers is non zero, and even I have to have the case where all the
numbers are zero, which can't happen if sum is zero.
Sincerely,
--
Kenichi Asai
More information about the Agda
mailing list