This is what I have so far:

> type Pid = FilePath
> type Uid = String
>
> type PsData     = Map String Uid
> type PsChildren = Map Pid PsInfo
>
> data PsInfo = PsInfo PsData PsChildren
> type PsMap  = Map Pid PsInfo
> type PsTree = Map Pid PsInfo
>
> parent :: PsData -> Pid
> parent psData = fromJust $ Map.lookup "PPid" psData
>
> getProcInfo :: PsData -> String -> IO PsData
> getProcInfo psData line = do
>   case matchRegex (mkRegex "^([a-z]+):[[:space:]]+(.*)$") line of
>     Nothing           -> return (psData)
>     Just [key, value] -> return (Map.insert key value psData)
>
> procInfo :: Pid -> IO PsInfo
> procInfo pid = do
>   procData <- readFile $ "/proc/" ++ pid ++ "/status"
>   psData <- foldM getProcInfo Map.empty (lines procData)
>   let [rUid, eUid, _] = words $ fromJust (Map.lookup "Uid" psData)
>   let [rGid, eGid, _] = words $ fromJust (Map.lookup "Gid" psData)
>   let uids = Map.fromList [("RUid", rUid), ("EUid", eUid),
>                            ("RGid", rGid), ("EGid", eGid)]
>   let psData' = Map.union psData uids
>   return (PsInfo psData' Map.empty)

I tried this for insertProc, but it obviously doesn't work... what would
be the correct way to do this?

> insertProc :: Pid -> StateT PsMap IO PsInfo
> insertProc pid = do
>   proc <- procInfo pid -- XXX this is obviously wrong...
>   psMap <- get
>   put (Map.insert pid proc psMap)
>   return (proc)

A second question: is it possible to make getProcInfo's type to be
PsData -> String -> PsData and use some operation similar to lift so
that it can be used with foldM, instead of making its return type to be
IO PsData explicitely?

Yes, and in fact, you don't even need foldM.  The only thing that actually uses IO is the readFile, so ideally you should just have a small function that just does the readFile and then processes the result using some (pure) functions.  Something like this:

> procInfo :: Pid -> IO PsInfo
> procInfo pid = do
>   procData <- readFile $ "/proc/" ++ pid ++ "/status"
>   return $ processData procData
>
> processData :: String -> PsInfo
> ... and so on ...

and so on.  Now instead of using foldM you can just use foldr.  IO is a cancer, best to keep it confined to as little of your program as possible! =)

-Brent