Lifting a value in the State monad in Haskell

I am writing a Sudoku generator/solver in Haskell as a learning exercise.

My solve function takes in a UArray but returns a State Int (UArray ...) so that it can also return the maximum difficulty level that it found while solving.

This is my function so far (still in the very experimental early stage):

import Control.Monad.State       (State, put)
import Control.Monad.Trans.Class (lift)
import Data.Array.MArray         (thaw)
import Data.Array.ST             (runSTUArray)
import Data.Array.Unboxed        (UArray)

-- ...

type Cell = Word16

solve :: UArray (Int, Int) Cell -> State Int (UArray (Int, Int) Cell)
solve grid = do
  return $ runSTUArray $ do
    arr <- thaw grid
    lift $ put 42
    return arr

It does not really do anything with the mutable array yet. I am simply trying to get it to type check with the put 42, but currently get the following error:

  • Couldn't match kind ‘*’ with ‘* -> *’
    When matching the kind of ‘ST’
  • In a stmt of a 'do' block: lift $ put 42
    In the second argument of ‘($)’, namely
      ‘do arr <- thaw grid
          lift $ put 42
          return arr’
    In the second argument of ‘($)’, namely
      ‘runSTUArray
         $ do arr <- thaw grid
              lift $ put 42
              return arr’
     |
 128 |     lift $ put 42
     |     ^^^^^^^^^^^^^

I was able to get a slight variation to compile and run after changing the State monad to a tuple (Int, Grid):

import Control.Monad.ST    (ST, runST)
import Data.Array.MArray   (freeze, thaw, writeArray)
import Data.Array.ST       (STUArray)
import Data.Array.Unboxed  (UArray)
import Data.Word (Word16)

type Cell = Word16
type Grid = UArray (Int, Int) Cell

solve :: Grid -> (Int, Grid)
solve grid =
  runST $ do
    mut <- thaw grid :: ST s (STUArray s (Int, Int) Cell)
    writeArray mut (0, 0) 0 -- test that I can actually write
    frozen <- freeze mut
    return (42, frozen)

This works fine for my application.