将C代码转换为Haskell

发布时间：2020-12-16 10:34:51 所属栏目：百科来源：网络整理

导读：我正在尝试将这段代码转换为 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(i

我正在尝试将这段代码转换为 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

因此,通过使用Maybe Int而不是Int for findGoodMove,我们可以在类型系统级别编码,此函数具有单一故障模式(即NO_GOOD_MOVE),我认为这会使意图更加清晰并确保我们不会意外地对待NO_GOOD_MOVE标志作为我们代码中其他地方的有效值.

对于循环部分,我已经定义了一个本地称为循环的递归函数,从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,因此它也使这个案例变得简单.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!