Translate C++ code to Haskell

Question

I am trying to translate this piece of c++ code to haskell but can't really get my head around it. This is taken from the nim.cpp in 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;
}

so far i have done in 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

i'm stuck in the for loop part. I would really like some suggestions on how do i translate it to haskell.

Thanks in advance.

Answer 1

First of all, I would use Haskell's richer type system to encode for failure in findGoodMove, by giving it the type

findGoodMove :: Int -> Maybe Int

And isBadPosition can have the type

isBadPosition :: Int -> Bool

Next we can move on to implementation. For this, I'm going to need to import isNothing from 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

So by using Maybe Int instead of Int for findGoodMove, we can encode at the type system level that this function has a single failure mode (i.e. NO_GOOD_MOVE), which I would argue makes the intent more clear and ensures that we can't accidentally treat the NO_GOOD_MOVE flag as a valid value elsewhere in our code.

For the loop portion, I've defined a recursive function locally called loop that starts at 1, and has 3 branches. If nTaken reaches our max value for moves, we've hit the end of our loop and return Nothing (NO_GOOD_MOVE). If that condition is False, we then check of nCoins - nTaken is a bad position, and if it is we return Just nTaken. If neither of these conditions were True, then we perform the loop again with nTaken + 1.

For isBadPosition, we know that if nCoins == 1, it's True, so we can use pattern matching to handle that simple case. Otherwise, we have to know if findGoodMove nCoins succeeds, and it only succeeds if it's not Nothing. The Data.Maybe.isNothing function is helpful here to quickly check if it's Nothing or Just something, so it makes this case easy as well.