Haskell Bencoded Dictionary Parser
Below is your code with some minor tweaks and the comments moved into standard Haddock form.

module Bencode (readBencodedFile, BencodedValue(..), bencode, bencodeBS) where

import qualified Control.Monad as Mon
import Data.ByteString (ByteString)
import Data.ByteString.Char8 (pack)
import qualified Data.Map as M
import Text.Parsec.ByteString as ParseBS
import Text.Parsec.Char (anyChar, char, digit)
import Text.Parsec.Prim ((&lt;|&gt;), parserFail, runParser)
import Text.Parsec.Combinator (count, many1, option)
import qualified Text.Parsec.Error as PE


type BMapT = M.Map BencodedValue BencodedValue

data BencodedValue = Bint Integer
                   | Bstr String
                   | Blist [BencodedValue]
                   | Bmap BMapT
                   deriving (Eq, Ord, Show)


-- |Transform a 'BencodedValue' back to an encoded string
bencode :: BencodedValue -&gt; String
bencode (Bint i)   = "i" ++ show i ++ "e"
bencode (Bstr s)   = (show . length) s ++ ":" ++ s
bencode (Blist bs) = 'l':concatMap bencode bs ++ "e"
bencode (Bmap bm)  = M.foldlWithKey (\a k b -&gt; a ++ bencode k ++ bencode b) "d" bm  ++ "e"


-- |Return a 'BencodedValue' value to it original encoded 'ByteString' form.
bencodeBS :: BencodedValue -&gt; ByteString
bencodeBS = pack . bencode


{-|
  'readBencodedFile' reads data from a torrent file and returns the parsed
  result as a dictionary in a 'BencodedValue'.
  The 'String' is the filename of the torrent to read.
 -}
readBencodedFile :: String -&gt; IO (Either PE.ParseError BencodedValue)
readBencodedFile = parseFromFile bMap

------------------------
-- Internal functions --
------------------------

-- |Parse a Bencoded Integer
bInt :: ParseBS.Parser BencodedValue
bInt = do char 'i'
          neg  &lt;- option ' ' (char '-')
          nums &lt;- many1 digit
          char 'e'
          mkBint neg nums
  where
    mkBint ' ' ['0']    = return $ Bint 0
    mkBint '-' ('0':ns) = parserFail "Can't have a negative zero"
    mkBint _   ('0':ns) = parserFail "Invalid number with a leading zero"
    mkBint '-' nums     = return $ Bint $ read ('-':nums)
    mkBint _   nums     = return $ Bint $ read nums


-- |Parse a Bencoded String
bString :: ParseBS.Parser BencodedValue
bString = do nums &lt;- many1 digit
             char ':'
             mkBstring (read nums)
  where
    mkBstring size = do cs &lt;- count size anyChar
                        return $ Bstr cs


-- |Parse a Bencoded List
bList :: ParseBS.Parser BencodedValue
bList = do char 'l'
           ls &lt;- many1 (bInt &lt;|&gt; bString &lt;|&gt; bList &lt;|&gt; bMap)
           char 'e'
           mkBlist ls
  where
    mkBlist = return . Blist


-- |Parse a Bencoded dictionary
bMap :: ParseBS.Parser BencodedValue
bMap = do char 'd'
          entries &lt;- many1 dictEntry
          char 'e'
          mkBmap entries
  where
    mkBmap = return . Bmap . M.fromList


-- |Parse a Bencoded dictionary entry.
-- This is an internal function declared outside of 'bMap' to
-- facilitate testing.
dictEntry :: ParseBS.Parser (BencodedValue, BencodedValue)
dictEntry = do key &lt;- bString
               value &lt;- bString &lt;|&gt; bList &lt;|&gt; bInt &lt;|&gt; bMap
               return (key, value)


Answers to your questions.


Without getting REAL fancy there is no good way limit the BMap argument to a Bstr while it is an member of algebraic type.
Your analogy to repr from Python is a good one. Typically if there is a Haskell Show instance there is also a Read instance so show . read . show is valid. In your case the result of show needs to be parsed again and you do not expose a parse from string/bytestring. I added a bencode and bencodeBS which takes a BencodedValue and outputs a String or ByteString.
Look at where I simplified or renamed your items to see suggestions on idiomatic usage. On the whole you did pretty well. If I had more time I would have liked to transform your parser functions into Applicative style. By transitioning to the mkFoo functions I started that process for you if you like.
In the code you ask about why this is a String when the ByteString is the input. It is because the parsers are returning Strings parsed from the ByteString. If the performance really matters you could transition over to Attoparsec.