[Agda] simple example
Serge D. Mechveliani
mechvel at botik.ru
Wed Aug 15 13:08:30 CEST 2012
People,
can you, please, answer a couple of beginner questions?
The function rem needs to evaluate the remainder of division of
natural numbers n by m by repeatedly subtracting m from the current
remainder.
The restriction IsPositive m is also processed.
The cost optimizations are ignored.
It uses Standard Library 0.6.
Math symbols used: \bn, \.-
---------------------------------------------------------
module MyLib where
open import Foreign.Haskell
open import IO.Primitive
open import Data.Bool as Bool
open import Data.Nat as Nat hiding (less)
open import Prelude using (toCostring)
less : Б└∙ -> Б└∙ -> Bool -- \bn for Nat
less zero zero = false
less zero (suc _) = true
less (suc _) zero = false
less (suc n) (suc m) = less n m
IsPositive : Б└∙ -> Set
IsPositive zero = T false
IsPositive (suc _) = T true
rem : Б└∙ -> (m : Б└∙) -> IsPositive m -> Б└∙
rem zero _ _ = zero
rem (suc n) (suc k) p = if less n k then suc n
else rem (n Б┬╦ k) (suc k) p
-- \.- for subtraction on Nat
rem _ zero () -- unaccessible
main : IO Unit
main = putStrLn (toCostring "done")
---------------------------------------------------------
1. If I skip the last sentence in rem, the compiler reports
... Missing cases: rem (suc _) zero _ ...
Why cannot it derive from `IsPositive m' the fact that m = zero
is not possible?
2. For the initial program, the compiler reports
Termination checking failed for the following functions: rem
Problematic calls: rem (n Б┬╦ k) (suc k) p
-- \.- for subtraction
How to fix this?
May be, one needs to provide a proof for n Б┬╦ k < n ?
(\.- for subtraction)
(if so, in what form can it be provided?).
May be, Standard library already has such a proof, and it can be
somehow imported?
3. It is natural to rely on the library.
What and how need I to use here from Standard Library 0.6 instead
of the above definitions for less and IsPositive ?
Thank you in advance for explanation,
------
Sergei
More information about the Agda
mailing list