jhegedus
jhegedus

Reputation: 20653

Why does Scala not have a return/unit function defined for each monad (in contrast to Haskell)?

What is the reason behind the design decision in Scala that monads do not have a return/unit function in contrast to Haskell where each monad has a return function that puts a value into a standard monadic context for the given monad?

For example why List, Option, Set etc... do not have a return/unit functions defined in the standard library as shown in the slides below?

I am asking this because in the reactive Coursera course Martin Odersky explicitly mentioned this fact, as can be seen below in the slides, but did not explain why Scala does not have them even though unit/return is an essential property of a monad.

enter image description here enter image description here enter image description here

Upvotes: 28

Views: 4488

Answers (4)

Cyäegha
Cyäegha

Reputation: 4251

I don't think you're really saying that Scala's monads don't have a unit function - it's rather just that the name of the unit function can vary. That's what seems to be shown in the second slide's examples.

As for why that is so, I think it's just because Scala runs on the JVM, and those function have to be implemented as JVM methods - which are uniquely identified by:

  • the class they belong to;
  • their name;
  • their parameters types. But they are not identified by their return type. Since the parameter type generally won't differentiate the various unit functions (it's usually just a generic type), you need different names for them.

In practice, they will often be implemented as the apply(x) method on the companion object of the monad class. For example, for the class List, the unit function is the apply(x) method on the object List. By convention, List.apply(x) can be called as List(x) too, which is more common/idiomatic.

So I guess that Scala at least has a naming convention for the unit function, though it doesn't have a unique name for it :

// Some monad :
class M[T] {
  def flatMap[U](f: T => M[U]): M[U] = ???
}
// Companion object :
object M {
  def apply(x: T): M[T] = ??? // Unit function
}

// Usage of the unit function :
val x = ???
val m = M(x)

Upvotes: 9

ayvango
ayvango

Reputation: 5977

Actually there is a return function in scala. It is just hard to find.

Scala slightly differs from Haskell in many aspects. Most of that differences are direct consequences of JVM limitations. JVM can not dispatch methods basing on its return type. So Scala introduced type class polymorphism based on implicit evidence to fix this inconvenience.

It is even used in scala standard collections. You may notice numerous usage of CanBuildFrom and CanBuild implicits used in the scala collection api. See scala.collection.immutable.List for example.

Every time you want to build custom collection you should write realization for this implicits. There are not so many guides for writing one though. I recommend you this guide. It shows why CanBuildFrom is so important for collections and how it is used. In fact that is just another form of the return function and anyone familiar with Haskell monads would understand it's importance clearly.

So you may use custom collection as example monads and write other monads basing on provided tutorial.

Upvotes: 1

Vladimir Matveev
Vladimir Matveev

Reputation: 128171

As Ørjan Johansen said, Scala does not support method dispatching on return type. Scala object system is built over JVM one, and JVM invokevirtual instruction, which is the main tool for dynamic polymorphism, dispatches the call based on type of this object.

As a side note, dispatching is a process of selecting concrete method to call. In Scala/Java all methods are virtual, that is, the actual method which is called depends on actual type of the object.

class A { def hello() = println("hello method in A") }

class B extends A { override def hello() = println("hello method in B") }

val x: A = new A
x.hello()  // prints "hello method in A"

val y: A = new B
y.hello()  // prints "hello method in B"

Here, even if y variable is of type A, hello method from B is called, because JVM "sees" that the actual type of the object in y is B and invokes appropriate method.

However, JVM only takes the type of the variable on which the method is called into account. It is impossible, for example, to call different methods based on runtime type of arguments without explicit checks. For example:

class A {
  def hello(x: Number) = println(s"Number: $x")
  def hello(y: Int) = println(s"Integer: $y")
}

val a = new A
val n: Number = 10: Int
a.hello(n)  // prints "Number: 10"

Here we have two methods with the same name, but with different parameter type. And even if ns actual type is Int, hello(Number) version is called - it is resolved statically based on n static variable type (this feature, static resolution based on argument types, is called overloading). Hence, there is no dynamic dispatch on method arguments. Some languages support dispatching on method arguments too, for example, Common Lisp's CLOS or Clojure's multimethods work like that.

Haskell has advanced type system (it is comparable to Scala's and in fact they both originate in System F, but Scala type system supports subtyping which makes type inference much more difficult) which allows global type inference, at least, without certain extensions enabled. Haskell also has a concept of type classes, which is its tool for dynamic polymorphism. Type classes can be loosely thought of as interfaces without inheritance but with dispatch on parameter and return value types. For example, this is a valid type class:

class Read a where
    read :: String -> a

instance Read Integer where
    read s = -- parse a string into an integer

instance Read Double where
    read s = -- parse a string into a double

Then, depending on the context where method is called, read function for Integer or Double can be called:

x :: Integer
x = read "12345"  // read for Integer is called

y :: Double
y = read "12345.0"  // read for Double is called

This is a very powerful technique which has no correspondence in bare JVM object system, so Scala object system does not support it too. Also the lack of full-scale type inference would make this feature somewhat cumbersome to use. So, Scala standard library does not have return/unit method anywhere - it is impossible to express it using regular object system, there is simply no place where such a method could be defined. Consequently, monad concept in Scala is implicit and conventional - everything with appropriate flatMap method can be considered a monad, and everything with the right methods can be used in for construction. This is much like duck typing.

However, Scala type system together with its implicits mechanism is powerful enough to express full-featured type classes, and, by extension, generic monads in formal way, though due to difficulties in full type inference it may require adding more type annotations than in Haskell.

This is definition of monad type class in Scala:

trait Monad[M[_]] {
  def unit[A](a: A): M[A]
  def bind[A, B](ma: M[A])(f: A => M[B]): M[B]
}

And this is its implementation for Option:

implicit object OptionMonad extends Monad[Option] {
  def unit[A](a: A) = Some(a)
  def bind[A, B](ma: Option[A])(f: A => Option[B]): Option[B] =
    ma.flatMap(f)
}

Then this can be used in generic way like this:

// note M[_]: Monad context bound
// this is a port of Haskell's filterM found here:
// http://hackage.haskell.org/package/base-4.7.0.1/docs/src/Control-Monad.html#filterM
def filterM[M[_]: Monad, A](as: Seq[A])(f: A => M[Boolean]): M[Seq[A]] = {
  val m = implicitly[Monad[M]]
  as match {
    case x +: xs =>
      m.bind(f(x)) { flg =>
        m.bind(filterM(xs)(f)) { ys =>
          m.unit(if (flg) x +: ys else ys)
        }
      }
    case _ => m.unit(Seq.empty[A])
  }
}

// using it

def run(s: Seq[Int]) = {
  import whatever.OptionMonad  // bring type class instance into scope

  // leave all even numbers in the list, but fail if the list contains 13
  filterM[Option, Int](s) { a =>
    if (a == 13) None
    else if (a % 2 == 0) Some(true)
    else Some(false)
  }
}

run(1 to 16)  // returns None
run(16 to 32)  // returns Some(List(16, 18, 20, 22, 24, 26, 28, 30, 32))

Here filterM is written generically, for any instance of Monad type class. Because OptionMonad implicit object is present at filterM call site, it will be passed to filterM implicitly, and it will be able to make use of its methods.

You can see from above that type classes allow to emulate dispatching on return type even in Scala. In fact, this is exactly what Haskell does under the covers - both Scala and Haskell are passing a dictionary of methods implementing some type class, though in Scala it is somewhat more explicit because these "dictionaries" are first-class objects there and can be imported on demand or even passed explicitly, so it is not really a proper dispatching as it is not that embedded.

If you need this amount of genericity, you can use Scalaz library which contains a lot of type classes (including monad) and their instances for some common types, including Option.

Upvotes: 36

Chris Martin
Chris Martin

Reputation: 30756

Caveat: I'm still learning Haskell and I'm sort of making up this answer as I go.


First, what you already know - that Haskell's do notation desugars to bind:

Borrowing this example from Wikipedia:

add mx my = do
  x <- mx
  y <- my
  return (x + y)

add mx my =
  mx >>= (\x ->
    my >>= (\y ->
      return (x + y)))

Scala's analogue to do is the for-yield expression. It similarly desugars each step to flatMap (its equivalent of bind).

There's a difference, though: The last <- in a for-yield desugars to map, not to flatMap.

def add(mx: Option[Int], my: Option[Int]) =
  for {
    x <- mx
    y <- my
  } yield x + y

def add(mx: Option[Int], my: Option[Int]) =
  mx.flatMap(x =>
    my.map(y =>
      x + y))

So because you don't have the "flattening" on the last step, the expression value already has the monad type, so there's no need to "re-wrap" it with something comparable to return.

Upvotes: 5

Related Questions