[Agda] record with proof
Serge D. Mechveliani
mechvel at botik.ru
Sun Aug 26 23:07:24 CEST 2012
On Fri, Aug 24, 2012 at 11:29:45PM +0400, Serge D. Mechveliani wrote:
> [..]
> I am trying to understand usage of Agda by programming the division
> remainder for natural numbers (of Nat -- Б└∙).
> (This is under Agda-2.3.0.1 + Standard library lib-0.6).
> So far, I ignore Data.Nat.DivMod, because it is rather difficult to
> understand, and I try to begin with a simpler, home-made approach.
>
> remainder n m, m > 0, is found by repeated subtraction of m from the
> current remainder.
> 1. remNat finds the remainder all right.
> It uses an auxiliary function rem which processes an additional
> argument for the counter - the number of subtractions applied.
> The counter is used in order to make a termination proof trivial.
>
> 2. remNatP is a variant of remNat with producing a proof for
> "remainder < m".
> Its idea is to provide a recursive proof together with a recursive
> evaluation of the remainder. As there are the two result values, I
> introduce the record Rem m with the two fields. The second field is
> for a proof, its type depends on m and on the value of the remainder
> field r.
> And remNatP is not compiled. I wonder, what is wrong there?
>
> [..]
It looks like I have fixed it. See below remBySuc.
--------------------------------------------------------------------
module IntResidue where
open import Data.Nat as Nat renaming ( _Б┴╓_ to _NБ┴╓_; _Б┴╓?_ to _NБ┴╓?_ )
-- Remainder of division of n by (suc m)
record Rem (m : Б└∙) : Set where
field r : Б└∙ -- remainer by suc m
boundProof : r NБ┴╓ m
remBySuc : Б└∙ -> (m : Б└∙) -> Rem m
remBySuc n m = rem n n
where -- below m' is a constant subtrahend
m' = suc m
rem : Б└∙ -> Б└∙ -> Rem m -- н╩ n counter -> remainder by m'
rem 0 _ = record{ r = 0; boundProof = zБ┴╓n }
rem _ 0 = record{ r = 0; boundProof = zБ┴╓n }
-- accessible only for m = 0
rem n (suc cnt) with n NБ┴╓? m
... | yes p = record{ r = n; boundProof = p }
... | _ = rem (n Б┬╦ m') cnt
--------------------------------------------------------------------
Is it all right?
Trying to use it:
--------------------------------------------------------------
module Foo where
open import Foreign.Haskell
open import IO.Primitive
open import Data.String as String
open import Data.Nat as Nat
open import Data.Nat.Show
open import Prelude using (toCostring) -- by F. Kettelhoit
open import IntResidue -- my lib
remRes : Rem 3
remRes = remBySuc 14 3 -- remainder by 4
rm : Б└∙
rm = remRes.r
main : IO Unit
main = putStrLn (toCostring (show rm))
------------------------------------------------------
The compiler compiles IntResidue,
and for Foo, it reports
Not in scope:
remRes.r
I wonder: how to take the r field in remRes ?
I tried
(Rem 3).r
-- because the Guide says that if r is a field in a record RR, then
RR.r is a function (value) r in a module RR related to the record
RR.
But the compiler rejects this `(Rem 3).r'
Please, how to fix this?
Thanks,
------
Sergei
More information about the Agda
mailing list