[Agda] signature for `with' branch

Sergei Meshveliani mechvel at botik.ru
Tue Feb 28 12:49:23 CET 2017


On Tue, 2017-02-28 at 11:26 +0100, Nils Anders Danielsson wrote:
> On 2017-02-27 21:38, Sergei Meshveliani wrote:
> > when I expect that there the result for  (add a (x ∷ xs))  must be
> > a ∷ x ∷ xs.
> 
> The term "add a (x ∷ xs)" reduces to "aux (a ≟ 0) (x ∷ xs)", which is
> stuck, because "a ≟ 0" does not reduce to WHNF.
> 
> [..]


I knew that it is not reduced. But how to make it reduced there without
using `with' or `case' ?

Generally, the matter is that I do not discover any regular and uniform
way to set Agda proofs for simple statements when a proof is based on
considering cases.   
I always know a simple naive proof, but often fail to convert it to an
Agda proof, because some terms do not want to reduce along the branches.
Mostly, "with | inspect" works, but not always.  

I attach the code again, because it has missed the mail list.

Thanks,

------
Sergei
-------------- next part --------------
open import Relation.Nullary using (yes; no; ¬_; Dec)
open import Relation.Binary  using (DecSetoid; DecTotalOrder; Tri; 
                                                       StrictTotalOrder)
open import Relation.Binary.PropositionalEquality as PE using (_≡_; _≢_)
open import Data.Empty    using (⊥-elim)
open import Data.List     using (List; []; _∷_; map)
open import Data.List.All using (All) renaming ([] to []a; _∷_ to _∷a_)
open import Data.Nat      using (ℕ; suc; _+_; _<_; _>_)
open import Data.Nat.Properties using (≤-decTotalOrder; strictTotalOrder) 

decSetoid = DecTotalOrder.Eq.decSetoid ≤-decTotalOrder
open DecSetoid        decSetoid        using (_≟_)
open StrictTotalOrder strictTotalOrder using (compare) 
open Tri

postulate anything : ∀ {a} {A : Set a} → A 


add : ℕ → List ℕ → List ℕ 
add a xs =  aux (a ≟ 0) xs 
  where
  aux : Dec (a ≡ 0) → List ℕ → List ℕ   
  aux (yes _)  xs       =  xs
  aux (no _)   []       =  a ∷ []
  aux (no a≢0) (x ∷ xs) =  aux0 (compare a x) 
                           where
                           aux0 : Tri (a < x) (a ≡ x) (a > x) → List ℕ 
                           aux0 (tri> _ _ _) =  a ∷ x ∷ xs 
                           aux0 (tri≈ _ _ _) =  (a + x) ∷ xs
                           aux0 (tri< _ _ _) =  x ∷ (aux (no a≢0) xs)


lemma :  ∀ a xs → a ≢ 0 → All (_≢ 0) xs → All (_≢ 0) (add a xs) 

lemma _ []       _   _             =  anything
lemma a (x ∷ xs) a≢0 (x≢0 ∷a xs≢0) =  aux (a ≟ 0)
  where
  aux :  Dec (a ≡ 0) → All (_≢ 0) (add a (x ∷ xs)) 

  aux (yes a≡0) = ⊥-elim (a≢0 a≡0)
  aux (no a≢0)  = aux0 (compare a x) 
      where
      aux0 :  Tri (a < x) (a ≡ x) (a > x) → All (_≢ 0) (add a (x ∷ xs)) 
      aux0 (tri> _ _ _) = 
                          -- add a (x ∷ xs) --> a ∷ x ∷ xs,
                          -- so that   (a≢0 ∷a x≢0 ∷a xs≢0)  is a proof
                   aux1 (a ≟ 0)
                   where
                   aux1 : Dec (a ≡ 0) → All (_≢ 0) (add a (x ∷ xs)) 
                   aux1 (no _)    = a≢0 ∷a x≢0 ∷a xs≢0
                   aux1 (yes a≡0) = ⊥-elim (a≢0 a≡0)

      aux0 (tri≈ _ _ _) = anything   
      aux0 (tri< _ _ _) = anything   




More information about the Agda mailing list