haskell modulus primitive recursion

Question

I'm trying to create a modulus function within haskell using primtive recursive functions. I know it's possible (because it's on the list of example functions on wikipedia)

And I know how i'd logically do it too.. But I just can't implement it!

IE, the logic is (not primtive recursion or haskell)

function mod(a, b){
  while(a > b)
    a -= b
  return a;
}

Which I can define using recursion (again not haskel)

function mod(a, b){
  if(a < b) return a;
  return mod(a - b, b);
} 

But I just can't seem to implement it using primitive recursive functions. I bit which I can't do is the logic of a < b

I think to really solve my problem I need some sort of defined logic such as (again not haskel)

reduce(a, b)
    = a >= b -> a-b 
    otherwise x

If anyone could help me with any part of this i'd really appreciate it, thanks

Edit:: I thought of potentially defining a modulus function making use of dividing, ie mod(a, b) = a - (a/b) * b, but since my primitive recursive function for divide relies on modulo I can't do it haha

Answer 1

Take a look at this for some pointers: http://www.proofwiki.org/wiki/Quotient_and_Remainder_are_Primitive_Recursive

Also note that the wikipedia definition is somewhat narrow. Any function built up by induction over a single finite data structure is primitive recursive, though it takes a bit to show that this translates into the tools given in wikipedia. And note that we can represent the naturals in the classic peano style. You don't have to do this of course, but it makes reasoning about induction much more natural. See the agda wiki for a citation of this notion of primitive recursion: http://wiki.portal.chalmers.se/agda/pmwiki.php?n=ReferenceManual.Totality#Primitiverecursion

The following page also has what I think is a somewhat clearer exposition of primitive recursion: http://plato.stanford.edu/entries/recursive-functions/#1.3