Список синтаксического анализа любого типа

Если я правильно понимаю, тестовый пример:

parseTest parsePredSub "P(f(x:X)=a:A,b:B)"

возвращает:

([(("f",([("x","X")],"A")),("a","A"))],("P",[("b","B")]))

но вместо этого вы хотите, чтобы он вернулся

([(("f",([("x","X")],"A")),("a","A"))],("P",[("a","A"),("b","B")]))
                           ^^^^^^^^^         ^^^^^^^^^

так что «права» одновременно вносят вклад в привязку и аргумент предиката.

Если да, то «проблема» в том, что ваш код:

parsePredSub :: Parser PredSub
parsePredSub = try $ do {(p,bc) <- pparens (commaSep parseVSub);
                         return (rights bc,(p,lefts bc))}

разделяет правые (привязки) и левые (несвязанные аргументы) и возвращает список несвязанных аргументов только как часть Pred. Вам нужно будет написать вспомогательную функцию, которая извлекает VarSrt как из привязок, так и из несвязанных аргументов:

varSrt (Left vs) = vs
varSrt (Right (_,vs)) = vs

и используйте map varSrt вместо вызова lefts, чтобы извлечь все VarSrt слева и справа по порядку. Что-то вроде этого:

parsePredSub :: Parser PredSub
parsePredSub = try $ do {(p,bc) <- pparens (commaSep parseVSub);
                         return (rights bc,(p,map varSrt bc))}
  where varSrt (Left vs) = vs
        varSrt (Right (_,vs)) = vs

Вот полный работоспособный пример, иллюстрирующий изменения:

module EitherParser where

import Control.Monad
import Data.Either
import Text.Parsec

type Parser = Parsec String ()

type Pre = String
type Var = String
type Srt = String
type Sym = String
type VSub = Either VarSrt Sub

commaSep :: Parser a -> Parser [a]
commaSep p = (:) <$> p <*> many (char ',' *> p)

whitespace :: Parser ()
whitespace = spaces

--
-- Your code starts here
--

-- (types Pre and Var and Srt and Sym are String)
type VarSrt = (Var,Srt)
type Ctx = [VarSrt]
type Trm = (Sym,([VarSrt],Srt))
type Sub = (Trm,VarSrt)
type Bind = [Sub]
type Pred = (Pre, Ctx)
type PredSub = (Bind, Pred)

parseVS :: Parser VarSrt
parseVS = do {v<-identifier; string ":"; s<-identifier; return $ (v,s)}

pparens :: Parser a -> Parser (String,a)
pparens par = try $ do {p<-identifier; string "("; z <- par; string ")";
                        return (p,z)}

parseSub :: Parser Sub
parseSub =
  do {(f,a) <- pparens (commaSep parseVS); string " = "; spaces;
       (x,s) <- parseVS; spaces;
       return $ ((f,(a,s)),(x,s))}

parseVSub :: Parser VSub
parseVSub = choice [Left <$> try parseVS, Right <$> try parseSub]

------- FIXED VERSION ----
parsePredSub :: Parser PredSub
parsePredSub = try $ do {(p,bc) <- pparens (commaSep parseVSub);
                         return (rights bc,(p,map varSrt bc))}
  where varSrt (Left vs) = vs
        varSrt (Right (_,vs)) = vs
--------------------------

lexeme :: Parser a -> Parser a
lexeme p = p <* whitespace

identifier :: Parser String
identifier = lexeme ((:) <$> firstChar <*> many nonFirstChar)
  where
    firstChar = letter <|> char '_'
    nonFirstChar = digit <|> firstChar

symbol :: String -> Parser String
symbol s = try $ lexeme $ do
    u <- many1 (oneOf "<>=+-^%/*!|,")
    guard (s == u)
    return s

--
-- Your code ends here
--

main = parseTest parsePredSub "P(f(x:X)=a:A,b:B)"