Vou te dar o tl; dr up front

Eu estou tentando usar o transformador monad estado emScalaz 7 para encadear estado extra através de um analisador, e estou tendo problemas para fazer qualquer coisa útil sem escrever ummuito dot m a -> t m b versões dem a -> m b métodos.

Um exemplo de problema de análise

Suponha que eu tenha uma string contendo parênteses aninhados com dígitos dentro deles:

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

Eu também tenho um fluxo de novos nomes de variáveis ​​(caracteres, neste caso):

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

Eu quero puxar um nome fora do topo do fluxo e atribuí-lo a cada expressão entre parênteses como eu analisá-lo e, em seguida, mapeie esse nome para uma seqüência representando o conteúdo dos parênteses, com as expressões de parênteses aninhadas (se houver) substituídas por os nomes deles.

Para tornar isso mais concreto, aqui está o que eu gostaria que a saída fosse parecida com a entrada de exemplo acima:

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

Pode haver uma sequência de dígitos ou arbitrariamente muitas subexpressões em um determinado nível, mas esses dois tipos de conteúdo não serão misturados em uma única expressão entre parênteses.

Para manter as coisas simples, vamos supor que o fluxo de nomes nunca conterá duplicatas ou dígitos, e que sempre conterá nomes suficientes para nossa entrada.

Usando combinadores de analisador com um pouco de estado mutável

O exemplo acima é uma versão ligeiramente simplificada do problema de análise emesta pergunta de estouro de pilha. Eurespondeu a essa pergunta com uma solução que parecia mais ou menos assim:

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)
}

Não é tão ruim, mas prefiro evitar o estado mutável.

O que eu quero

Haskell'sParsec biblioteca faz a adição do estado do usuário a um analisador trivialmente fácil:

import Control.Applicative ((*>), (<
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)))"
gt;), (<*))
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 (,) []
     <
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)))"
gt; many1 digit
     <|> (\ps -> (map (fst . head) ps, concat ps))
     <
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)))"
gt; many1 paren

main = print $
  runParser (fromList <
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)))"
gt; paren) ['a'..'z'] "example" "((617)((0)(32)))"

Esta é uma tradução bastante simples do meu analisador Scala acima, mas sem estado mutável.

O que eu tentei

Estou tentando chegar o mais perto possível da solução da Parsec usando o transformador de monad de estado de Scalaz, então ao invés deParser[A] Estou trabalhando comStateT[Parser, Stream[Char], A]. Eu tenho uma "solução" que me permite escrever o seguinte:

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)
}

Isso funciona, e não é muito menos conciso do que a versão de estado mutável ou a versão Parsec.

Mas o meuExtraStateParsers é feio como pecado - eu não quero tentar sua paciência mais do que eu já tenho, então eu não vou incluí-la aqui (emboraaqui está um link, se você realmente quiser). Eu tive que escrever novas versões de cadaParser eParsers método eu uso acima para o meuExtraStateParsers eESP tipos (rep1, ~>, <~e|, no caso você está contando). Se eu precisasse usar outros combinadores, eu teria que escrever novas versões de nível de transformador de estado deles também.

Existe uma maneira mais limpa de fazer isso? Eu adoraria ver um exemplo de um transformador de monad de estado do Scalaz 7 sendo usado para encadear estado através de um analisador, mas os exemplos de Scalaz 6 ou Haskell também seriam úteis e apreciados.