1 Apr 2008 05:12

Stanford Scala Class

```The first meeting of the Stanford Scala Class (CS 94SI) will be this
Wednesday, April 2 from 4:15pm to 5:45pm at the Gates Computer Science
Building (353 Serra St, Stanford CA), Room B12. Auditors are welcome.

Unfortunately, due to logistical and legal complications, we will be
unable to make videos of the class available online.

http://www.stanford.edu/class/cs94si/

Thank you,

CS 94SI Course Staff
Ben Newman
Jorge Ortiz
Julien Wetterwald

```
1 Apr 2008 12:08

Question regarding Variance and Type Bounds

Hello Folks,

I was just trying to write a simple Binary Search Tree and I seem to have hit upon a roadblock. Was wondering if somebody might be able to lend a hand..

So.. what I initially tried to do was create an abstract BSTree and associated case classes like so :

abstract class BSTree[+T]
case object Nil extends BSTree[Nothing]
case class Node[T](l: BSTree[T], e: T, r: BSTree[T]) extends BSTree[T]

and then i define a travese method like so :

def traverse[T](t: BSTree[T]):Unit = t match {
case Nil => println("Nil")
case Node(l, e, r) => { traverse(l); println("Element : " + e); traverse(r) }
}

now all is fine.. untill i try to define an add method like so :
(I need to ensure that only object inheriting from Ordered Trait can be add to a Tree..)

def add[T <: Ordered[T]](t: BSTree[T], x: T): BSTree[T] = t match {
case Nil => Node(Nil, x, Nil)
case Node(l, e, r) => if (x < e) Node(add(l, x), e, r) else Node(l, e, add(r, x))
}

to which the compiler spews the following :
<console>:10: error: inferred type arguments [Any] do not conform to method add's type parameter bounds [T <: Ordered[T]]
case Node(l, e, r) => if (x < e) Node(add(l, x), e, r) else Node(l, e, add(r, x))

But then... i CANT remove the Type bound from the method like :
def add[T](t: BSTree[T], x: T): BSTree[T].....
cuz
i need to do '(x < e)'...

any suggestions ?

Regards
Arun

1 Apr 2008 12:25

Re: Question regarding Variance and Type Bounds

```Arun Suresh wrote:
>
> any suggestions ?

It compiles for me without any errors.  What version of Scala are you
using?  Since the error you receive is related to inference you could
try changing

case Node(l, e, r) =>
if (x < e) Node(add(l, x), e, r) else Node(l,  e, add(r, x))

to

case Node(l, e, r) =>
if (x < e) Node(add[T](l, x), e, r) else Node(l,  e, add[T](r, x))

```
1 Apr 2008 12:45

Limited type inference (was: Question regarding Variance and Type Bounds)

```Arun Suresh schrieb:
> I seem to have hit upon a roadblock.

Your current problem has nothing to do with variance and bounds, you just
overestimated the type inferencer. Change that line:

>     case Nil => Node(Nil, x, Nil)

to
case Nil => Node(Nil: BSTree[T],x,Nil: BSTree[T])

The same thing happens if you try to fold with an empty List as init value:

scala> val s = List("Foo", "Bar", "Baz")
s: List[java.lang.String] = List(Foo, Bar, Baz)

scala> (s :\ Nil)(_ :: _)
<console>:6: error: type mismatch;
found   : List[java.lang.String]
required: object Nil
(s :\ Nil)(_ :: _)
^

scala> (s :\ (Nil: List[String]))(_ :: _)
res1: List[String] = List(Foo, Bar, Baz)

IMHO, this is one of the most annoying limitations of the scala type system.

Florian.
--

--
But our moral language is fragmented; our contemporaries reject the Kantian
hunch that choosing those things most admirable and plausible as ends in
themselves is the best practice; autonomous sources of the good are everywhere
brown and broken. Thus we have PHP. http://lambda-the-ultimate.org/node/1463

```
1 Apr 2008 17:25

Re: Limited type inference (was: Question regarding Variance and Type Bounds)

```On Tue, Apr 1, 2008 at 5:45 AM, Florian Hars <hars <at> bik-gmbh.de> wrote:
>
>  The same thing happens if you try to fold with an empty List as init value:
>
>  scala> val s = List("Foo", "Bar", "Baz")
>  s: List[java.lang.String] = List(Foo, Bar, Baz)
>
>  scala> (s :\ Nil)(_ :: _)
>  <console>:6: error: type mismatch;
>   found   : List[java.lang.String]
>   required: object Nil
>        (s :\ Nil)(_ :: _)
>                     ^
>
>  scala> (s :\ (Nil: List[String]))(_ :: _)
>  res1: List[String] = List(Foo, Bar, Baz)
>
>  IMHO, this is one of the most annoying limitations of the scala type system.

Incidentally, I seem to remember this working in older versions of
Scala, but I don't have one handy to check. I know it doesn't work
now, and I agree it's annoying. Does anybody know/remember whether
this used to work without the type annotation?

Matt

--

--
Matt Hellige / matt <at> immute.net
http://matt.immute.net

```
1 Apr 2008 17:38

Re: Limited type inference (was: Question regarding Variance and Type Bounds)

```Hi,

On Tuesday 01 April 2008 18:25:56 Matt Hellige wrote:
> Incidentally, I seem to remember this working in older versions of
> Scala, but I don't have one handy to check. I know it doesn't work
> now, and I agree it's annoying. Does anybody know/remember whether
> this used to work without the type annotation?

I think it did. At least I remember Tony Morris had a problem when he tried to
move from older version to maybe 2.7? And the reason for why the code wasn't
compiling for the newer was that there was a Nil. Adding type information the
code worked. He probably can tell in what version it did work.

> Matt

- Henrik

```
1 Apr 2008 17:56

Re: Limited type inference (was: Question regarding Variance and Type Bounds)

```Oops, now I remember it was None, not Nil, but the idea is still valid.

- Henrik

On Tuesday 01 April 2008 18:38:36 Henrik Huttunen wrote:
> Hi,
>
> On Tuesday 01 April 2008 18:25:56 Matt Hellige wrote:
> > Incidentally, I seem to remember this working in older versions of
> > Scala, but I don't have one handy to check. I know it doesn't work
> > now, and I agree it's annoying. Does anybody know/remember whether
> > this used to work without the type annotation?
>
> I think it did. At least I remember Tony Morris had a problem when he tried
> to move from older version to maybe 2.7? And the reason for why the code
> wasn't compiling for the newer was that there was a Nil. Adding type
> information the code worked. He probably can tell in what version it did
> work.
>
> > Matt
>
> - Henrik

```
1 Apr 2008 17:58

Re: Limited type inference

```Henrik Huttunen wrote:

> I think it did. At least I remember Tony Morris had a problem when he tried to
> move from older version to maybe 2.7? And the reason for why the code wasn't
> compiling for the newer was that there was a Nil. Adding type information the
> code worked. He probably can tell in what version it did work.

I seem to vaguely recall that this is related to the change in how case
classes are compiled that was introduced in 2.7.0.

```
1 Apr 2008 18:15

Re: Question regarding Variance and Type Bounds

Hey guyz

Was using version 2.6..
anyway... I tried it on 2.7.0 (the one that comes with the scala plugin..)
It seems to compile fine...

But I get compilation issues when I try to use the add funtion..

val t = Empty

In which case compilation fails with :
"Inferred type agruments [Int] do not conform to method add's type parameter bounds [T <: Ordered[T]]"

I then changed add method to use View bounds like so :
def add[T <% Ordered[T]](t: BSTree[T], x: T): BSTree[T]...

it seems to work fine now..

Thanks guyz
Arun

On Tue, Apr 1, 2008 at 3:55 PM, Geoffrey Alan Washburn <geoffrey.washburn <at> epfl.ch> wrote:
Arun Suresh wrote:
>
> any suggestions ?

It compiles for me without any errors.  What version of Scala are you
using?  Since the error you receive is related to inference you could
try changing

case Node(l, e, r) =>
if (x < e) Node(add(l, x), e, r) else Node(l,  e, add(r, x))

to

case Node(l, e, r) =>
if (x < e) Node(add[T](l, x), e, r) else Node(l,  e, add[T](r, x))

1 Apr 2008 20:14

higher kinded types/type functions

```I'm exploring some stuff inspired by the Type-level Church encodings
section of Towards Equal Rights for Higher-kinded Types and am
encountering some odd behavior.

Starting with the following definitions in the repl:

case class Equals[A, B >: A <: A]
trait hasT { type t <: hasT }
abstract class TypeHolder[T <: hasT] extends hasT { type t = T }
abstract class TNil extends hasT { type t = Nothing }

I try the following:

scala> Equals[TNil,TypeHolder[TNil]#t]
res4: Equals[TNil,TypeHolder[TNil]#t] = Equals()

scala> Equals[TNil,f[TypeHolder[TNil]]]
res5: Equals[TNil,f[TypeHolder[TNil]]] = Equals()

scala> Equals[TNil,TypeHolder[TypeHolder[TNil]]#t#t]
res6: Equals[TNil,TypeHolder[TypeHolder[TNil]]#t#t] = Equals()

scala> Equals[TNil,f[TypeHolder[TypeHolder[TNil]]#t]]
res7: Equals[TNil,f[TypeHolder[TypeHolder[TNil]]#t]] = Equals()

So far so good, but then I try switching the application of f and #t:

scala> Equals[TNil,f[TypeHolder[TypeHolder[TNil]]]#t]
<console>:10: error: illegal cyclic reference involving type t
Equals[TNil,f[TypeHolder[TypeHolder[TNil]]]#t]
^

As far as I can figure f[TypeHolder[TypeHolder[TNil]]]#t should be
equivalent to TypeHolder[TypeHolder[TNil]]#t#t and
f[TypeHolder[TypeHolder[TNil]]#t]

Even stranger is that after that error,
Equals[TNil,TypeHolder[TypeHolder[TNil]]#t#t] gives an error too where
it worked previously.

scala> Equals[TNil,TypeHolder[TypeHolder[TNil]]#t#t]
<console>:9: error: illegal cyclic reference involving type t
Equals[TNil,TypeHolder[TypeHolder[TNil]]#t#t]
^

Does anyone have any idea what's going on here?

-- Geoff Reedy

```

Gmane