[Agda] strange termination check

Sergei Meshveliani mechvel at botik.ru
Thu Oct 10 19:57:36 CEST 2013


Please, why the below  powerToPos  is not checked as terminating ?


{-# OPTIONS --termination-depth=3 #-}
module Report where
open import Level    using () renaming (zero to 0ℓ)
open import Function using (case_of_)
open import Relation.Binary 
            using (module Setoid; module IsEquivalence;_Preserves_⟶_)
open import Relation.Binary.PropositionalEquality using (_≡_)
open import Algebra    using (Semigroup; module Semigroup)
open import Data.Empty using (⊥)
open import Data.List  using ([]; _∷_)
open import Data.Fin   using (Fin) renaming (zero to 0b; suc to sucB)
open import Data.Digit using (Bit)
open import Data.Bin   using (Bin⁺)
          
1b : Bit
1b = sucB 0b

postulate H : Semigroup 0ℓ 0ℓ

open Semigroup H using (setoid; _≈_; _∙_)
                       renaming (Carrier to C; isEquivalence to ≈equiv)
open IsEquivalence ≈equiv using ()
                 renaming (refl to ≈refl; sym to ≈sym; trans to ≈trans)

HasLast1 : Bin⁺ → Set       -- "is the bit list of a non-zero binary"
HasLast1 []           =  ⊥
HasLast1 (b ∷ [])     =  b ≡ 1b
HasLast1 (_ ∷ b ∷ bs) =  HasLast1 (b ∷ bs)

powerToPos : C → (bs : Bin⁺) → HasLast1 bs → C
powerToPos _ []            ()
powerToPos x (1b ∷ [])     _             =  x
powerToPos x (b ∷ b' ∷ bs) last1-b:b':bs =
                           case b of \ { 0b              → p ∙ p
                                       ; (sucB 0b)       → x ∙ (p ∙ p)
                                       ; (sucB (sucB ()))
                                       }
                           where
                           last1-b':bs : HasLast1 (b' ∷ bs)
                           last1-b':bs = last1-b:b':bs

                           p = powerToPos x (b' ∷ bs) last1-b':bs
----------------------------------------------------------------------------

The recursion     (b ∷ b' ∷ bs)  -->  (b' ∷ bs)  

by the second argument is well-founded. Why does not the checker see the
termination proof? 

Thanks,

------
Sergei





More information about the Agda mailing list