Enhebrando el estado extra a través de un analizador en Scala

haskell monads

Question

Te doy el tl; dr al frente

Estoy tratando de usar el transformador de mónada estatal en Scalaz 7 para pasar un estado adicional a través de un analizador, y estoy teniendo problemas para hacer algo útil sin escribir muchas versiones tma -> tmb de los métodos ma -> mb .

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 nuevas (caracteres, en este caso):

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

Quiero quitar un nombre de la parte superior de la secuencia y asignarlo a cada expresión entre paréntesis mientras lo analizo, y luego asignar ese nombre a una cadena que representa el contenido de los paréntesis, con las expresiones entre paréntesis anidadas (si corresponde) reemplazadas por sus nombres.

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

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

Puede haber una cadena de dígitos o arbitrariamente muchas sub-expresiones 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 secuencia de nombres nunca contendrá duplicados ni dígitos, y que siempre contendrá suficientes nombres para nuestra entrada.

Usando combinadores de analizadores con un poco de estado mutable.

El ejemplo anterior es una versión ligeramente simplificada del problema de análisis en esta pregunta de Desbordamiento de pila . Respondí esa pregunta con una solución que se parecía aproximadamente a esto:

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 está tan mal, pero preferiría evitar el estado mutable.

Lo que quiero

Parsec biblioteca Parsec de Haskell hace que agregar el estado de usuario a un analizador sea 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 Scala anterior, pero sin estado mutable.

Lo que he intentado

Estoy tratando de acercarme lo más posible a la solución Parsec, ya que puedo usar el transformador de mónada estatal 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 mis ExtraStateParsers son feos como el pecado. No quiero probar tu paciencia más de lo que ya tengo, así que no lo ExtraStateParsers aquí (aunque aquí hay un enlace , si realmente lo quieres). He tenido que escribir nuevas versiones de todos los métodos Parser y Parsers que uso anteriormente para mis tipos ExtraStateParsers y ESP ( rep1 , ~> , <~ y | , en caso de que esté contando). Si hubiera necesitado usar otros combinadores, también habría tenido que escribir nuevas versiones de nivel de transformador de estado.

¿Hay una manera 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 utiliza para pasar el estado a través de un analizador, pero los ejemplos de Scalaz 6 o Haskell también serían útiles y apreciados.

Answer 1

Probablemente, la solución más general sería volver a escribir la biblioteca del analizador de Scala para acomodar los cómputos monádicos mientras analiza (como lo hizo usted en parte), pero esa sería una tarea bastante laboriosa.

Sugiero una solución utilizando el estado de ScalaZ donde cada uno de nuestros resultados no es un valor de tipo Parse[X] , sino un valor de tipo Parse[State[Stream[Char],X]] (alias como ParserS[X] ). Por lo tanto, el resultado global analizado no es un valor, sino un valor de estado monádico, que luego se ejecuta en algunos Stream[Char] . Esto es casi un transformador de mónada, pero tenemos que hacer el levantamiento / desvío manual. Hace que el código sea un poco más feo, ya que a veces necesitamos elevar los valores o usar map / flatMap en varios lugares, pero creo que aún es razonable.

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

object ParenParser extends RegexParsers with States {
  type S[X] = State[Stream[Char],X];
  type ParserS[X] = Parser[S[X]];


  // Haskell''s `return` for States
  def toState[S,X](x: X): State[S,X] = gets(_ => x)

  // Haskell''s `mapM` for State
  def mapM[S,X](l: List[State[S,X]]): State[S,List[X]] =
    l.traverse[({type L[Y] = State[S,Y]})#L,X](identity _);

  // .................................................

  // Read the next character from the stream inside the state
  // and update the state to the stream''s tail.
  def next: S[Char] = state(s => (s.tail, s.head));


  def paren: ParserS[List[(Char, String)]] =
    "(" ~> contents <~ ")" ^^ (_ flatMap {
      case (s, m) => next map (v => (v -> s) :: m)
    })


  def contents: ParserS[(String, List[(Char, String)])] = digits | parens;
  def digits: ParserS[(String, List[(Char, String)])] =
    "//d+".r ^^ (_ -> Nil) ^^ (toState _)
  def parens: ParserS[(String, List[(Char, String)])] =
    rep1(paren) ^^ (mapM _) ^^ (_.map(
        ps => ps.map(_.head._1).mkString -> ps.flatten
      ))


  def parse(s: String): ParseResult[S[Map[Char,String]]] =
    parseAll(paren, s).map(_.map(_.toMap))

  def parse(s: String, names: Stream[Char]): ParseResult[Map[Char,String]] =
    parse(s).map(_ ! names);
}

object ParenParserTest extends App {
  {
    println(ParenParser.parse("((617)((0)(32)))", Stream(''a'' to ''z'': _*)));
  }
}

Nota: Creo que su enfoque con StateT[Parser, Stream[Char], _] no es conceptualmente correcto. El tipo dice que estamos construyendo un analizador dado algún estado (un flujo de nombres). Por lo tanto, sería posible que dados diferentes flujos obtengamos analizadores diferentes. Esto no es lo que queremos hacer. Solo queremos que el resultado del análisis dependa de los nombres, no del analizador completo . De esta manera Parser[State[Stream[Char],_]] parece ser más apropiado (Haskell''s Parsec tiene un enfoque similar, el estado / mónada está dentro del analizador).