How to express Function type?

Question

I am currently reading Hutton's and Meijer's paper on parsing combinators in Haskell http://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf. For the sake of it I am trying to implement them in scala. I would like to construct something easy to code, extend and also simple and elegant. I have come up with two solutions for the following haskell code

/* 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
}

Question 1

In Haskell, zero is a function value that can be used as it is, expessing all failed parsers whether they are of type Parser[Int] or Parser[String]. In scala we achieve the same by calling the function Zero (1st approach) but in this way I believe that I just generate a different function everytime Zero is called. Is this statement true? Is there a way to mitigate this?

Question 2

In the second approach, the Zero case object is extending Parser with the usage of existential types Parser[T forSome {type T}] . If I replace the type with Parser[_] I get the compile error

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

I thought these two expressions where equivalent. Is this the case?

Question 3

Which approach out of the two do you think that will yield better results in expressing the combinators in terms of elegance and simplicity?

I use scala 2.11.8

Answer 1

Note: I didn't compile it, but I know the problem and can propose two solutions.

1. The more Haskellish way would be to not use subtyping, but to define zero as a polymorphic value. In that style, I would propose to define parsers not as objects deriving from a function type, but as values of one case class:

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

   As shown by @Alec, yes, this will produce a new value every time, since a def is compiled to a method.

2. If you want to use subtyping, you need to make Parser covariant. Then you can give zero a bottom result type:

   trait Parser[+A] extends (String => List[(A, String)])
   case object Zero extends Parser[Nothing] {...}
   

These are in some way quite related; in system F_<:, which is the base of what Scala uses, the types _|_ (aka Nothing) and \/T <: Any. T behave the same (this hinted at in Types and Programming Languages, chapter 28). The two possibilities given here are a consequence of this fact.

With existentials I'm not so familiar with, but I think that while unbounded T forSome {type T} will behave like Nothing, Scala does not allow inhertance from an existential type.

Answer 2

Question 1

I think that you are right, and here is why: Zero1 below prints hello every time you use it. The solution, Zero2, involves using a val instead.

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

Question 2

No idea. I'm still just starting out with Scala. Hope someone answers this.

Question 3

The trait one will play better with Scala's for (since you can define custom flatMap and map), which turns out to be (somewhat) like Haskell's do. The following is all you need.

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

Of course, to do anything interesting you need more parsers. I'll propose to you one simple parser combinator: Choice(p1: Parser[A], p2: Parser[A]): Parser[A] which tries both parsers. (And rewrite your existing parsers more to my style).

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

Then, you can write something like the following:

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

And calling parser("xyz") gives you List((('x','x'),"yz"), (('x','y'),"z")).