Total definition of Gcd in Idris

Question

I am working in a small project with a goal to give a definition of Gcd which gives the gcd of two numbers along with the proof that the result is correct. But I am unable to give a total definition of Gcd. The definition of Gcd in Idris 1.3.0 is total but uses assert_total to force totality which defeats the purpose of my project. Does someone have a total definition of Gcd which does not use assert_total?

P.S. - My codes are uploaded in https://github.com/anotherArka/Idris-Number-Theory.git

Answer 1

I have a version which uses the Accessible relation to show that the sum of the two numbers you're finding the gcd of gets smaller on every recursive call: https://gist.github.com/edwinb/1907723fbcfce2fde43a380b1faa3d2c#file-gcd-idr-L25

It relies on this, from Prelude.Wellfounded:

data Accessible : (rel : a -> a -> Type) -> (x : a) -> Type where
     Access : (rec : (y : a) -> rel y x -> Accessible rel y) ->
              Accessible rel x

The general idea is that you can make a recursive call by explicitly stating what gets smaller, and providing a proof on each recursive call that it really does get smaller. For gcd, it looks like this (gcdt for the total version since gcd is in the prelude):

gcdt : Nat -> Nat -> Nat
gcdt m n with (sizeAccessible (m + n))
  gcdt m Z | acc = m
  gcdt Z n | acc = n
  gcdt (S m) (S n) | (Access rec)
     = if m > n
          then gcdt (minus m n) (S n) | rec _ (minusSmaller_1 _ _)
          else gcdt (S m) (minus n m) | rec _ (minusSmaller_2 _ _)

sizeAccessible is defined in the prelude and allows you to explicitly state here that it's the sum of the inputs that's getting smaller. The recursive call is smaller than the input because rec is an argument of Access rec.

If you want to see in a bit more detail what's going on, you can try replacing the minusSmaller_1 and minusSmaller_2 calls with holes, to see what you have to prove:

gcdt : Nat -> Nat -> Nat
gcdt m n with (sizeAccessible (m + n))
  gcdt m Z | acc = m
  gcdt Z n | acc = n
  gcdt (S m) (S n) | (Access rec)
     = if m > n
          then gcdt (minus m n) (S n) | rec _ ?smaller1
          else gcdt (S m) (minus n m) | rec _ ?smaller2

For example:

*gcd> :t smaller1
  m : Nat
  n : Nat
  rec : (y : Nat) ->
        LTE (S y) (S (plus m (S n))) -> Accessible Smaller y
--------------------------------------
smaller1 : LTE (S (plus (minus m n) (S n))) (S (plus m (S n)))

I don't know of anywhere that documents Accessible in much detail, at least for Idris (you might find examples for Coq), but there are more examples in the base libraries in Data.List.Views, Data.Vect.Views and Data.Nat.Views.