[Agda] `with' in standard functions

Sergei Meshveliani mechvel at botik.ru
Sun Sep 24 13:46:32 CEST 2017


People,

There is a certain problem with user proofs for Standard library
functions that use `with' or `case_of_'.  
If a function is written without `with' (`with' replaced with calling an
auxiliary function  aux, and this  aux  is exported from the module),  
then it is much easier to compose various new proofs about it.

But the user cannot change implementation for a standard function. 

For example,  Data.Bin  implements 

-------------------------
fromBits : List Bit → Bin
fromBits []        = 0#
fromBits (b  ∷ bs) with fromBits bs
fromBits (b  ∷ bs) | bs′ 1# = (b ∷ bs′) 1#
fromBits (0b ∷ bs) | 0#     = 0#
fromBits (1b ∷ bs) | 0#     = [] 1#
fromBits (⊥b ∷ bs) | _
-------------------------

I need to prove 

          fromBits-bs++1 :  fromBits ∘ (_∷ʳ 1b) ≗ _1#

And find it difficult.
Then I get free of `with', and a proof becomes plain and easy to
compose:

--------------------------------------------------
fromBits-aux : Bit → List Bit → Bin → Bin    -- needs to be exported

fromBits-aux b  bs (bs' 1#) = (b ∷ bs') 1#
fromBits-aux 0b bs 0#       = 0#
fromBits-aux 1b bs 0#       = [] 1#
fromBits-aux ⊥b bs _

fromBits' : List Bit → Bin
fromBits' []       = 0#
fromBits' (b ∷ bs) = fromBits-aux b bs (fromBits' bs)


fromBits-bs++1 :  fromBits' ∘ (_∷ʳ 1b) ≗ _1#
fromBits-bs++1 []       =  refl
fromBits-bs++1 (b ∷ bs) =
  begin
    fromBits' (b ∷ (bs ∷ʳ 1b))                        ≡⟨ refl ⟩
    fromBits-aux b (bs ∷ʳ 1b) (fromBits' (bs ∷ʳ 1b))
       	       	       	       	    ≡⟨ cong (fromBits-aux b (bs ∷ʳ 1b))
                                            (fromBits-bs++1 bs)
                                     ⟩
    fromBits-aux b (bs ∷ʳ 1b) (bs 1#)  	       	      ≡⟨ refl ⟩
    (b ∷ bs) 1#
  ∎
---------------------------------------------------

Please, what is a way out?

Thanks,

------
Sergei




More information about the Agda mailing list