Problem with Parser Monad

[boris....@gmail.com]

I have the following problems with my parser monad:

1. I get a compiler error when I try to inherit it from my Monad trait.
2. I want bind to be an infix operator.
   

Someone proposed a solution on Stackoverflow, but it doesn't compile either https://stackoverflow.com/questions/1992532/monad-trait-in-scala

trait Monad[M[A]] {
  def unit[A](a: A): M[A]
  def bind[A, B](m: M[A])(f: A => M[B]): M[B]
}
   
class Parser[A] extends Monad[String => List[(A,String)]] { // doesn't compile
    type P[A] = String => List[(A,String)]
   
    def unit[A](a: A)(s: String) = List((a,s))
   
    def bind[A,B](ma: P[A])(f: A => P[B]): P[B] = {(s: String) =>
        ma(s) flatMap {case (a,t) => f(a)(t)}
    }
}

[Brian Maso]

The error is that the type String => List[(A, String)} cannot be bound to the type parameter of Monad, which you've declared as "M[A]". That is, you need to provide a type that has exactly 1 type parameter. String => List[(A, String)] does not conform to the Monad requirements.

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

Best regards,
Brian Maso
(949) 395-8551
Follow me: @bmaso
br...@blumenfeld-maso.com

[boris....@gmail.com]

In class Parser, I defined P[A] = String => List[(A,String)], which doesn't produce an error. Doesn't this mean that String => List[(A,String)] has one type parameter, namely A?

[boris....@gmail.com]

I've now arrived at this somewhat clumsy solution, which allows infix syntax for bind. However, I don't see how I can define a monad trait to inherit from.

class Parsers {
    case class Parser[A](parse: String => List[(A, String)]) {
        def apply(s: String) = parse(s)
   
        def bind[B](f: A => Parser[B]) = Parser[B] {(s: String) =>
            parse(s) flatMap {case (a,t) => f(a)(t)}
        }
    }

    def unit[A](a: A) = Parser[A] {(s: String) =>
        List((a, s))
    }   
}

[Jasper-M]

Monad requires a type constructor, or a type with a hole in it. In standard Scala there are 2 ways to do this.

trait Monad[M[A]] { ... }
    
class Parser1 extends Monad[({type L[A] = String => List[(A,String)]})#L] { ... }

object Foo { type L[A] = String => List[(A,String)] }

class Parser2 extends Monad[Foo.L]

Op woensdag 22 juni 2016 10:17:03 UTC+2 schreef boris....@gmail.com:

[boris....@gmail.com]

Neither works. I get

class Parser needs to be abstract, since method unit in trait Monad of type [A](a: A) Foo.L[A] is not defined (Note that A does not match A) 

What does #L mean in the first example?

[Viktor Klang]

It's a type projection so that you get a type constructor to satisfy the parameter requirement of your Monad trait (through the type lambda: ({type L[A] = String => List[(A,String)]})#L)

More reading: https://stackoverflow.com/questions/8736164/what-are-type-lambdas-in-scala-and-what-are-their-benefits

--

You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

Cheers,

√

[boris....@gmail.com]

Thanks for the explanation of the type lambda. Still, it doesn't compile:

trait Monad[M[A]] {
  def unit[A](a: A): M[A]
}

class Parser1[A] extends Monad[({type L[A] = String => List[(A,String)]})#L] {

    def unit[A](a: A)(s: String) = List((a,s))
}

class Parser1 needs to be abstract, since method unit in trait Monad of type [A](a: A)String => List[(A, String)] is not defined (Note that A does not match A)

[Juha Heljoranta]

The compile error message describes the problem: method is not defined.
When method is defined, it works:

def unit[A](a: A): String => List[(A,String)] = s => List((a,s))

Sometimes complex method definitions/signatures can be bit challenging to get
right. One trick which I use quite often is ??? operator. e.g. I might have
worked in incremental steps like this to see that if it keeps compiling:

override def unit[A](a: A) = ???
override def unit[A](a: A): String => List[(A,String)] = ???
override def unit[A](a: A): String => List[(A,String)] = s => List((a, s))

Cheers,
Juha

[Viktor Klang]

Thanks Juha,

also, one thing that confuses is to use "A" as the type parameter name for the type constructor:

trait Monad[M[A]] {
  def unit[A](a: A): M[A]
}

Most specifically because A will be different within unit due to the type parameter on the unit method definition.

So:

trait Monad[M[_]] {

  def unit[A](a: A): M[A]
}

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

Cheers,

√

[boris....@gmail.com]

Thanks, that solves the first problem. However, the error message is misleading because I defined unit, but not with the type Scala requires.

But why is

    def unit[A](a: A)(s: String) = List((a,s))

different to

    def unit[A](a: A) = (s: String) => List((a,s))

Both should have type A => String => List[(A, String)]

[Viktor Klang]

On Wed, Jun 22, 2016 at 4:02 PM, <boris....@gmail.com> wrote:

Thanks, that solves the first problem. However, the error message is misleading because I defined unit, but not with the type Scala requires.

unit in trait Monad of type [A](a: A)String => List[(A, String)] is not defined

It is slightly confusing, yes. IMO it would've been clearer with:

unit in trait Monad of type [A](a: A): String => List[(A, String)] is not defined

 

But why is

    def unit[A](a: A)(s: String) = List((a,s))

This is a method with multiple parameter lists, which returns a List

 

different to

    def unit[A](a: A) = (s: String) => List((a,s))

This is a method which returns a function from a string to a List

 

Both should have type A => String => List[(A, String)]

No, methods and functions are distinct concepts.

 

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

Cheers,

√

[Viktor Klang]

On Wed, Jun 22, 2016 at 4:18 PM, <boris....@gmail.com> wrote:

Why can the A in Monad[M[A]] be different from the A in unit[A]?
I want to ensure that unit has type
M a -> (a -> M b) -> M b
where M is the monad, eg Option or List.

One is a type parameter to the class, the other a type parameter to the method.

 

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

Cheers,

√

[boris....@gmail.com]

All right, now I can inherit from Monad. How do i solve the second problem, making bind an infix operator?
I've solved this with my approach above, which consists of on outer class Parsers with all unary functions and an inner case class Parser[A] for the infix operators. However, Parser can't inherit from Monad[Parser] because Parser is an inner class.

[Roland Kuhn]

You seem to be coming towards Scala from a rather difficult angle. Perhaps it helps to point out that Scala and Haskell take very different approaches in their type system, implementation, syntax, etc. and in general it is not possible to “write Haskell in Scala”—things that express the same concept will look quite differently between the two and things that are very closely similar in Haskell may differ significantly in Scala. What I mean to say is that it might be beneficial to first study the Scala syntax and type constructs before diving into the advanced parts—because the valuation of what is normal also differs between the two languages.

22 juni 2016 kl. 16:18 skrev boris....@gmail.com:

Why can the A in Monad[M[A]] be different from the A in unit[A]?
I want to ensure that unit has type
M a -> (a -> M b) -> M b

Technical detail: this is bind, not unit ;-)

In any case, there are several differences you will encounter that are linked to the design choices of the underlying runtime system, i.e. the JVM shines through in the case of Scala (which is a reason why methods and functions are not always equivalent as you discovered).

Regards,

Roland

where M is the monad, eg Option or List.

[Naftoli Gugenheim]

On Mon, Jun 20, 2016, 12:38 PM <boris....@gmail.com> wrote:

I have the following problems with my parser monad:

1. I get a compiler error when I try to inherit it from my Monad trait.
2. I want bind to be an infix operator.
   

Someone proposed a solution on Stackoverflow, but it doesn't compile either https://stackoverflow.com/questions/1992532/monad-trait-in-scala

trait Monad[M[A]] {
  def unit[A](a: A): M[A]
  def bind[A, B](m: M[A])(f: A => M[B]): M[B]
}
   
class Parser[A] extends Monad[String => List[(A,String)]] { // doesn't compile
    type P[A] = String => List[(A,String)]
   
    def unit[A](a: A)(s: String) = List((a,s))

Your monad instance generally shouldn't be a polymorphic class, it should be a single instance. If Parser is a monad then there be a Parser class, plus an implicit object of type Monad[Parser]. If you think about it, it has to be this way because:

 - You shouldn't need to instantiate something to call unit, it's basically a global function (per monad)

 - A Parser instance needs to know its A, but the monad instance doesn't

Etc.

   
    def bind[A,B](ma: P[A])(f: A => P[B]): P[B] = {(s: String) =>
        ma(s) flatMap {case (a,t) => f(a)(t)}
    }
}

[boris....@gmail.com]

Am Montag, 27. Juni 2016 03:23:41 UTC+2 schrieb nafg:

Your monad instance generally shouldn't be a polymorphic class, it should be a single instance. If Parser is a monad then there be a Parser class, plus an implicit object of type Monad[Parser]. If you think about it, it has to be this way because:

 - You shouldn't need to instantiate something to call unit, it's basically a global function (per monad)

 - A Parser instance needs to know its A, but the monad instance doesn't

Why should the parser monad be a single instance? I need type A to accomplish for the different purposes of the parser. Eg, if I want to compute expressions of type Double, I need a parser of type String => List[(Double, String)].

I now have a class Parser[A] that contains bind and outside of this a function unit that maps to Parser[A]. I can't inherit this from trait Monad[A], though.

[Jed Wesley-Smith]

> Why should the parser monad be a single instance?

Because you are not actually instantiating it for each different Parser[Foo], you implement it once as Monad[Parser]. The type parameter for Monad is unary kinded (ie. * -> *), as is Parser[A], so you only give it Parser, you don't pass in the simple kinded Parser[Foo]

Where the confusion lies (as was somewhat subtly pointed out earlier) is that the type parameter to Monad is declared as M[A], but the A here is meaningless and misleading – it shares nothing with the A type parameters to unit and bind. What you really have is an existential type parameter M[_], and you instantiate that in the methods where it is used.

Normally, the Parser companion object would contain the concrete, implicit instance  of Monad[Parser], and then you can look it up from the implicit context when needed:

    val M: Monad[Parser] = implicitly[Monad[Parser]]

You don't need Parser to inherit from Monad.

--

[boris....@gmail.com]

My current solution is this:

class Parsers {
    case class Parser[A](parse: String => List[(A, String)]) {
        def apply(s: String) = parse(s)
   
        def bind[B](f: A => Parser[B]) = Parser[B] {(s: String) =>
            parse(s) flatMap {case (a,t) => f(a)(t)}
        }
   
    def unit[A](a: A) = Parser[A] {(s: String) =>
        List((a, s))
    }
}

I'm afraid it's not possible to much improve upon this in Scala. The biggest problem is that Scala doesn't have infix operators, these must be methods. It's easier to do this in Haskell and Ocaml.

[Patrick Roemer]

Responding to boris....@gmail.com:

> class Parsers {
> case class Parser[A](parse: String => List[(A, String)]) {
> def apply(s: String) = parse(s)
>
> def bind[B](f: A => Parser[B]) = Parser[B] {(s: String) =>
> parse(s) flatMap {case (a,t) => f(a)(t)}
> }
>
> def unit[A](a: A) = Parser[A] {(s: String) =>
> List((a, s))
> }
> }

I'm not sure I understand your intention correctly, but maybe you're
aiming for something like this?

A monad "type class":

trait Monad[M[_]] {

def unit[A](a: A): M[A]
def bind[A, B](m: M[A])(f: A => M[B]): M[B]
}

The parser. Not sure about the role of the List in your example - here
the Option signals parse success (Some) or failure (None).

case class ParseResult[A](parsed: A, remain: String)
trait Parser[A] extends Function1[String, Option[ParseResult[A]]]

A monad implementation in the Parser companion object.

implicit object ParserMonad extends Monad[Parser] {
override def unit[A](a: A) =
new Parser[A] {
override def apply(s: String) = Some(ParseResult(a, s))
}
override def bind[A, B](m: Parser[A])(f: A => Parser[B]): Parser[B] =
new Parser[B] {
override def apply(s: String): Option[ParseResult[B]] =
m(s).flatMap(r => f(r.parsed)(r.remain))
}
}

Finally, an implicit class in the Monad companion that provides #bind as
a method on any "monadified" type, using the canonical Scala name to
make it applicable in for expressions.

implicit class ScalaAdaptedMonad[A, M[_] : Monad](m: M[A]) {
private def monad: Monad[M] = implicitly[Monad[M]]
def flatMap[B](f: A => M[B]): M[B] = monad.bind(m)(f)
def map[B](f: A => B): M[B] = monad.bind(m)(a => monad.unit(f(a)))
}

Now, given some Parser implementations, they can be combined like this:

import Monad._
import Parser._

val p =
for {
a <- rep(char('a'))
b <- char('b')
c <- rep1(char('c'))
_ <- end
} yield (a ++ (b +: c)).mkString

p("abcc") // Some(ParseResult(abcc,))
p("abcx") // None

There certainly are other (and probably better or at least more elegant)
approaches, but this would work for me.

Best regards,
Patrick

[boris....@gmail.com]

Lists are useful to combine parse results, see Wadler's original paper on the subject.
I better use Haskell or Ocaml for monadic parsers, the syntax is much easier and clearer.