how to translate Haskell into Scalaz?

Question

One of my high school students and I are going to try to do a port of Haskell's Parsec parser combinator library into Scala. (It has the advantage over Scala's built-in parsing library that you can pass state around fairly easily because all the parsers are monads.)

The first hitch I've come across is trying to figure out how Functor works in scalaz. Can someone explain how to convert this Haskell code:

data Reply s u a = Ok a !(State s u) ParseError
                 | Error ParseError


instance Functor (Reply s u) where
    fmap f (Ok x s e) = Ok (f x) s e
    fmap _ (Error e) = Error e -- XXX

into Scala (using Scalaz, I assume). I got as far as

sealed abstract class Reply[S, U, A]
case class Ok[S, U, A](a: A, state: State[S, U], error: ParseError)
    extends Reply[S, U, A]
case class Error[S, U, A](error: ParseError) extends Reply[S, U, A]

and know that I should make Reply extend the scalaz.Functor trait, but I can't figure out how to do that. (Mostly I'm having trouble figuring out what the F[_] parameter does.)

Any help appreciated!

Thanks, Todd

Based on dflemstr's answer, I came up with this:

sealed abstract class Reply[S, U, A]
object Reply {
  implicit def ReplyFunctor[S, U]  = {
    type ReplySU[A] = Reply[S, U, A]
    new Functor[ReplySU] {
      def fmap[A, B](r: ReplySU[A], f: A => B) = r match {
        case Ok(a, state, error) => Ok(f(a), state, error)
        case Error(error) => Error[S, U, B](error)
      }
    }
  }
}
case class Ok[S, U, A](a: A, state: State[S, U], error: ParseError) 
    extends Reply[S, U, A]()
case class Error[S, U, A](error: ParseError) extends Reply[S, U, A]()

What I'm not sure about is that ReplySU[A] type. The actual Functor in Haskell is Reply s u with curried types and the a type missing. Is this how I should do the same thing in Scala or am I overly complicating things?

Scala parsers are monads too ! A Scala monad is any object with implementations for map and flatMap methods (provided they satisfy monad axioms). — paradigmatic
It looks like you've already got your answer, but for future, feel free to drop in. irc://freenode.net/#scalaz — Tony Morris

dflemstr dflemstr · Accepted Answer · 2012-03-30T10:41:46

In Functor[F[_]], the F means that it is a type constructor, that is, a parameterized type that must take some other type as a parameter to become a fully qualified type. For instance, if F is List, then List[Int] is a type instance of that parameterized type.

So when you define a value of type Functor[List], it means that it is an object describing the functor nature of Lists, and that the functor object will use the higher-order type List to construct various type instances, such as List[A] and List[B].

Further, you must understand the difference between Scala's classes and Haskell's classes. A class instance in Haskell is best modeled by an implicit value in Scala, rather than the implementation of an interface; while you need an instance of an object to also have an instance of an interface in Java/Scala, you can have an instance of a class in Haskell without having an instance of the type of value that the class deals with.

Imagine, for example, how you would implement the Read class from Haskell in Scala. The Read class deserializes values from strings; there is a function called read with type Read a => String -> a so for any type a which has a Read instance, you can convert a String into an instance of type a. If you model it using an interface in Scala, such that class Foo implements Read[Foo], how would you then convert a string into an instance of Foo? You can't call Foo.read because you don't have a Foo yet; the read function is supposed to return one!

Instead, you create a separate ReadFoo: Read[Foo] object that contains the implementations of the functions of Read for the type Foo. Then you can call ReadFoo.read(string: String): Foo and get a Foo back type-safely.

For a functor instance, what you need is the following:

// All implicits in the companion object of Reply are automatically brought into
// scope when Reply is imported
object Reply {
  // Describes how to treat a `Reply` as a functor
  implicit val ReplyFunctor: Functor[Reply] = new Functor[Reply] {
    def fmap[A, B](r: Reply[A], f: A => B) = r match {
      case Ok(x, s, e) => Ok(f(x), s, e)
      case err         => err // leave value unchanged
    }
  }
}

how to translate Haskell into Scalaz?

2 Answers