About foldRight

[Jaco]

Hi,

Given following definitions:

sealed abstract class Tree[+T]
case object Empty extends Tree[Nothing]
case class Node[T](e: T, sag: Tree[T], sad: Tree[T]) extends Tree[T]

and an insert function with the following signature:

def insert[T <% Ordered[T]](e: T, tree: Tree[T]): Node[T]

I still don't understand while the following definition gives me an
error :

def list2Tree2[T <% Ordered[T]](list: List[T]) = (list foldRight
Empty) { insert(_, _) }

The error is:

<console>:10: error: type mismatch;
found : Node[T]
required: object Empty
def listTree2[T <% Ordered[T]](list: List[T]) = (list foldRight
Empty) { insert(_, _)}

The following definition works (and do the job):

def list2Tree[T <% Ordered[T]](list: List[T]): Tree[T] = list match {
case Nil => Empty
case x :: xs => insert(x, list2Tree(xs))
}

I understand this insert function is far for optimal as it produces a
totally unbalanced tree, but that's not the point: i wonder why Scala
complains about this type mismatch...

Any clue?

[Derek Williams]

On Sun, Jan 30, 2011 at 4:49 PM, Jaco <eric.j...@gmail.com> wrote:
> I still don't understand while the following definition gives me an
> error :
>
> def list2Tree2[T <% Ordered[T]](list: List[T]) = (list foldRight
> Empty) { insert(_, _) }

Changing that to:

def list2Tree2[T <% Ordered[T]](list: List[T]) = (list foldRight

(Empty: Tree[T])) { insert(_, _) }

or maybe

def list2Tree2[T <% Ordered[T]](list: List[T]): Tree[T] = (list
foldRight Empty) { insert(_, _) }

should work. The reason why you get that error is somewhere in my
head, but I just can't seem to find it... oh well. I'm pretty sure one
of these 2 changes should fix it. I'm pretty sure the same thing
happens if you try to fold into a List and give it a Nil.

--
Derek

[Jaco]

On 31 jan, 01:37, Derek Williams <de...@nebvin.ca> wrote:

> Changing that to:
>
> def list2Tree2[T <% Ordered[T]](list: List[T]) = (list foldRight
> (Empty: Tree[T])) { insert(_, _) }

It works, thanks! (bu not the second one).

I've discovered another piece of Scala, BTW, as i didn't know this
"typecasting" syntax for parameters.

But i admit i still don't know why i have to do this dirty trick...
What prevent Scala to infer the right type for Empty?

And, yes, i get the same thing with lists but, at least, i can write
List[Int]() instead of Nil.

Thanks again

[Paul Phillips]

On Sun, Jan 30, 2011 at 10:28:15PM -0800, Jaco wrote:
> But i admit i still don't know why i have to do this dirty trick...
> What prevent Scala to infer the right type for Empty?

It infers from left to right and doesn't go back across parameter list
boundaries to change its mind. And it picks the most specific type.
You can use this to your advantage sometimes. Other times, like
foldLeft, it uses you instead. A simple illustration.

scala> def f1[T](x: T)(xs: Set[T]) = xs + x
f1: [T](x: T)(xs: Set[T])scala.collection.immutable.Set[T]

scala> f1("a")(Set(new AnyRef))
<console>:7: error: type mismatch;
found : java.lang.Object
required: java.lang.String
f1("a")(Set(new AnyRef))
^

scala> def f2[T](x: T, xs: Set[T]) = xs + x
f2: [T](x: T,xs: Set[T])scala.collection.immutable.Set[T]

scala> f2("a", Set(new AnyRef))
res1: scala.collection.immutable.Set[java.lang.Object] = Set(java.lang.Object@26bb2f6e, a)

--
Paul Phillips | Eschew mastication.
Caged Spirit |
Empiricist |
up hill, pi pals! |----------* http://www.improving.org/paulp/ *----------