用Haskell函数实现最大公约数函数

我会尝试这样的东西(伪代码)

mygcd a b = finalize (until endState nextState (a,b))
   where
   finalize (x,y)  = ...
   endState (x,y)  = some condition here
   nextState (x,y) = (x',y') computed in some way using mod

mygcd a b = until (==0) (`mod` (a b)) b

> :t until
until :: (a -> Bool) -> (a -> a) -> a -> a

所以我们有了谓词 (==0) ,我们的职能 (`mod`(a b)) ,以及起始值 b 然而,我的第一个问题是:在谓词为真之前,它不会终止,所以它只能生成0。这说明了什么?我们也看到 a 一定是那种 Integral a => a -> a 因为它适用于 B 得到一些我们可以用的东西 b `mod` x .重复这个过程不会产生不同的结果,所以表达式要么立即生成0,要么在1之后生成0 mod ,或者永远不会结束。

我想,从中得到一些有用的东西 until ,您需要一个比等式检查更复杂的谓词。也许你会问“13比100的最小倍数是多少”,或者你可能会问 A. 一个元组并检查其中的一部分。在我看来有点像:

until p f v = head (dropWhile (not . p) (iterate f v))