Using the state in a let in a do block in Haskell

The whole point of the State monad is to automatically pass states around, without you having to do that explicitly. Almost no function should get s as argument, or return it.

For instance,

let m' = getFresh m s

is suspicious, it should probably read

m' <- getFresh m

where we would have getFresh :: String -> State [String] String.

The whole code should then read as

       do l' <- freshNodesS l
          m' <- getFresh m
          r' <- freshNodesS r
          return (BNode l' m' r')

Note how no s or s' is ever mentioned. This should look like imperative code, where a mutable state variable is modified by each function call, even if the code does not mention that explicitly.

Now, in getFresh you will have to deal with the states, since there’s no way around that. If your State monad is the standard one, you can access the state with get and put. You probably need something like

getFresh :: String -> State [String] String
getFresh m = do
   s <- get          -- read the current state
   let m' = ...      -- compute a fresh name m'
   let s' = m' : s   -- mark m' as used
   put s'            -- write the current state
   return m'