scala - 如何表达函数类型？

Question

我目前正在阅读 Hutton 和 Meijer 关于在 Haskell 中解析组合器的论文 http://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf .为此，我试图在 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
}

问题一

在 Haskell 中，零是一个可以按原样使用的函数值，表示所有失败的解析器，无论它们是类型 Parser[Int] 还是 Parser[String]。在 scala 中，我们通过调用函数零(第一种方法)来实现相同的目的，但我相信通过这种方式，每次调用零时我都会生成一个不同的函数。这个说法是真的吗？有没有办法缓解这种情况？

问题2

在第二种方法中，零案例对象通过使用存在的 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

Answer 1

注:我没有编译，但我知道问题所在，可以提出两种解决方案。

1. 更 Haskellish 的方式是不使用子类型，而是定义 zero作为多态值。在这种风格下，我建议将解析器定义为不 object s 派生自函数类型，但作为一个案例类的值:

   final case class Parser[T](run: String => List[(T, String)])
   def zero[T]: Parser[T] = Parser(...)
   

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

2. 如果你想使用子类型，你需要制作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 不允许从现有类型继承。