title: Parse expression right-to-left
body: <p>I'm building a parser for expression.</p>
  
  <p>Here's my grammar rule:</p>
  
  <pre><code>expr   ::= term   (+ expr | - expr | null)
  term   ::= expo   (* term | / term | null)
  expo   ::= factor (^ expo | null)
  factor ::= (expr) | int
  </code></pre>
  
  <p>and corresponding code:</p>
  
  <pre><code>expr :: Parser Int
  expr = do t &lt;- term
            do _ &lt;- symbol "+"
               e &lt;- expr
               return (t + e)
               &lt;|&gt; do _ &lt;- symbol "-"
                      e &lt;- expr
                      return (t - e)
                      &lt;|&gt; return t
  
  term :: Parser Int
  term = do ep &lt;- expo
            do _ &lt;- symbol "*"
               t &lt;- term
               return (ep * t)
               &lt;|&gt; do _ &lt;- symbol "/"
                      t &lt;- term
                      return (ep `div` t)
                      &lt;|&gt; return ep
  
  expo :: Parser Int
  expo = do f &lt;- factor
            do _ &lt;- symbol "^"
               e &lt;- expo
               return (f ^ e)
               &lt;|&gt; return f
  
  factor :: Parser Int
  factor = do _ &lt;- symbol "("
              e &lt;- expr
              _ &lt;- symbol ")"
              return e
              &lt;|&gt; integer
  </code></pre>
  
  <p>It works well for most case but fail for certain:</p>
  
  <pre><code>$ eval "3*1/3"
  </code></pre>
  
  <blockquote>
    <p>0</p>
  </blockquote>
  
  <p>since <code>3 * 1 / 3</code> is parsed to <code>3 * (1 / 3)</code> </p>
  
  <pre><code> (*)
   / \
  3  (/)
     / \
    1   3
  </code></pre>
  
  <p>and</p>
  
  <pre><code>$ eval "4-3-2"
  </code></pre>
  
  <blockquote>
    <p>3</p>
  </blockquote>
  
  <p>since <code>4 - 3 - 2</code> is parsed to <code>4 - (3 - 2)</code></p>
  
  <pre><code> (-)
   / \
  4  (-)
     / \
    3   2
  </code></pre>
  
  <p>I realize it's all about parsing direction (right associativity).</p>
  
  <p>What I expect is <code>(4 - 3) - 2</code></p>
  
  <pre><code>   (-)
     / \
   (-)  2
   / \
  4   3
  </code></pre>
  
  <p>which means I would parse <code>right-left</code> and interpret it <code>left-right</code> (or parse it recursively).</p>
  
  <p>I have no idea how to achieve so. Nothing but <code>foldl</code> comes to my mind so far.</p>
  
  <p>Could someone suggest what should I do to fix it?</p>
  
  <p>total program:</p>
  
  <pre><code>{-# OPTIONS_GHC -Wall #-}
  
  import Control.Applicative
  import Data.Char
  
  newtype Parser a = P (String -&gt; [(a, String)])
  
  parse :: Parser a -&gt; String -&gt; [(a, String)]
  parse (P p) inp = p inp
  
  instance Functor Parser where
      fmap g p = P (\inp -&gt; case parse p inp of
                                 []         -&gt; []
                                 [(v, out)] -&gt; [(g v, out)]
                                 _          -&gt; undefined)
  
  instance Applicative Parser where
      pure v = P (\inp -&gt; [(v, inp)])
      pg &lt;*&gt; px = P (\inp -&gt; case parse pg inp of
                                  []         -&gt; []
                                  [(g, out)] -&gt; parse (fmap g px) out
                                  _          -&gt; undefined)
  
  instance Monad Parser where
      p &gt;&gt;= f = P (\inp -&gt; case parse p inp of
                                []         -&gt; []
                                [(v, out)] -&gt; parse (f v) out
                                _          -&gt; undefined)
  
  instance Alternative Parser where
      empty   = P (\_ -&gt; [])
      p &lt;|&gt; q = P (\inp -&gt; case parse p inp of
                                []         -&gt; parse q inp
                                [(v, out)] -&gt; [(v, out)]
                                _          -&gt; undefined)
      many x = some x &lt;|&gt; pure []
      some x = pure (:) &lt;*&gt; x &lt;*&gt; many x
  
  item :: Parser Char
  item = P (\inp -&gt; case inp of
                         []        -&gt; []
                         (x : xs)  -&gt; [(x, xs)])
  
  sat :: (Char -&gt; Bool) -&gt; Parser Char
  sat p = do x &lt;- item
             if p x
                 then return x
                 else empty
  
  digit :: Parser Char
  digit = sat isDigit
  
  char :: Char -&gt; Parser Char
  char x = sat (== x)
  
  string :: String -&gt; Parser String
  string []       = return []
  string (x : xs) = do _ &lt;- char x
                       _ &lt;- string xs
                       return (x : xs)
  
  space :: Parser ()
  space = do _ &lt;- many (sat isSpace)
             return ()
  
  nat :: Parser Int
  nat = do xs &lt;- some digit
           return (read xs)
  
  int :: Parser Int
  int = do _ &lt;- char '-'
           n &lt;- nat
           return (-n)
           &lt;|&gt; nat
  
  token :: Parser a -&gt; Parser a
  token p = do _ &lt;- space
               v &lt;- p
               _ &lt;- space
               return v
  
  integer :: Parser Int
  integer = token int
  
  symbol :: String -&gt; Parser String
  symbol = token . string
  
  expr :: Parser Int
  expr = do t &lt;- term
            do _ &lt;- symbol "+"
               e &lt;- expr
               return (t + e)
               &lt;|&gt; do _ &lt;- symbol "-"
                      e &lt;- expr
                      return (t - e)
                      &lt;|&gt; return t
  
  term :: Parser Int
  term = do ep &lt;- expo
            do _ &lt;- symbol "*"
               t &lt;- term
               return (ep * t)
               &lt;|&gt; do _ &lt;- symbol "/"
                      t &lt;- term
                      return (ep `div` t)
                      &lt;|&gt; return ep
  
  expo :: Parser Int
  expo = do f &lt;- factor
            do _ &lt;- symbol "^"
               e &lt;- expo
               return (f ^ e)
               &lt;|&gt; return f
  
  factor :: Parser Int
  factor = do _ &lt;- symbol "("
              e &lt;- expr
              _ &lt;- symbol ")"
              return e
              &lt;|&gt; integer
  
  eval :: String -&gt; Int
  eval xs = case (parse expr xs) of
                 [(n, [])]  -&gt; n
                 [(_, out)] -&gt; error ("Unused input " ++ out)
                 []         -&gt; error "Invalid input"
                 _          -&gt; undefined
  </code></pre>