c++ - 将 C++ 代码翻译成 Haskell

Question

我正在尝试将这段 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 的建议。

提前致谢。

Answer 1

首先，我会使用 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，因此它也使这种情况变得简单。