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.
CodePudding user response：
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:
= (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 look equivalent, but it's more readable with the where clauses, 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.