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))
EDIT:
From Will Ness's comments, I am updating the evaluation.
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.