number_guessing in Haskell

This program is inspired by Context Free’s Haskell solution, shown on Youtube:

Know what your functions are doing? - Side effects in 12+ languages (15:05 Haskell)

Compiling and Linting

Since number_guessing.hs does not use “special” modules, the compilation should be possible with the standard Haskell installation:

ghc --make -Wall number_guessing.hs

Lint:

hlint -s number_guessing.hs

Usage

Call number_guessing this way:

number_guessing [MIN-VAL] [MAX-VAL]

Examples:

number_guessing         # -> range:  1 .. 100 (default)
number_guessing 50      # -> range: 50 .. 100 (MAX-VAL is default)
number_guessing d  200  # -> range:  1 .. 200 (MIN-VAL is default)
number_guessing 10 150  # -> range: 10 .. 150

Example game session:

$ ./number_guessing 4 6
Guess a number between 4 and 6: x
I didn't understand 'x'
Guess a number between 4 and 6: 4
4 is too low
Guess a number between 4 and 6: 7
7 is too high
Guess a number between 4 and 6: 6
6 is too high
Guess a number between 4 and 6: 5
5 is the answer!
Finished in 5 guesses
Total input errors: 1
1 guess "too low"
2 guesses "too high"

The last three lines are output on stderr instead of stdout.

Implementation hints

readMaybe instead of exceptions

I don’t want to use exceptions for handling invalid inputs (i.e. inputs that are not numbers), because an exception is not visible at the signature of a function and therefore somewhat surprising.

The function readMaybe (of module Data.Maybe) does the job for us by taking a String and returning an Int or Nothing, if the String does not represent an Int value.

Data types

The number of invalid inputs shall be output on stderr at the end of the game. Therefore, we need a counter that is incremented for every invalid input.

Furthermore, the number of guesses shall be output on stdout at the end of the game. Instead of a related counter, we use a counter for the number of “too low” guesses and a counter for the number of “too high” guesses.

We do not need an extra counter for the overall number of guesses, because this value can be calculated with the sum of the counter values plus one.

These three counters build some kind of global state that is modified during and evaluated after the game session.

To simplify things a bit, we add the guessing range and the value, to be guessed, to the global state, although the guessing range and the value, to be guessed, will not be changed during a game session.

The GuessRange is a pair of Int with the lower limit of the range as first and the upper limit as second value.

The GameValue is a type alias for Guesses. It is used for the overall number of guesses.

type GuessRange = (Int, Int)
type Guesses    = Int
type GameValue  = Guesses

The GameState is a record type that holds the guessing range, the value, to be guessed, and the three counters, mentioned above.

data GameState =
  GameState
    { gsGuessRange :: GuessRange
    , gsGuessVal   :: Int
    , gsInvalidCnt :: Guesses
    , gsLowCnt     :: Guesses
    , gsHighCnt    :: Guesses
    }

Default guessing range

As already mentioned, the data type GuessRange holds the guessing range. The variable defaultGuessRange defines the default:

defaultGuessRange :: GuessRange
defaultGuessRange = (1, 100)

StateT IO monad transformer

We use a StateT IO monad transformer to make the GameState available for the functions that need access to GameState. A StateT IO monad transformer is used (instead of just a State monad), because the functions shall also be able to output a string on stdout or read a line from stdin, respectively.

See also Annex: States à la Haskell for some details, how states are handled in Haskell.

Function main

The main function is executed in the IO context (as usual). It evaluates the guessing range from the command line arguments (with function readGuessRange), creates a random number inside this range (which might also be the default guessing range 1 .. 100), and defines an initial game state with these values and all counters set to 0.

main :: IO ()
main = do
  args <- getArgs
  let guessRange = readGuessRange args
  guessVal <- randomRIO guessRange
  let initialGameState = GameState guessRange guessVal 0 0 0
  runStateT playGame initialGameState >>= printResult

Calling runStateT with the function playGame and the initial game state then returns a pair of GameValue and GameState inside the IO context, which allows us to “forward” this IO embellished pair to the function printResult, using the bind operator.

Function readGuessRange

The function readGuessRange takes a list of strings (the command line arguments) and returns the guessing range (a GuessRange type).

readGuessRange :: [String] -> GuessRange
readGuessRange = listToPair . fromMaybe [] . convert
  where
    listToPair :: [Int] -> GuessRange
    listToPair (x:y:_) = (x, y)
    listToPair (x:_)   = (x, snd defaultGuessRange)
    listToPair _       = defaultGuessRange
    convert :: [String] -> Maybe [Int]
    convert xs = zipWithM (<|>) (readMaybeInts xs) (Just <$> defRange)
    readMaybeInts :: [String] -> [Maybe Int]
    readMaybeInts = map readMaybe . take 2
    defRange = [fst defaultGuessRange, snd defaultGuessRange]

defRange is a list with two elements: the lower limit and the upper limit of the guessing range.

readMaybeInts is a (nested) function that takes the first two elements of the command line argument list and maps readMaybe over them, returning a list of Maybe Int.

The (nested) function convert holds two lists: the result of function readMaybeInts and the defRange list, where Just is mapped over both elements of defRange.

Both lists are “zipped” with the alternative operator <|>, which looks as follows (assuming that 20 and 80 are given via command line):

zipWith (<|>) [Just 20, Just 80] [Just 1, Just 100]

The result is a two-element list:

[Just 20 <|> Just 1, Just 80 <|> Just 100] = [Just 20, Just 80]

Applying the function sequence to this list of Maybe Int leads to a Maybe [Int]. sequence . zipWith can be replaced with zipWithM.

Therefore, function convert always returns a Just list (where the list might be empty):

>>> convert ["20", "80"]
Just [20,80]

>>> convert ["20", "y"]
Just [20,100]

>>> convert ["x", "80"]
Just [1,80]

>>> convert ["x", "y"]
Just [1,100]

>>> convert ["20"]
Just [20]

>>> convert ["x"]
Just [1]

>>> convert []
Just []

Function fromMaybe is an easy way to remove Just. The (nested) function listToPair takes the list of Int (which might be empty or might have only one element) and returns the guessing range (replacing missing elements with the default values).

So, this is, what function readGuessRange does:

>>> readGuessRange ["20", "80"]
(20,80)

>>> readGuessRange ["20", "y"]
(20,100)

>>> readGuessRange ["x", "80"]
(1,80)

>>> readGuessRange ["x", "y"]
(1,100)

>>> readGuessRange ["20"]
(20,100)

>>> readGuessRange ["x"]
(1,100)

>>> readGuessRange []
(1,100)

Function playGame

The function playGame is a StateT IO monad transformer (it returns StateT GameState IO GameValue). Therefore, the do notation is located “inside” the GameState context.

playGame :: StateT GameState IO GameValue
playGame = do
  guessRange <- gets gsGuessRange
  let (l, h) = bimap show show guessRange
  liftIO $ putStr $ mconcat ["Guess a number between ", l, " and ", h, ": "]
  liftIO $ hFlush stdout
  s <- liftIO getLine
  case readMaybe s of
    Nothing -> handleInvalid s
    Just n  -> handleValid   n

We need the guessing range here, which is an element of GameState. The function gets is used to read this value (of type GuessRange) out of GameState.

Since GameState is an (Int) pair and pairs are bifunctors, we can use function bimap here for an easy conversion to a pair of String.

To output the “Guess a number” message, we have to lift the IO context (using function liftIO) for the putStr function. Since the message is not terminated with an end of line, we have to hFlush the buffer to output the message on stdout. Reading a line from stdin (via function getLine) is then done with the same liftIO mechanism.

Function readMaybe tries to parse the input as an Int. In case of failure (no number entered), function handleInvalid is called (with the non-number string as argument), otherwise function handleValid (with the successfully parsed numerical value as argument).

Function handleInvalid

Like function playGame, function handleInvalid is a StateT IO monad transformer. It is called in case of an invalid (non-numerical) input, increments the counter for invalid inputs (gsInvalidCnt), which is an element of GameState, and outputs an “I did not understand” message on stdout with this non-numerical input.

handleInvalid :: String -> StateT GameState IO GameValue
handleInvalid s = do
  modify (\state -> state {gsInvalidCnt = gsInvalidCnt state + 1})
  liftIO $ putStrLn $ "I didn't understand '" <> s <> "'"
  playGame

Inside the do notation, function modify allows a direct incrementation of gsInvalidCnt as follows: The function modify is of the following type:

>>> :t modify
modify :: Control.Monad.State.Class.MonadState s m => (s -> s) -> m ()

modify expects a function from “old state to new state” and returns a unit (“inside” the state monad context). In handleInvalid, the expected function is a lambda abstraction that takes a state (the “old state”), gets the related value of gsInvalidCnt out of this state, and returns a state (the “new state”), where all values of the related GameState record type keep the same, except the gSInvalidCnt value, which is incremented.

The message output on stdout is realized with the already known liftIO mechanism.

Last, but not least, function handleInvalid calls function playGame, which is possible, since handleInvalid and playGame have the same return type. playGame may later call handleInvalid again; this alternate recursive calling (which is even tail recursive), is optimized internally by the compiler to a loop (or maybe even to a goto).

Function handleValid

Like function playGame and function handleInvalid, function handleValid is a StateT IO monad transformer and is called in case of a valid (numerical) input.

handleValid :: Int -> StateT GameState IO GameValue
handleValid n = do
  guessVal <- gets gsGuessVal
  case compare n guessVal of
    LT -> handleTooLow  n
    EQ -> handleGuessed
    GT -> handleTooHigh n

The function uses the gets function to read the guessing value out of GameState. Depending on the value, it calls the related handler function (which is quite self-explanatory).

Functions handleTooLow and handleTooHigh

The functions handleTooLow and handleTooHigh use the same handling as function handleInvalid to increment the related counters, to output a related message on stdout, and to call playGame in a recursive way. See description of function handleInvalid for details.

handleTooLow :: Int -> StateT GameState IO GameValue
handleTooLow n = do
  modify (\state -> state {gsLowCnt = gsLowCnt state + 1})
  liftIO $ putStrLn $ show n <> " is too low"
  playGame

handleTooHigh :: Int -> StateT GameState IO GameValue
handleTooHigh n = do
  modify (\state -> state {gsHighCnt = gsHighCnt state + 1})
  liftIO $ putStrLn $ show n <> " is too high"
  playGame

Function handleGuessed

The function handleGuessed is called, if the player has guessed the expected number correctly. It uses get to read the GameState record. It outputs a success message (with the correct value) on stdout and returns a GameValue type (i.e. it puts the value into the monadic context).

handleGuessed :: StateT GameState IO GameValue
handleGuessed = do
  gameState <- get
  liftIO $ putStrLn $ show (gsGuessVal gameState) <> " is the answer!"
  return $ 1 + sum ([gsInvalidCnt, gsLowCnt, gsHighCnt] <*> pure gameState)

The value, to be returned, is the sum of all counters plus 1, that is, the number of guesses. The sum of all counters could be calculated as follows, but it looks ugly because of gameState entered repeatedly:

gsInvalidCnt gameState + gsLowCnt gameState + gsHighCnt gameState

gsInvalidCnt, gsLowCnt, and gsHighCnt are all of type GameState -> Guesses (i.e. function from GameState to Guesses). Therefore, we put all these into a list: [gsInvalidCnt, gsLowCnt, gsHighCnt].

With pure, we put gameState into the list applicative context and use the <$> operator:

[gsInvalidCnt, gsLowCnt, gsHighCnt] <*> pure gameState

The result is a list, where gameState is applied to gsInvalidCnt, gsLowCnt, and gsHighCnt one after the other, which is exactly what we want.

If you don’t like invalid inputs to be counted as guesses, just remove gsInvalidCnt from the list [gsInvalidCnt, gsLowCnt, gsHighCnt].

Function printResult

The function printResult expects a pair of GameValue and GameState) and outputs the number of guesses on stdout. Furthermore, it outputs the counter values on stderr.

printResult :: (GameValue, GameState) -> IO ()
printResult (guesses, endState) = do
  putStrLn $ "Finished in " <> showGuesses guesses
  hPutStr stderr $
    unlines
      [ "Total input errors: "           <> show (gsInvalidCnt endState)
      , showGuesses (gsLowCnt  endState) <> " \"too low\""
      , showGuesses (gsHighCnt endState) <> " \"too high\""
      ]
  where
    showGuesses :: Guesses -> String
    showGuesses g = mconcat [show g, " guess", bool "es" "" (g == 1)]

As a detail, it outputs “guess” for a value of 1, otherwise “guesses” (to prevent ugly outputs like “Finished in 1 guesses”).

Annex: States à la Haskell

We need a state that is modified during and evaluated after the game session. How is this handled in Haskell?

A function stateFunc that has to deal with an argument of type a and additionally with the state of type s could get a and s as a pair of type (a,s) and return its result of type b together with the (possibly modified) state of the same type s also as a pair of type (b,s):

stateFunc :: (a,s) -> (b,s)

But this way we have to add s to the arguments of each function that depends on s, although s is somewhat “global”. Is there a better way instead of the pair boilerplate?

First of all, let us rewrite the function in a curried way like this (stateFunc'):

stateFunc' :: a -> (s -> (b,s))

The parentheses around s -> (b,s) are redundant, but now we see clearly that we have a function that takes an a and returns a function from s to a pair.

In fact, in Haskell State is defined as follows:

newtype State s b = State { runState :: (s -> (b,s)) }

Therefore, we can write our function stateFunc'' like so:

stateFunc'' :: a -> State s b

The function takes an a and returns a State s b, which is a function from s (our “global” state) to a pair that consists of the essential return value of type b and the (possibly modified) state of type s.

The return value is somewhat “embellished” with the state, or, in other words, it is available inside the State context. Watch that this context is a function.

To get the pair (b,s) out of this context, we have to execute the function. This is, what runState does. It has the following signature:

runState :: State s b -> s -> (b, s)

It takes a State s b (which is the function that runState shall execute) and an (initial) state s and returns a pair (b, s).

Let’s runState execute our function stateFunc'':

(y,endState) = runState (stateFunc'' x) initialState
\__________/            \_____________/ \__________/
   (b,s)                   State s b         s

x is a value of type a (what stateFunc'' expects as input), and y is the return value of type b (what stateFunc'' returns in an “embellished” way).

The initialState of type s is handled as a context (that is, stateFunc'' can access it without an explicit function argument needed), and endState (also of type s) is the state that might be modified by stateFunc'').

And, by the way, State is a monad, which allows us to use the do notation.