Translate C ++ code to Haskell
I am trying to translate this piece of C ++ code into haskell but cannot fool it. This is taken from nim.cpp at 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 am stuck on the for loop part. I would really like some suggestions on how to translate it to haskell.
Thanks in advance.
source to share
First of all, I would use the richer Haskell system for coding to fail in findGoodMove
by specifying its type
findGoodMove :: Int -> Maybe Int
And isBadPosition
may be of type
isBadPosition :: Int -> Bool
Next, we can move on to the implementation. For this I need to import isNothing
fromData.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 for Maybe Int
instead , we can encode at the system level that this function has a single failure mode (i.e. ), which I would say makes the intent more clear and ensures that we cannot accidentally treat the flag as a valid value elsewhere in our code.Int
findGoodMove
NO_GOOD_MOVE
NO_GOOD_MOVE
For the loop part, I have defined a recursive function, locally called loop
, that starts with 1
and has 3 branches. If it nTaken
reaches our maximum value for moves, we hit the end of our loop and return Nothing
( NO_GOOD_MOVE
). If this is a condition False
, then checking nCoins - nTaken
is a bad position and if we return Just nTaken
. If none of these conditions were True
met, we loop again with nTaken + 1
.
For isBadPosition
we know that if nCoins == 1
, it is True
, so we can use pattern matching to handle this simple case. Otherwise, we need to know findGoodMove nCoins
if it succeeds , and it will succeed if it fails Nothing
. The function Data.Maybe.isNothing
is useful here to quickly check if it's there Nothing
or Just something
, so it makes this case easy too.
source to share
Something like that?
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
source to share
Instead of defining a function loop
as in @ bheklilr's answer, you can use a description, which is a powerful tool in Haskell. Then you can use pattern matching to pick the right one 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
Since Haskell is lazy. The list choices
will not be fully built. It will stop as soon as it finds the first valid one nTaken
. So the time complexity of the function findGoodMove
is the same as the C ++ version.
source to share