[Agda] termination problem

mechvel at scico.botik.ru mechvel at scico.botik.ru
Sat Oct 3 21:32:12 CEST 2020


Dear Agda developers,

There is a certain particular effect in termination check in Agda-2.6.1.

-- Sum of two monomial lists. For the same exponents the coefficients 
are summed by
-- _+_. If e > e', then the first head monomial is put ahead.
-- It is almost same as merging lists.

_+ms_ : Op₂ (List Mon)
[]                  +ms mons'                 =  mons'
mons                +ms []                    =  mons
((monᶜ a e) ∷ mons) +ms ((monᶜ b e') ∷ mons') =  with <-cmp e e'
...
     | tri> _ _ _ =  (monᶜ a e)  ∷ (mons +ms ((monᶜ b e') ∷ mons'))
... | tri< _ _ _ =  (monᶜ b e') ∷ (((monᶜ a e) ∷ mons) +ms mons')
... | tri≈ _ _ _ =  (monᶜ (a + b) e) ∷ (mons +ms mons')

On the right hand side, +ms is applied to the two lists, and at least 
one of these lists
is a tail of the corresponding argument on the left hand side.

Agda reports of unproved termination.
All right, this is a known effect. One has to introduce a counter as an 
additional argument.

Instead I try another version for the last sentence:

((monᶜ a e) ∷ mons) +ms ((monᶜ b e') ∷ mons') =
   with <-cmp e e' | (monᶜ b e') ∷ (((monᶜ a e) ∷ mons) +ms mons')   -- I
                   | (monᶜ (a + b) e) ∷ (mons +ms mons')             -- 
II
                   | (monᶜ a e) ∷ (mons +ms ((monᶜ b e') ∷ mons'))   -- 
III
... | tri< _ _ _ | xs | _  | _  = xs
... | tri≈ _ _ _ | _  | ys | _  = ys
... | tri> _ _ _ | _  | _  | zs = zs

And it is type-checked.

1) Can you, please, comment this?
2) For a good performance, only a single term among {I, II, II} needs to 
be computed.
    Will this be so?

Thanks,

------
Sergei



More information about the Agda mailing list