首页 文章

如何表达功能类型？

提问于
浏览 次
3

我目前正在阅读关于在Haskell http://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf中解析组合子的Hutton 's and Meijer'论文 . 为此，我试图在scala中实现它们 . 我想构建一些易于编码，扩展且简单而优雅的东西 . 我已经为以下haskell代码提出了两个解决方案

/* Haskell Code */
type Parser a = String -> [(a,String)]

result :: a -> Parser a
result v = \inp -> [(v,inp)]

zero :: Parser a
zero = \inp -> []

item :: Parser Char
item = \inp -> case inp of
            [] -> []
            (x:xs) -> [(x,xs)]


/* Scala Code */
object Hutton1  {

  type Parser[A] = String => List[(A, String)]

  def Result[A](v: A): Parser[A] = str => List((v, str))
  def Zero[A]: Parser[A] = str => List()
  def Character: Parser[Char] = str => if (str.isEmpty) List() else List((str.head, str.tail))

}

object Hutton2 {
  trait Parser[A] extends (String => List[(A, String)])

  case class Result[A](v: A) extends Parser[A] {
    def apply(str: String) = List((v, str))
  }

  case object Zero extends Parser[T forSome {type T}] {
    def apply(str: String) = List()
  }

  case object Character extends Parser[Char] {
    def apply(str: String) = if (str.isEmpty) List() else List((str.head, str.tail))
  }
}


object Hutton extends App {
  object T1 {
    import Hutton1._

    def run = {
      val r: List[(Int, String)] = Zero("test") ++ Result(5)("test")
      println(r.map(x => x._1 + 1) == List(6))
      println(Character("abc") == List(('a', "bc")))
    }
  }

  object T2 {
    import Hutton2._

    def run = {
      val r: List[(Int, String)] = Zero("test") ++ Result(5)("test")
      println(r.map(x => x._1 + 1) == List(6))
      println(Character("abc") == List(('a', "bc")))
    }
  }

  T1.run
  T2.run
}

问题1

在Haskell中，零是一个可以按原样使用的函数值，它将解析所有失败的解析器，无论它们是Parser [Int]还是Parser [String] . 在scala中，我们通过调用函数Zero（第一种方法）来实现相同的功能，但是这样我相信每次调用Zero时我只生成一个不同的函数 . 这个陈述是真的吗？有没有办法缓解这种情况？

问题2

在第二种方法中，Zero case对象使用存在性 types Parser[T forSome {type T}] 来扩展Parser . 如果我用 Parser[_] 替换类型，我得到编译错误

Error:(19, 28) class type required but Hutton2.Parser[_] found
      case object Zero extends Parser[_] {
                           ^

我认为这两个表达式是等价的 . 是这样的吗？

问题3

您认为哪种方法可以在优雅和简洁方面表达组合器，从而产生更好的结果？

我使用scala 2.11.8

scala haskell functional-programming existential-type

2 回答

  • 2

    注意：我没有编译它，但我知道问题，可以提出两个解决方案 .

    • 更多Haskellish方法是不使用子类型，而是将 zero 定义为多态值 . 在那种风格中，我建议将解析器定义为不是从函数类型派生的 object ，而是作为一个案例类的值：
    final case class Parser[T](run: String => List[(T, String)])
def zero[T]: Parser[T] = Parser(...)

    正如@Alec所示，是的，每次都会产生一个新值，因为 def 被编译成一个方法 .

    • 如果要使用子类型，则需要使 Parser 协变 . 然后你可以给 zero 一个底部结果类型：
    trait Parser[+A] extends (String => List[(A, String)])
case object Zero extends Parser[Nothing] {...}

    这些在某种程度上是相关的;在系统F_ <:,这是Scala使用的基础，类型 _|_ （又名 Nothing ）和 \/T <: Any. T 的行为相同（这在类型和编程语言中暗示，第28章） . 这里给出的两种可能性是这一事实的结果 .

    对于存在感，我不太熟悉，但我认为虽然无界 T forSome {type T} 会表现得像 Nothing ，但Scala不允许存在类型的存在 .

    回复于
  • 1

    问题1

    我认为你是对的，这就是为什么： Zero1 以下每次使用时打印 hello . 解决方案 Zero2 涉及使用 val 代替 .

    def Zero1[A]: Parser[A] = { println("hi"); str => List() }
val Zero2: Parser[Nothing] = str => List()

    问题2

    不知道 . 我还是刚刚开始使用Scala . 希望有人回答这个 .

    问题3

    使用Scala的 for （因为你可以定义自定义 flatMap 和 map ），这个特性将更好地发挥作用，结果证明（有点）像Haskell的 do . 以下是您所需要的一切 .

    trait Parser[A] extends (String => List[(A, String)]) {
  def flatMap[B](f: A => Parser[B]): Parser[B] = {
      val p1 = this
      new Parser[B] {
        def apply(s1: String) = for {
          (a,s2) <- p1(s1)
          p2 = f(a)
          (b,s3) <- p2(s2)
      } yield (b,s3)
    }
  }

  def map[B](f: A => B): Parser[B] = {
    val p = this
    new Parser[B] {
      def apply(s1: String) = for ((a,s2) <- p(s1)) yield (f(a),s2) 
    }
  }
}

    当然，要做任何有趣的事情，你需要更多的解析器 . 我将向您推荐一个简单的解析器组合器： Choice(p1: Parser[A], p2: Parser[A]): Parser[A] ，它会尝试两个解析器 . （并根据我的风格重写现有的解析器） .

    def choice[A](p1: Parser[A], p2: Parser[A]): Parser[A] = new Parser[A] {
  def apply(s: String): List[(A,String)] = { p1(s) ++ p2(s) }
}

def unit[A](x: A): Parser[A] = new Parser[A] {
  def apply(s: String): List[(A,String)] = List((x,s))
}

val character: Parser[Char] = new Parser[Char] {
  def apply(s: String): List[(Char,String)] = List((s.head,s.tail))
}

    然后，您可以编写如下内容：

    val parser: Parser[(Char,Char)] = for {
  x <- choice(unit('x'),char)
  y <- char
} yield (x,y)

    并且调用 parser("xyz") 会给你 List((('x','x'),"yz"), (('x','y'),"z")) .

    回复于

相关问题