我正在尝试将这段 C++ 代码转换为 haskell,但我无法真正理解它。这取自 http://cs.stanford.edu/people/eroberts/courses/cs106b/chapters/07-backtracking-algorithms.pdf 中的 nim.cpp。 .
C++:
const int MAX_MOVE = 3;
const int NO_GOOD_MOVE = -1;
int FindGoodMove(int nCoins) {
for (int nTaken = 1; nTaken <= MAX_MOVE; nTaken++) {
if (IsBadPosition(nCoins - nTaken)) return nTaken;
}
return NO_GOOD_MOVE;
}
bool IsBadPosition(int nCoins) {
if (nCoins == 1) return true;
return FindGoodMove(nCoins) == NO_GOOD_MOVE;
}
到目前为止,我已经在 haskell 中完成了:
findGoodMove nCoins = if isBadPosition (nCoins - nTaken) == True
then nTaken
else -1
where nTaken = 1
isBadPosition nCoins = if nCoins == 1
then True
else findGoodMove(nCoins) == -1
我卡在 for 循环部分了。我真的很想得到一些关于如何将它翻译成 haskell 的建议。
提前致谢。
最佳答案
首先,我会使用 Haskell 更丰富的类型系统来为 findGoodMove
中的失败进行编码,方法是给它类型
findGoodMove :: Int -> Maybe Int
isBadPosition
可以有类型
isBadPosition :: Int -> Bool
接下来我们可以继续实现。为此,我需要从 Data.Maybe
isNothing
import Data.Maybe
maxMove :: Int
maxMove = 3
findGoodMove :: Int -> Maybe Int
findGoodMove nCoins = loop 1
where
loop nTaken
| nTaken == maxMove = Nothing
| isBadPosition (nCoins - nTaken) = Just nTaken
| otherwise = loop (nTaken + 1)
isBadPosition :: Int -> Bool
isBadPosition 1 = True
isBadPosition nCoins = isNothing $ findGoodMove nCoins
因此,通过为 findGoodMove
使用 Maybe Int
而不是 Int
,我们可以在类型系统级别编码此函数有一个单一的失败模式(即 NO_GOOD_MOVE
),我认为这使意图更加清晰,并确保我们不会意外地将 NO_GOOD_MOVE
标志视为我们代码中其他地方的有效值。
对于循环部分,我在本地定义了一个称为loop
的递归函数,它从1
开始,有3 个分支。如果 nTaken
达到了我们的移动最大值,我们就到达了循环的末尾并返回 Nothing
(NO_GOOD_MOVE
)。如果该条件为 False
,则我们检查 nCoins - nTaken
是否为错误位置,如果是,我们返回 Just nTaken
。如果这两个条件都不为 True
,那么我们将使用 nTaken + 1
再次执行循环。
对于 isBadPosition
,我们知道如果 nCoins == 1
,则为 True
,因此我们可以使用模式匹配来处理这种简单情况.否则,我们必须知道 findGoodMove nCoins
是否成功,只有当它不是 Nothing
时它才会成功。 Data.Maybe.isNothing
函数在这里有助于快速检查它是 Nothing
还是 Just something
,因此它也使这种情况变得简单。
关于c++ - 将 C++ 代码翻译成 Haskell,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25098894/