Haskell's shop question or why this monad is not working properly

Question

here is a kind of huge piece of code, it finally got huge because of the monadic material, but the task is simple: analyze the following line in the data structure:

"hello (some, args)" → [("fid", "hello"), ("sym", "("), ("args", "some, args"), ("sym", ")" )]

but the code I wrote is as follows:

"hello (some, args)" → [("fid", ""), ("sym", "("), ("args", ""), ("sym", ")")]

since you can see that the values ​​of "args" and "fid" are lost somewhere along the way, I suspect that the compiler decided not to calculate them for some mysterious reason.

I think the code is completely bad, also I am marked with a "?" parts that seem useless to me, but the compiler made me leave them in place :)

And here is the code:

type PStream = String type PToken a = (String, a) data Pstate a = Pstate (String -> ([PToken String], PStream)) a instance Monad Pstate where return x = Pstate (\_ -> ([("start", "")], "?")) x -- not used ? (Pstate bindparser v) >>= f = Pstate newparser fv where Pstate fparser fv = fv (btok, brest) = bindparser "this string also not used" (tok, rest) = fparser brest newparser _ = (btok ++ tok, rest) -- parsers parseFid :: Pstate String parseFid = Pstate parser "???" where parser r = let (fid, rest) = span (/= '(') r in ([("fid", fid)],rest) parseSym :: Char -> Pstate String parseSym c = Pstate parser "???" where parser r = let rest = parseOne cr in ([("sym", [c])],rest) parseOne s (h:t) = if h == s then t else error $ "symbol not match:" ++ [h] ++ " /= " ++ [s] parseOne s [] = [] parseArgs :: Pstate String parseArgs = Pstate parser "???" where parser r = let (args,rest) = span (/=')') r in ([("args", args)],rest) -- util load :: String -> Pstate String load s = Pstate (\ls -> ([("load", "")],ls)) "???" runP :: Pstate String -> ([PToken String], PStream) runP (Pstate fparser fv) = fparser "???" -- combined parser parseFunction :: String -> Pstate String parseFunction s = do load s --- should be 'return' here ? parseFid parseSym '(' parseArgs parseSym ')' main = putStrLn $ show $ runP $ parseFunction "hello(abc)" 

Answer 1

First, about "???" you had to leave. Consider your Pstate definition:

 data Pstate a = Pstate (String -> ([PToken String], PStream)) a 

This means that your data constructor is of the following type:

 Pstate :: (String -> ([PToken String], PStream)) -> a -> Pstate a 

This is a standard monad design. If you define monadic combinators, it is actually not uncommon to have some combinators where this is not needed, so the convention should leave it () in this case.

But in fact, I think your code is very strange, it looks like you did not capture the point of the state-maintained monad. Let me explain:

Typically, a state calculation is of the type:

 data MyState a = MyState (TypeOfState -> (a, TypeOfState)) 

This means that your monadic action is actually a kind of calculation that does something (possibly with your piece of state) and returns the result and the new state. The state is wrapped in a monad, so you do not need to think about it.

You use the same template in your code, but in a slightly different way. It looks like you fixed the result of the calculation [PToken String] . Let me correct your definition a bit:

 data Pstate a = Pstate (PStream -> (a, PStream)) 

So, now you get the return value of your calculation, using combinators that look like this:

 instance Monad Pstate where -- return should just wrap the computation up, so no changes return x = Pstate (\p -> (x,p)) parser1 >>= parser2 = Pstate $ \input -> let Pstate parser1' = parser1 Pstate parser2' = parser2 (output, rest) = parser1' input result = parser2' output rest in result 

Now you can see the type signatures for your parsers, they should be something like this: parseFid :: Pstate [PToken PStream] . This means that your parser consumes some input and returns the parsed material as [PToken PStream] and sets a new input to what is left. Consider this parseFid definition of how it might look:

 parseFid :: Pstate [PToken PStream] parseFid = Pstate $ \r -> let (fid, rest) = span (/= '(') r in ([("fid", fid)],rest) 

The rest remains an exercise for the reader. I would suggest you reformulate your parser with the State monad from Control.Monad.State.Strict . You will see that the monad above is basically the same.

---

In fact, in most cases it is easier to rely on existing and well-known tools, rather than folding your own parser. Here's a parser for what you need to create using Parsec , a modern library for parsing:

 import Text.Parsec parseFunction = do name <- parseName obrace <- parseOpeningBrace args <- parseArguments cbrace <- parseClosingBrace return [name,obrace,args,cbrace] parseName = many (noneOf "(") >>= \name -> return ("fid",name) parseOpeningBrace = char '(' >> return ("sym","(") parseArguments = many (noneOf ")") >>= \name -> return ("args",name) parseClosingBrace = char ')' >> return ("sym",")") main = case parse parseFunction "" "hello(some, args)" of Left error -> print error Right result -> print result 

Here's the conclusion:

 [("fid","hello"),("sym","("),("args","some, args"),("sym",")")] 

I really suggest you think about a better representation of the function being analyzed, this may make the task easier.

Answer 2

If you run the code as sent, you can see that the string "this string also not used" actually used, since you get this output:

 ([("load",""),("fid","this string also not used"),("sym","("),("args","this string also not used"),("sym",")")],"") 

In fact, the string is mainly used as input for all parsers. In the definition >>= string is entered as an input to bindparser . Then this parser perceives it as an input and creates tokens from it. parseFid , for example, parseFid a token ("fid","this string also not used") .

newparser built in >>= ignores any input that it may receive later, it simply returns the result of the parsing "this string also not used" . Similarly, the parser created with return ignores the value it should return.

Bind parsers should not ignore / override their inputs for parsing to work properly.

You should also decide what role the second Pstate parameter should play, since at the moment it basically contains "???", which does not look particularly useful.