除了 is_zero、succ 和 pred 之外,不使用任何辅助函数,是否可以在单次递归过程中将分数化简为最低形式?
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?
除了 is_zero
、succ
和 pred
之外,是否可以在单次递归传递中将分数化简为最低形式?例如,如果我们想以这种方式实现 gcd,我们可以这样写:
// 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))
注意这个函数是如何直接递归的,除了is_zero、succ和pred之外没有使用任何辅助函数。不过,它确实需要一个额外的参数来存储结果。它也是尾递归的,但这不是必需的。我的问题是:是否可以这样做,但是 reduce_fraction
?
// reduce_fraction(a, b, ...) returns a pair
// with the `a/b` fraction in the lowest form
function reduce_fraction(a, b, ...):
...
请注意,不允许使用 GCD 实现 reduce_fraction
:
function reduce_fraction(a,b):
return (a / gcd(a,b), b / gcd(a,b))
因为reduce_fraction
会调用2个辅助函数(gcd
和/
),这是定义允许的不。它必须是仅使用 is_zero
、succ
和 pred
.
的直接递归
我正在专门寻找一种解决方案来减少 space 使用(辅助参数的数量)和使用的时间(总递归步骤)。
我们可以编写一个简单的函数来模仿您拥有的相同 gcd
结构,但是 returns 简化形式的分数:
-- 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)
“啊!”,你大叫,“但是那使用了一个名为 +
的辅助函数!”!好的没问题;我们将使用评论中描述的“模式”技巧。模式0是gcd计算;方式1为加法运算
-- 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_zero
、succ
和 pred
之外,是否可以在单次递归传递中将分数化简为最低形式?例如,如果我们想以这种方式实现 gcd,我们可以这样写:
// 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))
注意这个函数是如何直接递归的,除了is_zero、succ和pred之外没有使用任何辅助函数。不过,它确实需要一个额外的参数来存储结果。它也是尾递归的,但这不是必需的。我的问题是:是否可以这样做,但是 reduce_fraction
?
// reduce_fraction(a, b, ...) returns a pair
// with the `a/b` fraction in the lowest form
function reduce_fraction(a, b, ...):
...
请注意,不允许使用 GCD 实现 reduce_fraction
:
function reduce_fraction(a,b):
return (a / gcd(a,b), b / gcd(a,b))
因为reduce_fraction
会调用2个辅助函数(gcd
和/
),这是定义允许的不。它必须是仅使用 is_zero
、succ
和 pred
.
我正在专门寻找一种解决方案来减少 space 使用(辅助参数的数量)和使用的时间(总递归步骤)。
我们可以编写一个简单的函数来模仿您拥有的相同 gcd
结构,但是 returns 简化形式的分数:
-- 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)
“啊!”,你大叫,“但是那使用了一个名为 +
的辅助函数!”!好的没问题;我们将使用评论中描述的“模式”技巧。模式0是gcd计算;方式1为加法运算
-- 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