Evaluating implementation of Extended Euclidean algorithm

Question

After some experimentation and search, I came up with the following definition:

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

I'd evaluate emcd' 56 15 up to the innermost level, for example, as:

  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))

• Is my evaluation going in the right direction ?

EDIT:

From Will Ness's comments, I am updating the evaluation.

Answer 1

The general direction is correct but it contains the recursive calls which had already been performed and thus mustn't be there. Instead, it's

  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))

In what follows I derive the following pseudocode (where a where { ... } stands for 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) } } } } } 

The two indeed are equivalent, but it's more readable with the where pseudocode, I think.

---

Restructuring the definition a little bit, it becomes

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 } 

We then write, in pseudocode with where instead of let, using the basic cut-and-paste substitutions,

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 } } } } } 

and now we've hit the base case:

= (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)

Hopefully there's no cut-and-paste errors here. The general idea is just to make the straightforward substitutions in a purely mechanical manner.

_{side note: (g,t,s)=foo a b === g==gcd a b && g==t*a+s*b.}