0

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

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 的评论，我正在更新评估。

4

1 回答 1

0

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

  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。

于 2021-12-13T21:09:31.283 回答