Haskell中的递归和无限循环问题

8mmmxcuj  于 6个月前  发布在  其他
关注(0)|答案(3)|浏览(51)

我在Haskell中有三个函数,它们都是基于初始猜测进行n次迭代的。
1.

squareRootTwo :: Double -> Integer -> Double
squareRootTwo guess n
| n == 0 = guess
| otherwise = squareRootTwo ((guess + 2/guess) / 2) (n-1)

字符串
1.

squareRootTwoA :: Double -> Integer -> Double
squareRootTwoA guess n
| n == 0 = guess
| otherwise = squareRootTwoA ((guess + 2/guess) / 2) (n-1) where n=n


1.

squareRootTwoB :: Double -> Integer -> Double
squareRootTwoB guess n
| n == 0 = guess
| otherwise = let n = n-1 in squareRootTwoB ((guess + 2/guess) / 2) n


第一个函数(squareRootTwo)工作正常。在ghci中:

ghci> squareRootTwo 1.0 5   
1.414213562373095

ghci> squareRootTwoA 1.0 5
No response
ghci> squareRootTwoB 1.0 5
No response


但是第二个和第三个函数根本不起作用。它们只是死机。我不得不在VS Code终端中按下(c + c)来停止它。现在,我明白了也许它正在创建一个递归,福尔斯陷入了无限循环。但是,我不明白它是如何创建无限循环的。因为这两个程序的编写方式,对我来说,它似乎没有创建无限循环。
由于我是Haskell的新手,我只是不明白为什么会发生这种情况。

kulphzqa

kulphzqa1#

您的定义相当于以下内容:

squareRootTwoA :: Double -> Integer -> Double
squareRootTwoA guess n
  | blurb == 0  = guess
  | otherwise   = squareRootTwoA ((guess + 2/guess) / 2) (blurb-1)
 where blurb = blurb

squareRootTwoB :: Double -> Integer -> Double
squareRootTwoB guess n
  | n == 0     = guess
  | otherwise  = let blurb = blurb-1
                 in squareRootTwoB ((guess + 2/guess) / 2) blurb

字符串
你可以看到,在递归调用中的整数参数在两种情况下都与原始值n没有任何关系,它是一个全新的变量,只是碰巧具有相同的名称和 * 阴影 * 旧的n。像n = n-1这样的定义当然是循环的,这是一个不可能实现的等式(当其他语言将其作为语句执行时,它们在数学上对您撒谎)。
实现您所尝试的方法是显式地给予新版本一个不同的名称:

squareRootTwoA :: Double -> Integer -> Double
squareRootTwoA guess n
  | n == 0     = guess
  | otherwise  = squareRootTwoA ((guess + 2/guess) / 2) (n'-1)
 where n' = n

squareRootTwoB :: Double -> Integer -> Double
squareRootTwoB guess n
  | n == 0     = guess
  | otherwise  = let n' = n-1
                 in squareRootTwoB ((guess + 2/guess) / 2) n'

hiz5n14c

hiz5n14c2#

squareRootTwo guess n = squareRootTwo (...) (...)squareRootTwo的递归定义:它在等号的左边和右边都提到了相同的名字。n=n-1n的递归定义,原因相同。这里有一个红色的鲱鱼:你已经选择在一个已经存在一个名为n的值的地方写方程n=n-1。这个现有的值被完全忽略,这一事实本身就可以解释你的困惑。但如果不是,请继续阅读。
现在,递归并不总是一个问题--递归方程通常有一个很好的解;例如,你给出了squareRootTwo方程的一个可能的右侧,尽管是递归的,但它仍然可以正常工作。但是我希望清楚为什么n=n-1是一个有问题的递归定义:n没有一个好的值可以满足这个方程。结果是,如果你问n的值,它 * 必须 * 无限循环,而不是返回一个具体的值。
方程n=n也是有问题的,尽管它的原因肯定不那么明显。简而言之,n可能有 * 太多 * 好的值,而且没有好的方法在它们之间进行选择。所以它无限循环。
(In一般来说,如果无限循环是递归方程的有效解,那么它就是Haskell选择的解!)

utugiqy6

utugiqy63#

问题出在n=nn = n-1上:在这两个定义中,等号两边的n是同一个,所以它们变成了无限循环(什么是“n”?哦,它等于“n”。但是那个“n”是什么?哦,它等于“n”。等等,直到无穷大。)
解决第一种情况的方法是完全删除where n=n部分,解决第二种情况的方法是使用新名称:n' = n - 1,然后在函数体的其余部分使用n'。

相关问题