Enhebrar estado extra a través de un analizador sintáctico en Scala

Te daré el tl; dr por adelantado

Estoy tratando de usar el transformador de mónada de estado en Scalaz 7 para enhebrar estado extra a través de un analizador, y estoy teniendo problemas para hacer algo útil sin escribir un lote de t m a -> t m b versiones de métodos m a -> m b.

Un ejemplo de problema de análisis

Supongamos que tengo una cadena que contiene paréntesis anidados con dígitos dentro de ellos:

val input = "((617)((0)(32)))"

También tengo un flujo de nombres de variables frescas (caracteres, en este case):

val names = Stream('a' to 'z': _*)

Quiero sacar un nombre de la parte superior de la secuencia y asignarlo a cada paréntesis expression as I parse it, and then map that name to a string representing the contenido de los paréntesis, con las expresiones entre paréntesis anidadas (si las hay) reemplazadas por sus nombre.

Para hacer esto más concreto, esto es lo que me gustaría que la salida se vea como para la entrada de ejemplo anterior:

val target = Map(
  'a' -> "617",
  'b' -> "0",
  'c' -> "32",
  'd' -> "bc",
  'e' -> "ad"
)

Puede haber una cadena de dígitos o arbitrariamente muchos subexpresiones en un nivel dado, pero estos dos tipos de contenido no se mezclarán en una sola expresión entre paréntesis.

Para mantener las cosas simples, asumiremos que la corriente de nombres nunca contener duplicados o dígitos, y que siempre contendrá lo suficiente nombres para nuestra entrada.

Usando combinadores parser con un poco de estado mutable

El ejemplo anterior es una versión ligeramente simplificada del problema de análisis en este Desbordamiento de Pila pregunta. Yo respondí a esa pregunta con una solución que se veía aproximadamente así:

import scala.util.parsing.combinator._

class ParenParser(names: Iterator[Char]) extends RegexParsers {
  def paren: Parser[List[(Char, String)]] = "(" ~> contents <~ ")" ^^ {
    case (s, m) => (names.next -> s) :: m
  }

  def contents: Parser[(String, List[(Char, String)])] = 
    "\\d+".r ^^ (_ -> Nil) | rep1(paren) ^^ (
      ps => ps.map(_.head._1).mkString -> ps.flatten
    )

  def parse(s: String) = parseAll(paren, s).map(_.toMap)
}

No es tan malo, pero preferiría evitar el estado mutable.

Lo que quiero

La biblioteca de Haskell Parsec hace agregar estado de usuario a un analizador trivialmente fácil:

import Control.Applicative ((*>), (<$>), (<*))
import Data.Map (fromList)
import Text.Parsec

paren = do
  (s, m) <- char '(' *> contents <* char ')'
  h : t  <- getState
  putState t
  return $ (h, s) : m
  where
    contents
      =  flip (,) []
     <$> many1 digit
     <|> (\ps -> (map (fst . head) ps, concat ps))
     <$> many1 paren

main = print $
  runParser (fromList <$> paren) ['a'..'z'] "example" "((617)((0)(32)))"

Esta es una traducción bastante sencilla de mi analizador de Scala anterior, pero sin estado mutable.

Lo que he intentado

Estoy tratando de acercarme lo más posible a la solución Parsec como puedo usando el transformador de mónada de estado de Scalaz, así que en lugar de Parser[A] estoy trabajando con StateT[Parser, Stream[Char], A]. Tengo una "solución" que me permite escribir lo siguiente:

import scala.util.parsing.combinator._
import scalaz._, Scalaz._

object ParenParser extends ExtraStateParsers[Stream[Char]] with RegexParsers {
  protected implicit def monadInstance = parserMonad(this)

  def paren: ESP[List[(Char, String)]] = 
    (lift("(" ) ~> contents <~ lift(")")).flatMap {
      case (s, m) => get.flatMap(
        names => put(names.tail).map(_ => (names.head -> s) :: m)
      )
    }

  def contents: ESP[(String, List[(Char, String)])] =
    lift("\\d+".r ^^ (_ -> Nil)) | rep1(paren).map(
      ps => ps.map(_.head._1).mkString -> ps.flatten
    )

  def parse(s: String, names: Stream[Char]) =
    parseAll(paren.eval(names), s).map(_.toMap)
}

Esto funciona, y no es mucho menos conciso que la versión de estado mutable o la versión Parsec.

Pero mi ExtraStateParsers es feo como el pecado-No quiero probar tu paciencia más de lo que ya tengo, así que no lo incluiré aquí (aunque aquí hay un enlace, si realmente lo quieres). He tuve que escribir nuevas versiones de cada Parser y Parsers método que utilizo anteriormente para mis tipos ExtraStateParsers y ESP (rep1, ~>, <~, y |, en caso de que estés contando). Si hubiera necesitado usar otros combinadores, también habría tenido que escribir nuevas versiones a nivel de transformador de estado de ellos.

¿Hay una forma más limpia de hacer esto? Me encantaría ver un ejemplo de un transformador de mónada de estado de Scalaz 7 que se usa para enhebrar el estado a través de un analizador sintáctico, pero los ejemplos de Scalaz 6 o Haskell también serían útiles y apreciado.