Can this be coded without using a mutable variable?

Question

Consider the following (very dull) game: - Player A thinks of a number between 1 and 100. - Player B is allowed 5 attempts to guess the number. Player A will respond to each guess as "too big", "too small" or "correct".

I wanted to simulate this in Haskell, which is trivial, of course. To make things interesting, though, I wanted to write the code in such a way that Player B can't "cheat". That means two things: - The Player B code isn't allowed to see the correct value of the secret number. The Player A code gives the Player B code a function with which to check its guesses. - The Player B code isn't allowed to call that function more than five times. Somehow, the Player A code has to keep count of how many times the function is called.

This is very easy to achieve in an OO language with private mutable variables.

In Haskell, I coded it using an IORef to keep count of the number of calls. That's fine, I think my solution is correct. But my question is:

"Can this be done in Haskell without IORef or similar? Is there a purely functional solution that I've missed?"

Here is my Haskell code:

import Data.IORef (newIORef, readIORef, writeIORef)
import System.Random (randomRIO)

lowest = 1
highest = 100
maxtries = 5

playerA :: IO (Int -> IO (Maybe Ordering))
playerA = do
    secret <- randomRIO (lowest, highest)
    print ("Secret", secret)
    tries <- newIORef maxtries
    return $ \ guess -> do
        t <- readIORef tries
        if t == 0 then
            return Nothing
        else do
            writeIORef tries $ t - 1
            return $ Just $ guess `compare` secret

playerB :: (Int -> IO (Maybe Ordering)) -> Int -> Int -> IO ()
playerB guessfunc lowbound highbound = do
    let guess = (lowbound + highbound) `div` 2
    response <- guessfunc guess
    print (lowbound, highbound, guess, response)
    case response of
        Just GT -> playerB guessfunc lowbound (guess - 1)
        Just LT -> playerB guessfunc (guess + 1) highbound
        Just EQ -> putStrLn "Player B wins"
        Nothing -> putStrLn "Player B loses"

main :: IO ()
main = do
    guessfunc <- playerA
    playerB guessfunc lowest highest

And what's not so purely functional about IORef?

bipll
– bipll

2018-01-24 12:29:27 +00:00
Commented Jan 24, 2018 at 12:29 — bipll
– bipll, Commented Jan 24, 2018 at 12:29

leftaroundabout · Accepted Answer · 2018-01-24 12:39:33Z

There's no need to do this in IO, you might as well use a pure state monad:

import Control.Monad.Trans.State
import System.Random (randomRIO)

maxtries = 5

playerA :: IO (Int -> State Int (Maybe Ordering))
playerA = do
   secret <- randomRIO (1,100)
   return $ \guess -> state $ \tries
          -> if tries < maxtries then (Just $ guess`compare`secret, tries+1)
                                 else (Nothing, tries)

playerB :: Monad m => (Int -> m (Maybe Ordering)) -> Int -> Int -> m (Maybe Int)
playerB guessfunc lowbound highbound = do
    let guess = (lowbound + highbound)`div`2
    response <- guessfunc guess
    case response of
        Just GT -> playerB guessfunc lowbound (guess - 1)
        Just LT -> playerB guessfunc (guess + 1) highbound
        Just EQ -> return $ Just guess
        Nothing -> return Nothing

main = do
   pa <- playerA
   print . (`evalState`0) $ playerB pa 1 100

Notice that playerB doesn't know the monad is State Int. That's important so she can't cheat by manipulating the state variable between calls to guessfunc.

bipll · Accepted Answer · 2018-01-24 12:36:12Z

0

Note that you're using IO for random generation and to keep track of attempts left. The number itself can be hidden inside a purest monadless function:

playerA :: Int -> Int -> Ordering
playerA = compare

This way, playerA 42 is an opaque (in terms of structure, not purity) object that returns Ordering when fed with a number, but you can never retrieve that 42 of it by any means described in the Report, without bruteforcing.

answered Jan 24, 2018 at 12:36

bipll

12k1 gold badge21 silver badges33 bronze badges

2 Comments

Daniel Wagner Over a year ago

Usually "brute force" means "try every possible input". But you can do much better here than that; e.g. binary search will recover 42 with only a couple dozen queries, far under the 2^(couple dozen) that brute force would need.

bipll Over a year ago

Sure, since we get more than a single bit for every attempt, rather the whole ordering.

Collectives™ on Stack Overflow

Can this be coded without using a mutable variable?

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related