Can this parser (concerning about infinite hierarchy of operators) be implemented purely in ReadPrec?

Question

In Haskell, I tried to implement a parser for expressions containing hyperoperations, and finally succeeded. Valid expressions shall contain:

• Parentheses.

• Nonnegative integers.

• Addition represented by +. It has precedence of 6, and its associativity shall be exploited.

• Multiplication represented by *. It has precedence of 7, and its associativity shall be exploited.

• Exponentiation represented by ^. It has precedence of 8.

• Tetration represented by ^^. It has precedence of 9.

• Pentation represented by ^^^. It has precedence of 10.

• ad infinitum.

I was struggling for months to implement this with ReadPrec. It was truly a "Eureka" moment when I found that I have a workaround:

import Control.Monad
import Text.ParserCombinators.ReadPrec
import Text.Read
import Text.Read.Lex

hyperOp :: Int -> Integer -> Integer -> Integer
hyperOp 0 _ y = y + 1
hyperOp 1 x y = x + y
hyperOp 2 x y = x * y
hyperOp 3 x y = x ^ y
hyperOp n x 0 = 1
hyperOp n x y = hyperOp (n-1) x (hyperOp n x (y-1))

parseHyperOp :: Int -> ReadPrec Integer
parseHyperOp opn = parens . choice $
    lift readDecP
    : prec 6 (do
        m <- step (parseHyperOp opn)
        Symbol "+" <- lexP
        n <- parseHyperOp opn
        return (m + n))
    : prec 7 (do
        m <- step (parseHyperOp opn)
        Symbol "*" <- lexP
        n <- parseHyperOp opn
        return (m * n))
    : fmap (\c -> prec (7 + c) $ do
        m <- step (parseHyperOp opn)
        Symbol op <- lexP
        guard (replicate c '^' == op)
        n <- step (parseHyperOp opn)
        return (hyperOp (2 + c) m n)
        ) [1 .. opn]

highestOp :: String -> Int
highestOp "" = 0
highestOp ('^':str) = let
    (str1, str2) = span ('^'==) str
    in max (1 + length str1) (highestOp str2)
highestOp (_  :str) = highestOp str

parseOp :: Prec -> ReadS Integer
parseOp c str = readPrec_to_S (parseHyperOp (highestOp str)) c str

The trick is to find the highest operation within the input string. That makes the choice finite.

Still, I think it's quite ugly to use readPrec_to_S. Can this be implemented without using readPrec_to_S and co?

Answer 1

A simple rule of thumb is that you should never use readS_to_Prec and readS_to_P. Consider that once you've converted a parser to a ReadS to run it, there is no way back. (One handwavy explanation is that those functions are really dirty hacks, which is also why gather is undefined when they are used.)

Under those constraints, the only place where you can find out the maximal level opn of hyperoperators is at the very top level where you actually apply your parser to a string; that is the one location where you can scan the string to compute opn. That means that all your parsers need to be parameterized by opn in order to pass it down to parseHyperOp.

parseOp :: Int -> P.ReadP Integer
parseOp opn = readPrec_to_P (parseHyperOp opn) 0

-- Top-level runner for parsers parameterized by opn
runP :: (Int -> P.ReadP a) -> ReadS a
runP parser str =
  let opn = highestOp str in
  P.readP_to_S (parser opn) str

example = runP parseOp "(1 + 2) ^ 3 + 2 ^ 2"

Having an infinite number of precedence levels makes top-down parsing (the popular approach using parser combinators) rather problematic, since there isn't really a "top" to start from. Consider giving up that feature (by making all operators beyond a certain level non-associative at the same level), or switching to a bottom-up parsing strategy.