将C++代码翻译成Haskell

Question

我将尝试将这段C++代码翻译成Haskell，但实际上我无法理解它。这段代码来自nim.cpp文件，该文件可以在 http://cs.stanford.edu/people/eroberts/courses/cs106b/chapters/07-backtracking-algorithms.pdf 中找到。

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的建议。

提前感谢您。

- Minar Ashiq Tishan

Answer 1

首先，在findGoodMove中，我会使用Haskell更丰富的类型系统来编码错误处理，给它赋予以下类型：

首先，在findGoodMove中，我会使用Haskell更丰富的类型系统来编码错误处理，给它赋予以下类型：

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。如果这些条件都不成立，则我们使用nTaken + 1再次执行循环。

对于isBadPosition，我们知道如果nCoins == 1，它是True，所以我们可以使用模式匹配来处理这种简单情况。否则，我们必须知道findGoodMove nCoins是否成功，它仅在它不是Nothing时成功。在这里，Data.Maybe.isNothing函数非常有用，可以快速检查它是否为Nothing或Just something，因此也很容易处理这种情况。

- bheklilr

Answer 2

像这样吗？

max_move = 3
no_good_move = -1

findGoodMove nCoins = findGoodMoveStep nCoins 1

findGoodMoveStep nCoins nTaken = if nTaken> max_move
                        then no_good_move
                        else if isBadPosition (nCoins - nTaken) == True
                        then nTaken
                        else findGoodMoveStep nCoins nTaken+1


isBadPosition nCoins = if nCoins == 1
                        then True
                        else findGoodMove(nCoins) == no_good_move

- Ashalynd

---

啊，好的，我更熟悉Scala，所以不知道那个。 - Ashalynd

这更像是“音译”而不是翻译。至少是一个好的起点。 - luqui

谢谢。我认为在“else findGoodMove nCoins nTaken+1”中，您的意思是findGoodMoveStep... - Minar Ashiq Tishan

Answer 3

不必像 @bheklilr 的回答中那样定义 loop 函数，你可以使用 列表推导式，这是 Haskell 语言中的一个强大工具。然后你可以使用模式匹配来选择正确的 nTaken。

maxMove :: Int
maxMove = 3

findGoodMove :: Int -> Maybe Int
findGoodMove nCoins =
  let choices = [nTaken | nTaken <- [1..maxMove], isBadPosition (nCoins - nTaken)]
  in case choices of
    [] -> Nothing
    (nTaken:_) -> Just nTaken

isBadPosition :: Int -> Bool
isBadPosition 1 = True
isBadPosition nCoins = findGoodMove nCoins == Nothing

由于Haskell是惰性的，列表choices不会完全构建。它会在找到第一个有效的nTaken后停止。因此，函数findGoodMove的时间复杂度与C++版本相同。

- Ray