<div dir="ltr">Details aside, this sounds like an instance of the common relationship between Monad and Applicative: namely, analysis is possible on Applicative structures without executing effects, while Monad structures cannot be analyzed without executing its effects in a specific instance and looking at their results.  That's less specific than your result and uses some fuzzy language, but it's a pattern that comes up a lot.  As far as Arrow, in the absence of ArrowApply it occupies a space similar to Applicative.  I imagine an ArrowApply instance would interfere with your desired properties in the same way that a Monad instance does.<div><br></div><div>People have definitely talked about using Applicative for parsing in this way (e.g., see <a href="https://jobjo.github.io/2019/05/19/applicative-parsing.html">https://jobjo.github.io/2019/05/19/applicative-parsing.html</a>), but I'm not familiar with a specific parsing library that meets your needs.  Maybe someone else can jump in there. I just wanted to suggest that you broaden your search to include Applicative-based parsers as well as Arrow-based.</div><div><br></div><div>Good luck!</div><div><br></div><div>Chris </div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Jun 11, 2021 at 6:22 PM Askar Safin via Haskell-Cafe <<a href="mailto:haskell-cafe@haskell.org">haskell-cafe@haskell.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi. I hope people here, at haskell-cafe, like various theorem, pearls on parsing, monads, monad transformers and anything like that, right? So, I just proved something interesting for you!<br>
Theorem about impossibility of monad transformer for parsing with (1) unbiased choice and (2) ambiguity checking before running embedded monadic action.<br>
I already presented it on #haskell in Libera chat, now let me send it here. This is not quite theorem, i. e. I would not say that it keeps with mathematical standards of rigor.<br>
---------------------------<br>
I want monad transformer (let's name it ParserT) with following properties (hint: I proved such transformer doesn't exist):<br>
<br>
- it has unbiased choice (i. e. (<|>) :: ParserT m a -> ParserT m a -> ParserT m a) (this means running parser can give you multiple results)<br>
- you can run parser without executing embedded monadic actions. i. e. "run" function should look like this:<br>
<br>
run :: ParserT m a -> String -> [m a] {- Not m [a] -}<br>
<br>
I want such function, because I want to do this: run parser, then count number of possible parses, then (if count is equal to one) actually execute embedded monadic action. I. e. I want something like this:<br>
<br>
parser :: ParserT (Either String) ()<br>
parser = .....<br>
<br>
main :: IO ()<br>
main = do {<br>
  input <- ....;<br>
  case run parser input of {<br>
    [res] -> do {<br>
      -- Cool! we got exactly one result! Let's run it<br>
      case res of {<br>
        Left e -> putStr $ "Parsing succeed, but we have semantic error: " ++ e;<br>
        Right () -> putStr "Everything OK";<br>
      };<br>
    };<br>
    _ -> putStr "Cannot parse. 0 parse trees or >1 parse trees";<br>
  };<br>
}<br>
<br>
Now let me state theorem.<br>
<br>
Theorem. Such transformer doesn't exist. Moreover, even if I replace arbitrary monad "m" with particular monad "Maybe" (or "Either String") the task is still unsolvable. But the task seems achievable using arrows<br>
<br>
-------------------------------------<br>
<br>
Proof. Let's imagine such "ParsecT Maybe" exists. Let's imagine we have such function:<br>
<br>
char :: Char -> ParserT Maybe Char {- matches supplied char -}<br>
<br>
Also, keep in mind we have "lift":<br>
<br>
lift :: Maybe a -> ParserT Maybe a<br>
<br>
Now let's write this:<br>
<br>
parseA = char 'a'<br>
parseAorA = char 'a' <|> char 'a'<br>
contr = do {<br>
  a <- lift $ Nothing;<br>
  if a > 5 then parseA else parseAorA;<br>
  return ();<br>
}<br>
<br>
Now, please, say, what is (run contr "a")? How many elements will (run contr "a") have? If "a > 5", then (run contr "a") will contain one element. If "a <= 5", then (run contr "a") will contain two elements. But we cannot know whether "a > 5", because we cannot extract "a" from "Nothing". So, we got contradiction. QED<br>
-----------------<br>
In other words, function "run" with type "ParserT m a -> String -> [m a]" means that we should somehow be able to know count of parses before executing monadic action. But this is impossible, because our parser can contain code like this: (do { a <- lift $ ...; if a then ... else ...; }). I. e. count of parses can depend on value, embedded in inner monad, so we cannot know count of parses before we run embedded inner monadic action.<br>
<br>
This theorem is not simply out of curiosity. I actually need parsing lib with this properties.<br>
<br>
1. I need unbiased choice, because it is compatible with CFGs, and I love CFGs (as opposed to PEG)<br>
2. I need embedding monads, because this allows me to check semantic errors (such as "type mismatch") in time of parsing. I. e. I can simply embed (Either String) monad into parsing monad, and use this (Either String) monad for checking semantic errors<br>
3. I need to know number of parse trees before executing monadic actions (i. e. i need ([m a]) as opposed to (m [a])), because I want to check that number of parses is equal to 1 (if not, then print error), and then extract inner monad (which will contain information about semantic errors). In other words, I want check the input for ambiguity (and print error if it is ambiguous), and if it is not ambiguous, then print possible semantic errors (if any). The possibility of ambiguity detection is whole point of using CFGs as opposed to PEGs (which are always unambiguous, but this unambiguity is simply trick).<br>
4. Every terminal and nonterminal should carry location info (i. e. begin and end of this string). And this location info should be passed implicitly. And it should not be embedded deeply in ASTs I will use. (This means that "happy" is not for me. As well as I understand it cannot implicitly pass location info. In <a href="https://github.com/ghc/ghc/blob/master/compiler/GHC/Parser.y" rel="noreferrer" target="_blank">https://github.com/ghc/ghc/blob/master/compiler/GHC/Parser.y</a> I see explicit location management all the time.)<br>
5. Left recursion is not needed<br>
<br>
So, does such lib exist? Well, I already know such lib should be arrow based (as opposed to monad). So, is there such arrow parsing lib? Embedding arbitrary inner monad is not needed, just embedding (Either String) will go.<br>
<br>
If there is no such lib, I plan to create my own. This is threat! :)<br>
<br>
Also, I wrote letter long ago asking for parsing lib with different properties. I included desire for reversibility, among others. Well, this was other task. For my current task I don't need reversibility.<br>
<br>
==<br>
Askar Safin<br>
<a href="http://safinaskar.com" rel="noreferrer" target="_blank">http://safinaskar.com</a><br>
<a href="https://sr.ht/~safinaskar" rel="noreferrer" target="_blank">https://sr.ht/~safinaskar</a><br>
<a href="https://github.com/safinaskar" rel="noreferrer" target="_blank">https://github.com/safinaskar</a><br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div>