Implicit resolution, Ordered and Ordering

Thanks to my new four day work week setup (a mixed blessing, but
rather nice) I finally have time to give the collections API the kick
around I've been promising. 

I've been investigating some of the Ordering stuff to start with (I'm
updating TreeSet to use Ordering, thus keeping it in line with TreeMap
and giving it shiny new bonus performance goodness). I ran into some
problems.

Some of them are just cases where a conversion has been passed
explicitly. Those are fortunately the work of moments to fix and can
safely be ignored.

The more problematic case is things where an existing class has
explicitly extended Ordered[MyClass]. These don't automatically get an
Ordering, which is a bit of a pain.

Ok, I thought this would be simple to solve by just adding the
following implicit to Ordering:

  implicit def OrderedOrdering[A <: Ordered[A]] : Ordering[A] = new Ordering[A]{
    def compare(x : A, y : A) = x.compare(y);
  }

But unfortunately this introduces an implicit ambiguity:

scala> Ordering[Int]
<console>:5: error: ambiguous implicit values:
 both value Int in object Ordering of type => Ordering[Int]
 and method OrderedOrdering in object Ordering of type [A <:

Mapping maps

More implicit resolution errors:

scala> TreeMap(1 -> 2)
res0: scala.collection.immutable.TreeMap[Int,Int] = Map(1 -> 2)

scala> res0.map(_.toString)
res1: scala.collection.immutable.Iterable[String] = List((1,2))

scala> res0.map(x => x)
<console>:9: error: ambiguous implicit values:
 both method builderFactory in object TreeMap of type [A,B](implicit
ord: Ordering[A])scala.collection.generic.BuilderFactory[(A,
B),scala.collection.immutable.TreeMap[A,B],scala.collection.immutable.TreeMap#Coll]
 and method builderFactory in object Traversable of type
[A]scala.collection.generic.BuilderFactory[A,scala.collection.immutab...
       res0.map(x => x)
               ^

This seems to be a specific problem with TreeMap, either because of
ordering or because of defining methods in the companion object:

scala> IntMap(1 -> 2)
res4: scala.collection.immutable.IntMap[Int] = IntMap(1 -> 2)

scala> res4.map(x => x)
res5: scala.collection.immutable.Map[Int,Int] = Map(1 -> 2)

scala> HashMap(1 -> 2)
res6: scala.collection.immutable.HashMap[Int,Int] = Map(1 -> 2)

List.flatten

It seems this method has been deprecated in object List, and removed  
in class List. The deprecation message says one should use the missing  
method on class List:

   /** Concatenate all the elements of a given list of lists.
    *
    *   <at> param xss the list of lists that are to be concatenated
    *   <at> return    the concatenation of all the lists
    */
    <at> deprecated("use `xss.flatten' instead")
   def flatten[A](xss: List[List[A]]): List[A] = {

Is there a problem if I undeprecate it? Grepping the compiler showed  
that it is still used in a couple of places.

iulian

--
Iulian Dragos
--
http://lamp.epfl.ch/~dragos

Builders and builder factories

The current design of Builders as things which have a += method
mirrors quite closely my initial design when I was playing around with
alternative collections API designs a while back. This is unfortunate
as, after a discussion with Jamie Webb who suggested the basic idea, I
replaced it with what I thought was a much better one. 

Currently we have Builders and BuilderFactories. A BuilderFactory
creates a Builder, which you then use to build.

What I had instead was

trait Buildable[A, B]{
   def build(elements : Traversable[A]) : B;
}

This has a number of advantages over the += approach:

- Reduces concept proliferation. You don't have distinct Builder and
BuilderFactories, they're unified into a single type.
- Means you don't have to expose mutability to the end user
- Improves performance in many cases! Particularly in the case of
mutable collections. e.g. suppose I'm building an array and I'm
building it from something with a known size. Then I can just create
an array of that size and populate it rather than having to resize.
Also because you don't have to be able to reuse Builders in the same
way, given an ArrayBuffer I can just create a new one, append to it
and then return that. etc.

I'm still getting my head around the way BuilderFactory and Builder
are used (in particular the case where some things can return

Re: List.flatten

Ok, I found the flatten method, and it's in the same boat as unzip:  
both are unusable ATM because of implicit resolution errors. This is  
currently failing:

scala> val xs = List((1, "one"), (2, "two"))
xs: List[(Int, java.lang.String)] = List((1,one), (2,two))

scala> xs.unzip
<console>:6: error: value unzip is not a member of List[(Int,  
java.lang.String)]
        xs.unzip

Now method unzip is added post factum to traversables that are  
instantiated at a pair type, using implicits of course. However, even  
when the method is called explicitly, builders are not found at the  
right types:

cala> pairTraversableWrapper[List[(Int, String)], Int, String](xs).unzip
<console>:12: error: no implicit argument matching parameter type  
scala.collection.generic.BuilderFactory[String,That2,List[(Int,  
String)]] was found.
        pairTraversableWrapper[List[(Int, String)], Int, String] 
(xs).unzip

(note that I had to pass type parameters explicitly).

I can't really say if this is a bug in the compiler, or the collection  
libraries miss something, but this should definitely be fixed before  
2.8-preview.

Re: List.flatten

2009/6/1 Iulian Dragos <iulian.dragos@...>:
> Ok, I found the flatten method, and it's in the same boat as unzip: both are
> unusable ATM because of implicit resolution errors. This is currently
> failing:
>
> scala> val xs = List((1, "one"), (2, "two"))
> xs: List[(Int, java.lang.String)] = List((1,one), (2,two))
>
> scala> xs.unzip
> <console>:6: error: value unzip is not a member of List[(Int,
> java.lang.String)]
>       xs.unzip
>
> Now method unzip is added post factum to traversables that are instantiated
> at a pair type, using implicits of course. However, even when the method is
> called explicitly, builders are not found at the right types:
>
> cala> pairTraversableWrapper[List[(Int, String)], Int, String](xs).unzip
> <console>:12: error: no implicit argument matching parameter type
> scala.collection.generic.BuilderFactory[String,That2,List[(Int, String)]]
> was found.
>       pairTraversableWrapper[List[(Int, String)], Int, String](xs).unzip
>
> (note that I had to pass type parameters explicitly).
>
> I can't really say if this is a bug in the compiler, or the collection
> libraries miss something, but this should definitely be fixed before
> 2.8-preview.

I have to say, I'm getting *very* uncomfortable with how sensitive the

Re: List.flatten

On Mon, June 1, 2009 7:01 pm, Iulian Dragos wrote:
> I can't really say if this is a bug in the compiler, or the collection
> libraries miss something, but this should definitely be fixed before
> 2.8-preview.
>

For the record, the latest is that 2.8-preview might not actually happen,
or at least not in time for JavaOne. I asked Martin about the preview the
other day, and he seemed to indicate that trunk is too much in flux at
this time. We'll see how things evolve in a few days, I suppose.
Toni

Re: names / defaults

Hey Lukas

I have one question, I can see that you committed a new starr together 
with the named/default args commit. What is in that new starr? Any 
reason why it was made?
The reason I ask is because I am currently creating a new starr that 
supports only the new early defs syntax, and that means to remove that 
old syntax usage from trunk!

/Anders

Lukas Rytz wrote:
> Named and default arguments are now in trunk. The main changes are:
> 
> - MethodType now takes (params: List[Symbol]) as argument, no more
> List[Type]
> - To create parameter symbols for a synthetic MethodType, use
>     methodSymbol.newSyntheticValueParamss(argtypess)
> 
> - the expression "foo(x = _)" was previously parsed as
>        foo(x$1 => x = x$1)
>    but is now parsed as a named application:
>        x$1 => foo(x = x$1)
> 
> - a "copy" method is added to case classes
> - the tree copiers in the compiler are now called "treeCopy", no longer
> "copy"
> 
> To learn how to use named / default arguments and how they are implemented,
> see http://www.scala-lang.org/sid/1

Re: names / defaults

Re: names / defaults

Hey Lukas

Sorry, I thought is was the named arguments commit, but yes, sorry it 
was the annotations commit :) But never the less, you committed a new 
starr :) Okay, I have just today merge the earlydefs branch with trunk 
and I am running the test suite to see if there are any failing test 
cases. If not, then I will build a new starr of this for my branch, 
where the early defs syntax has changed!

This starr will then contain the named arguments and the annotations 
commit.

/Anders

Lukas Rytz wrote:
> Hi Anders,
> 
> In fact I did not commit a new starr togeter with the named/default
> arguments
> (http://lampsvn.epfl.ch/trac/scala/changeset/17916).
> But I did commit a new starr with the new annotations implementation
> (http://lampsvn.epfl.ch/trac/scala/changeset/17925).
> 
> The reason is that (actually in both changes), the pickle format has
> changed.
> The new starr was done to make sure it uses that new format. Also, we can
> now start using named/default arguments in the compiler/library.
> 
> If you build a new starr just make sure you build it based on a recent
> version of trunk.
> 
> Cheers: Lukas
> 
--

-- 
Anders Bach Nielsen            |   http://www.cs.au.dk/~abachn/
University of Aarhus           |   abachn@...
- 
  Half of being smart is knowing what you're dumb at.