In Scala, why can't I implement a trivial generic function like this?

Question

I want a generic function called "double", which behaves like this and could be applied to any type with def +(x:T):T method:

double("A")
> "AA"
double(1)
> 2
double(0.2)
> 0.4

So I write this function like this:

def double[T](x:T):T = { x+x }

But when I run it in REPL, scala compains about it:

scala> def double[T](x:T):T = { x+x }
<console>:7: error: type mismatch;
 found   : T
 required: String
       def double[T](x:T):T = { x+x }
                                  ^

I think structural type may be an approach to implement duck typing, and I tried something like this, but it doesn't work either:

def double[T <: { def +(x:T):T }](x:T):T = { x + x }
def double[T <: { def +[U<:T](x:U):U}](x:T) = { x + x }

Does anyone have ideas about this? Thanks!

---

I found in Haskell, the similar function can be written like this:

double x = x + x

just wondering why I can't do this in Scala...

Answer 1

Not every type T has a + method, so that can't work. The strange error message comes from the compiler treating the first x as a String, because every type has a toString method, and that's the only way it can see a generic T as having +. But then T is being passed to +, instead of String, and it would require a second implicit conversion to allow this to work--and even if we did that, it would return String instead of T.

The problem is that we need a way to provide evidence that T has a + operation. There isn't anything in the standard library that does exactly this, to my knowledge, but we can create a type class that would provide the evidence that a type can be "doubled".

trait CanDouble[A] {
    def double(a: A): A
}

// Create some instances for types we know, like String, or numeric types
implicit val StringDouble: CanDouble[String] = new CanDouble[String] {
    def double(a: String): String = a + a
}

// Uses the Numeric type class to create a CanDouble for all Numeric types
implicit def numericDouble[A: Numeric]: CanDouble[A] = {
    new CanDouble[A] {
         def double(a: A): A = implicitly[Numeric[A]].plus(a, a)
    }
}

Now we can define the double method that requires a evidence of the type class CanDouble.

def double[A: CanDouble](a: A): A = implicitly[CanDouble[A]].double(a)

scala> double(1)
res4: Int = 2

scala> double(0.4)
res5: Double = 0.8

scala> double("a")
res6: String = aa

Ideally, you would put all of the type class instances like StringDouble and numericDouble within the companion object CanDouble.

---

I don't think a structural type can work at all here, because you are not allowed to use an abstract type parameter within the structural refinement that is defined outside of the refinement (the type parameter T). From the SLS:

Within a method declaration in a structural refinement, the type of any value parameter may only refer to type parameters or abstract types that are contained inside the refinement. That is, it must refer either to a type parameter of the method itself, or to a type definition within the refinement. This restriction does not apply to the method's result type.

Structural types should typically be avoided, anyway, as they are quite slow. Type classes should be preferred in this scenario.

Answer 2

In haskell you can:

Prelude> let double x = x + x // (1)
Prelude> let quadruple x = double (double x) //(2)

Prelude> :t double
double :: Num a => a -> a
Prelude> :t quadruple
quadruple :: Num a => a -> a

In scala you have to specify Num explicitly

scala> def double[T: Numeric] (a: T) = implicitly[Numeric[T]].plus(a, a)
double: [T](a: T)(implicit evidence$1: Numeric[T])T

scala> def quadruple[T: Numeric](a: T) = double(double(a))
quadruple: [T](a: T)(implicit evidence$1: Numeric[T])T

Because haskell's type inferrence is smarter. (1)st line did find typeclass Num:

Prelude> :info Num
class Num a where
  (+) :: a -> a -> a //looks like structural types, but ...
  (*) :: a -> a -> a
  (-) :: a -> a -> a
  negate :: a -> a
  abs :: a -> a
  signum :: a -> a
  fromInteger :: Integer -> a
    -- Defined in ‘GHC.Num’ //... but here is implementations found accross build - they are explicitly saying that they are instances of Num

instance Num Integer -- Defined in ‘GHC.Num’
instance Num Int -- Defined in ‘GHC.Num’
instance Num Float -- Defined in ‘GHC.Float’
instance Num Double -- Defined in ‘GHC.Float’

Also Scala has problems with structural types - you can't define polymorphic structural type (not only this - you ca not define polymorphic lambdas) "Parameter type in structural refinement may not refer to an abstract type defined outside that refinement"

Otherwise Num would be defined in Scala as something like that:

implicit class Num[T <: { def +(x:T):T }](a: T) = ... //will not work, and pretty slow by the way

See other answers to find out how it's really defined (Numeric).

In the (2)nd line compiler inferred input type for x (Num x) from double's application. Scala just can't do that. Its analog to the haskell's Num would be:

scala> trait Num[T]{ val a: T; def + (b: Num[T]): Num[T] }
defined trait Num

scala> implicit class NumInt(val a: Int) extends Num[Int] {override def + (b: Num[Int]) = NumInt(a + b.a)}
defined class NumInt

scala> def double[T](a: Num[T]) = a + a
double: [T](a: Num[T])Num[T]

scala> double(5)
res4: Num[Int] = NumInt@424f5762

But the problem is still same - you have to specify input types (a: Num[T]) in scala, it cannot infer them.

However, even in Haskell you can't let's say:

Prelude> let double x = x +++ x

<interactive>:28:18:
    Not in scope: ‘+++’
    Perhaps you meant ‘++’ (imported from Prelude)
Otherwise `Num` would be defined in Scala as something like that:

And Haskell's real duck typing is not so easy to use: http://chrisdone.com/posts/duck-typing-in-haskell

Answer 3

This is a perfect example of when to use typeclasses.

+ is just a function. You've given the compiler no information such as

def +(t : T, t : T) : T = ...

And you couldn't, because you don't have any idea what a T is.

Here it would work as follows. You have a type constructor, called Doubles:

trait Doubles[T]{
  def double(t : T) : T
}

Now in a companion object, just for convenience, I'm going to rewrite your double function as follows:

object Doubles{
  def double[T](t : T)(implicit doubles : Doubles[T]) =    doubles.double(t)
}

So this says, I can double a T, as long as there's a Doubles for T in scope, or you explicitly provide me with a Doubles for T. Otherwise, I won't be able to double a T, and you'll get a compiler error.

The following are going to be instances of that typeclass Doubles[T]:

object Implicits{
    //Now, you wouldn't want to have to write this for 
    //every kind of number.  Scala already provides you with a numeric
    //typeclass.  So here's a function that gives a Doubles[N] 
    //whenever you ask for a Doubles[Numeric[T]], i.e. a Doubles for a     
    //member of the Numeric typeclass:

    implicit def numDoubler[N](implicit num : Numeric[N]) : Doubles[N] = new Doubles[N]{
        def double(n : N) : N = num.plus(n,n)
    }

    implicit object stringDoubler extends Doubles[String]{
        def double(t : String) : String = t + t
    }

 //So something like this is no longer needed:
 // implicit object intDoubler extends Doubles[Int]{
 //   def double(t : Int) : Int = t + t
 // }

}