Statically Typed

because Hindley-Milner rocks

Solution in Scala to the Previous Post

My previous solution in terms of Scala was being hamstrung by the type system, sorta.  I’m a big fan of Hindley-Milner type inference and Scala lacks a complete implementation.  It is still tied to the wonderful Java type system upon which Scala is built.  In order to access the world of all those Java libraries some sacrifices had to be made and one of them was the use of Java Generics.  (James Iry, of One Div Zero, clarifies my inaccuracies below in his comment.)

So what, exactly, was holding me up?  Simple:

def MySimpleFunction[A<:AnyVal]( _input:List[A], _values:List[A],
                                 _max:A, _location:MaxInfo ) =
    _input match {
        case x :: Nil =>
!           val sum = x + _values.head

that’s it.  Here, the Scala compiler is attempting to convert things to java.lang.String where “+” is defined but later on encountering an issue with a recursive call back to the “MySimpleFunction.”

That’s as far as I could get because generics in Java are much, much different from templates in C++.  This is something I need to continue to remind myself.  In C++ templates are essentially macros wherein the compiler checks to make sure the operations and member function calls make sense.  In Java, there’s no way for the compiler to know future uses.  Hence the Scala compiler doesn’t know if the variable type “A” will have a unary function “+”.  Even deriving from AnyVal does not provide the needed functions.

My solution was to create a trait which had all the overloaded operators I needed:

trait TwoOps{
    def +( _in:TwoOps ): TwoOps
    def >( _in:TwoOps ): Boolean

Then instead of deriving from AnyVal, I derived from TwoOps.  Now the Scala compiler understands that everything I will be using will have a unary operator “+” and boolean operator “>.”  Well, that is until I attempt to pass in a List[Int].  Hrmph!  Guess it can’t implicitly convert from Int to TwoOps because Int has several different unary “+” operators.  It doesn’t know which one to choose.  I’m liking Scala less and less with each passing day but it sure is more powerful than other languages on the JVM (opinion.)  Can’t have it all, eh?

Stack Overflow already answered one question for me as I attempted to recreate this solution in Scala.  I have a sneaking suspicion they can answer my next question too.


6 comments on “Solution in Scala to the Previous Post

  1. Ittay
    April 18, 2010

    You need a class that abstracts the ‘+’ method. Then implement it for the various types you’re interested in. Then, if you have implicit values for these implementations, then your method can use it:

    object Summation {
    trait Summable[A] {def sum(a1: A, a2: A): A}

    implicit object IntSum extends Summable[Int] {override def sum(i1: Int, i2: Int) = i1 + i2}

    // more such objects

    import Summation._
    def MySimpleFunction[A
    val sum = s.sum(x, _values.head)
    // rest of the method

    You can add a Comparable[A] trait to compare numbers etc.

    The cool thing about Scala is the implicit arguments which means users of the method don’t need to worry about where they are defined (just import the object)

  2. Pingback: Dynamic Problem Solution in Scala « Statically Typed

  3. James Iry
    April 18, 2010

    I just wanted to pop in and clarify a couple of things.

    Scala doesn’t have HM type inference because it has a type system that’s too sophisticated for the HM algorithm. It’s still an open research question as to just how much type reconstruction is possible under type systems like Scala’s, but whatever the final answer is it will never be the HM algorithm and it’s almost certainly never going to be full reconstruction.

    Also, Java’s “generics” and Scala’s parametric polymorphism are more closely related to the kinds of parametric polymorphism found in ML and other HM languages than C++’s templates are. C++ templates are outliers in the space of type system design – it’s in fact very hard to give a clean type theoretical semantics to C++ templates where it’s much, much easier to do so for Java (and Scala).

    In ML, Java, C#, Haskell, and Scala a function/method f parametrized by type t without qualification says that “for all types t there exists a function f such that…” In C++, a function/method f parameterized by type t only says “for all types t such that the expansion of this template compiles there exists a function f such that…” In other words, C++ templates create pretty arbitrarily sophisticated bounds on the type t but do it implicitly. That’s powerful stuff, but very hard to reason about. One eminently practical consequence is that type parameter errors in C++ tend to make compilers throw up pages of stuff because it’s not clear where the problem is. Another consequence is the general lack of separate compilation in C++ – in order to know if a type parameter works the code using a template needs to know if the template will compile when expanded. Compare that with the much simpler error messages involved when you screw up an ML type parameter or the ease with which Java handles separate compilation. It’s no surprise that C++ remains one of the very tiny fraction of languages that have gone down the route of templates for type abstraction.

    • owreese
      April 19, 2010

      Holy crap it’s James Iry on my blog! I’m honored. I read your blog. You’re coding in Scala now too? Scala’s type system is too powerful for HM? I never thought about what limitations HM might impose on a type system. Well I gotta correct that in my post. Thanks for pointing that out.

      • James Iry
        April 19, 2010

        I’ve been playing with Scala since 2007

        As for HM’s restrictions, it’s basically System F with the restriction that polymorphism is limited to rank 1. Scala’s type system is at least in the general neighborhood of System F<: and System Fω plus it some limited dependent typing.

      • owreese
        April 19, 2010

        Yes, yes you have. Now I remember why I read your blog in the first place, it was mentioned at our Scala group. Forgive my ignorance. I’m still really flattered that someone I read was over at my blog, helping me understand more.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


This entry was posted on April 17, 2010 by in Intervew Questions, Scala.
%d bloggers like this: