评估扩展欧几里得算法的实现

Question

经过一些实验和搜索，我得出了以下定义：

emcd' :: Integer -> Integer -> (Integer,Integer,Integer)
emcd' a 0 = (a, 1, 0)
emcd' a b = 
let (g, t, s) = emcd' b r
in (g, s, t - (q * s))
where
(q, r) = divMod a b

我会将emcd' 56 15评估到最内层，例如：

emcd' 56 15 
= let (g, t, s) = emcd' 15 11 in (
let (g, t, s) = emcd' 11 4 in (
let (g, t, s) = emcd' 4 3 in (
let (g, t, s) = emcd' 3 1 in (
let (g, t, s) = emcd' 1 0 in (
(1, 1, 0)
) in (g, s, t - (3 * s))
) in (g, s, t - (1 * s))
) in (g, s, t - (2 * s))
) in (g, s, t - (1 * s))
) in (g, s, t - (3 * s))

• 我的评估方向正确吗

编辑：

根据Will Ness的评论，我正在更新评估。

Answer 1

一般方向是正确的，但它包含已经执行的递归调用，因此不能存在。相反，它是

emcd' 56 15 
= let (g, t, s) = (
let (g, t, s) = (
let (g, t, s) = (
let (g, t, s) = (
let (g, t, s) = (
(1, 1, 0)
) in (g, s, t - (3 * s))
) in (g, s, t - (1 * s))
) in (g, s, t - (2 * s))
) in (g, s, t - (1 * s))
) in (g, s, t - (3 * s))

在下面的内容中，我导出了以下伪代码(其中a where { ... }代表let { ... } in a(：

= (g, s, t-(3*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = (g, s, t-(2*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = (g, s, t-(3*s))
where { (g, t, s) = (1, 1, 0) } } } } } 

这两者确实是等价的，但我认为使用where伪代码更可读。

---

稍微重组一下定义，它就变成了

foo a 0 = (a, 1, 0)
foo a b = (g, s, t-(q*s))
where { (q, r) = divMod a b 
; (g, t, s) = foo b r } 

然后，我们用where而不是let编写伪代码，使用基本的剪切和粘贴替换，

foo 56 15
= (g, s, t-(q*s))
where { (a, b) = (56, 15)      --
; (q, r) = divMod a b
; (g, t, s) = foo b r }
= (g, s, t-(q*s))
where { (q, r) = divMod 56 15    --
; (g, t, s) = foo 15 r }
= (g, s, t-(q*s))
where { (q, r) = (3, 11)           --
; (g, t, s) = foo 15 r }
= (g, s, t-(3*s))
where { (g, t, s) = foo 15 11 }      --
= (g, s, t-(3*s))
where { (g, t, s) = (g, s, t-(q*s))
where { (a, b) = (15, 11)             --
; (q, r) = divMod a b
; (g, t, s) = foo b r } } 
= (g, s, t-(3*s))
where { (g, t, s) = (g, s, t-(q*s))
where { (q, r) = divMod 15 11
; (g, t, s) = foo 11 r } } 
= (g, s, t-(3*s))
where { (g, t, s) = (g, s, t-(q*s))
where { (q, r) = (1, 4)
; (g, t, s) = foo 11 r } }  
= (g, s, t-(3*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = foo 11 4 } }  
= (g, s, t-(3*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = (g, s, t-(q*s))
where { (a, b) = (11, 4)
; (q, r) = divMod a b
; (g, t, s) = foo b r } } } 
= (g, s, t-(3*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = (g, s, t-(q*s))
where { (q, r) = divMod 11 4
; (g, t, s) = foo 4 r } } } 
= (g, s, t-(3*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = (g, s, t-(q*s))
where { (q, r) = (2, 3)
; (g, t, s) = foo 4 r } } } 
= (g, s, t-(3*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = (g, s, t-(2*s))
where { (g, t, s) = foo 4 3 } } } 
= (g, s, t-(3*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = (g, s, t-(2*s))
where { (g, t, s) = (g, s, t-(q*s))
where { (a, b) = (4, 3)
; (q, r) = divMod a b
; (g, t, s) = foo b r } } } } 
= (g, s, t-(3*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = (g, s, t-(2*s))
where { (g, t, s) = (g, s, t-(q*s))
where { (q, r) = divMod 4 3
; (g, t, s) = foo 3 r } } } } 
= (g, s, t-(3*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = (g, s, t-(2*s))
where { (g, t, s) = (g, s, t-(q*s))
where { (q, r) = (1, 1)
; (g, t, s) = foo 3 r } } } } 
= (g, s, t-(3*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = (g, s, t-(2*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = foo 3 1 } } } } 
= (g, s, t-(3*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = (g, s, t-(2*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = (g, s, t-(q*s))
where { (a, b) = (3, 1)
; (q, r) = divMod a b
; (g, t, s) = foo b r } } } } } 
= (g, s, t-(3*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = (g, s, t-(2*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = (g, s, t-(q*s))
where { (q, r) = divMod 3 1
; (g, t, s) = foo 1 r } } } } } 
= (g, s, t-(3*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = (g, s, t-(2*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = (g, s, t-(q*s))
where { (q, r) = (3, 0)
; (g, t, s) = foo 1 r } } } } } 
= (g, s, t-(3*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = (g, s, t-(2*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = (g, s, t-(3*s))
where { (g, t, s) = foo 1 0 } } } } } 

现在我们已经触及了基本情况：

= (g, s, t-(3*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = (g, s, t-(2*s))
where { (g, t, s) = (g, s, t-(1*s))
where { (g, t, s) = (g, s, t-(3*s))
where { (g, t, s) = (1, 1, 0) } } } } } 
= (1, s, t-(3*s))
where { (t, s) = (s, t-(1*s))
where { (t, s) = (s, t-(2*s))
where { (t, s) = (s, t-(1*s))
where { (t, s) = (0, 1-(3*0)) } } } } 
= (1, s, t-(3*s))
where { (t, s) = (s, t-(1*s))
where { (t, s) = (s, t-(2*s))
where { (t, s) = (1, 0-(1*1)) } } } 
= (1, s, t-(3*s))
where { (t, s) = (s, t-(1*s))
where { (t, s) = (-1, 1-(2*(-1))) } } 
= (1, s, t-(3*s))
where { (t, s) = (3, (-1)-(1*3)) } 
= (1, (-4), 3-(3*(-4)))
= (1, (-4), 15)

希望这里没有剪切粘贴错误。一般的想法只是以纯粹的机械方式进行简单的替换。

_{旁注：(g,t,s)=foo a b==g==gcd a b && g==t*a+s*b}