Now that I'm comfortable with the simpler monads like Maybe and List, I challenged myself to redo a small coding challenge I saw a few month ago using haskell and the State monad.
Constraints and objectives
The challenge boils down to make authenticated requests to an http api and collect the data which form a tree. The leaves of the tree ultimately form a string. There are a few tricks there, but the main one is that the auth token is valid only for 10 requests. This is an excellent exercice to practice the following:
- Make HTTP requests (with custom headers)
- Parse JSON response
- Keep track of a state between requests (the token)
Getting Started
For the cabal file:
build-depends: base >=4.8 && <4.9,
bytestring,
text,
vector,
mtl >= 2.2.1 && <3,
containers >= 0.5.6.3,
lens >= 4.5,
aeson >= 0.7.0.3,
lens-aeson,
wreq-sb >= 0.4 && < 0.5,
transformers
I went for http://www.serpentine.com/wreq/tutorial.html to make http requests. It's a simple and complete library. The other important dependency is the mtl to get the State monad.
The state monad
The star of the post. In Haskell, functions are pure which means they don't have side effects and their output is only a function of their input (no access to outside state/variables). Of course, sometimes, carrying a state between computation is required. Although this information could be embedded as an additional parameter, it quickly become cumbersome, and it makes composition of functions more difficult. As usual in Haskell, monads provide an elegant solution to this problem.
The state monad is usually introduced as:
newtype State s a = State { runState :: s -> (a, s) }
This was very confusing for me. The key is to see that it's just a wrapper around a function of type s -> (a, s). The next difficulty is how to construct such object. There are two methods. One which directly uses a constructor:
initialState :: State String a
initialState = state (\s -> compute s) -- or state compute
Another method is to use the do notation:
initialState :: State String a
initialState = do
state <- get
let (result, nextState) = compute state
put nextState
return result
get is provided by the State monad, and allow one to retrieve the internal state. compute here is just a pure function (which needs to have type String -> (a, String)). put set the internal state and return set the result of the computation.
From this monad, to extract the result, one has to use runState:
λ: :type runState
runState :: State s a -> s -> (a, s)
So for example:
let (result, nextState) = runState initialState "foo"
Dealing with impure functions
In my case, the function to compute the next state involve making an http request, and this is impure. That's where monad transformers come into play. They allow one monad to be executed in the context of another monad. In my case, I had to use StateT s IO a which means a function with the signature s -> IO (a, s). This special monad can transform its state.
The code
First, some type aliases:
type Id = String
type Result = String
type Session = (Int, BI.ByteString)
type CrawlState = ([Id], Session)
The core function embedded into the state monad:
queryApi :: ([Id], Session) -> IO (Maybe Result, ([Id], Session))
queryApi ([], session) = return (Nothing, ([], session))
queryApi (currentId:nextIds, session) = do
(body, newSess) <- liftIO $ fetchNext currentId session
let nextTargets = extractIds body
let res = extractResult body
return (res, (nextTargets ++ nextIds, newSess))
Note the liftIO here, which means the given action has to be executed in the IO context. This is valid here because the transformer is IO.
The next step is to use this function into a State monad and pass it around until I got all the info from the api. This is the gather function:
gather :: StateT CrawlState IO (Maybe Result) -> CrawlState
-> IO ([Maybe Result], CrawlState)
gather mState s = do
(res, newState@(ids, _)) <- runStateT mState s
case ids of
[] -> return ([res], newState)
_ -> do
(nextResults, nextState) <- gather mState newState
return (res : nextResults, nextState)
runStateT is the equivalent of runState and allow to retrieve the result and the new state from the compution embedded inside the monad. Then, depending on the new state (is there more stuff to fetch?), I'm either done or I recurse with the new updated state.
The main function is very simple:
main :: IO ()
main = do
initialSession <- newSession
let initialState = (["start"], initialSession)
(results, _) <- gather (S.StateT queryApi) initialState
putStrLn $ show $ concat . catMaybes $ results
The full code is on github.
Conclusion
This was an interesting exercise, although I'm pretty sure it would be easier to just pass the state as function argument here. This was also a neat opportunity to do network requests, as a web dev, it's my bread and butter and it feels more practical than most abstract exercises from books I've read.
This post also uses the StateT monad (combined with the list monad) in a very clever way, and is well worth the read.