将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

接下来我们可以继续实施.对于这一点,我将需要进口isNothing从Data.Maybe

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

因此,通过使用Maybe Int而不是Intfor findGoodMove,我们可以在类型系统级别编码该函数具有单一故障模式(即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,所以它使这种情况下很容易为好.