[Agda] Re: double constructor termination
Sergei Meshveliani
mechvel at botik.ru
Mon May 2 12:21:05 CEST 2016
Jesper, thank you.
Such an unexpected power of `let' !
Dear Agda developers, can `where' be improved so that to support
termination similarly as `let' does in this example?
------
Sergei
On Mon, 2016-05-02 at 12:07 +0200, Jesper Cockx wrote:
> One solution is to use 'let' instead of 'where':
>
> lemma : ∀ n → n ≤ n + 1
> lemma 0 = z≤n
> lemma 1 = s≤s z≤n
> lemma (suc (suc n)) =
> let n'≤n'+1 = lemma (suc n)
> in s≤s n'≤n'+1
>
>
> I'm not sure why Agda accepts the let-version, but not the
> where-version, though.
>
>
> cheers,
>
> Jesper
>
>
>
> On Mon, May 2, 2016 at 11:47 AM, Sergei Meshveliani <mechvel at botik.ru>
> wrote:
> Hi,
>
> Can people advise, please, on the following subject?
> The below program can be rewritten with removing a double
> `suc' pattern.
> But let it be a contrived example:
>
>
------------------------------------------------------------------
> open import Relation.Binary.PropositionalEquality as PE using
> (_≡_)
> open import Data.Nat using (ℕ; suc; _+_; _≤_; pred)
>
> open _≤_
>
> lemma : ∀ n → n ≤ n + 1
> lemma 0 = z≤n
> lemma 1 = s≤s z≤n
> lemma (suc (suc n)) = s≤s n'≤n'+1 where
> n'≤n'+1 = lemma (suc n)
>
------------------------------------------------------------------
>
> Agda does not see termination here.
> What is the nicest way to prove termination with preserving
> this suc-suc
> pattern?
> I write it this way:
>
> --------------------------------
> lemma n = aux n (pred n) PE.refl
> where
> aux : (n m : ℕ) → m ≡ pred n → n ≤ n + 1
> aux 0 _ _ = z≤n
> aux 1 _ _ = s≤s z≤n
> aux (suc (suc n)) 0 ()
> aux (suc (suc n)) (suc m) m'≡pred-n'' = s≤s n'≤n'+1
> where
> m≡pred-n' = PE.cong pred
> m'≡pred-n''
> n'≤n'+1 = aux (suc n) m
> m≡pred-n'
> ---------------------------------
>
> And it looks awkward.
>
> Thanks,
>
> ------
> Sergei
>
>
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda
>
>
More information about the Agda
mailing list