CODEWITHSUNDEEP
c++haskell
Minar Ashiq Tishan
Minar Ashiq Tishan

Reputation: 312

Translate C++ code to Haskell

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.

Upvotes: 3

Views: 432

Answers (3)

Ray
Ray

Reputation: 1667

Instead of defining the loop function as in @bheklilr 's answer, you can use a list comprehension, which is a powerful tool in the Haskell language. Then you can use pattern matching to take the right choice of 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 won't be fully constructed. It will stop once it found the first valid nTaken. So the time complexity of function findGoodMove is the same as the C++ version.

Upvotes: 0

bheklilr
bheklilr

Reputation: 54068

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.

Upvotes: 11

Ashalynd
Ashalynd

Reputation: 12573

Something like this?

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

Upvotes: 2

Related Questions