Is it possible to reduce a fraction to the lowest form in a single recursive pass, using no auxiliary functions other than is_zero, succ and pred?

Question

Is it possible to reduce a fraction to the lowest form, in a single recursive pass, using no auxiliary function other than is_zero, succ and pred? As an example, if we wanted to implement gcd that way, we could write it as follows:

// gcd(a, b, c) returns the greatest common divisor of `a+c` and `b+c`
function gcd(a, b, c)
  if is_zero(a):
    if is_zero(b):
      c
    else:
      gcd(c, b, 0)
  else:
    if is_zero(b):
      gcd(a, c, 0)
    else:
      gcd(pred(a), pred(b), succ(c))

Notice how this function is a direct recursion that does not use any auxiliary function other than is_zero, succ and pred. It does require one extra argument, though, which stores the result. It is also tail-recursive, but that isn't a demand. My question is: is it possible to do the same, but for reduce_fraction?

// reduce_fraction(a, b, ...) returns a pair 
// with the `a/b` fraction in the lowest form
function reduce_fraction(a, b, ...):
  ...

Note that using GCD to implement reduce_fraction isn't allowed:

function reduce_fraction(a,b):
  return (a / gcd(a,b), b / gcd(a,b))

Because reduce_fraction would call 2 auxiliary functions (gcd and /), which is not allowed by definition. It must be a direct recursion using only is_zero, succ and pred.

I'm specifically looking for a solution that reduces the space used (number of auxiliary arguments) and time used (total recursive steps).

user_791604 · Answer

We can write a straightforward function that mimics the same gcd structure you have, but which returns the fraction in reduced form:

-- redBad n d delta reduces the fraction (n+delta)/(d+delta)
redBad 0 0 delta = (1, 1)
redBad 0 d delta = case redBad delta d 0 of
    (n', d') -> (n', n'+d')
redBad n 0 delta = case redBad n delta 0 of
    (n', d') -> (n'+d', d')
redBad n d delta = redBad (n-1) (d-1) (delta+1)

"Ah!", you shout, "but that uses an auxiliary function named +"! Okay, no problem; we'll use the "mode" trick described in the comments. Mode 0 is the gcd calculation; mode 1 is the addition calculation.

-- redGood n d delta 0 reduces the fraction (n+delta)/(d+delta)
-- redGood n d delta 1 produces the fraction (n+delta)/d
redGood 0 0 delta 0 = (1, 1)
redGood 0 d delta 0 = case redGood delta d 0 0 of
    (n', d') -> case redGood d' n' n' 1 of
        (d'', n'') -> (n'', d'')
redGood n 0 delta 0 = case redGood n delta 0 0 of
    (n', d') -> redGood n' d' d' 1
redGood n d delta 0 = redGood (n-1) (d-1) (delta+1) 0
redGood n d 0 mode = (n, d)
redGood n d delta mode = redGood (n+1) d (delta-1) mode

Is it possible to reduce a fraction to the lowest form in a single recursive pass, using no auxiliary functions other than is_zero, succ and pred?

1 Answers