converting a List to a Vector

[Russ P.]

It would be handy if List had a toVector method.

Since it doesn't, what is the simplest way to convert a List to a Vector? Thanks.

--Russ P.

[Erik Osheim]

def listToVector[A](as:List[A]) = Vector[A]() ++ as

-- Erik

[Marcel Molina]

scala> List(1).toIndexedSeq

scala.collection.immutable.IndexedSeq[Int] = Vector(1)

[Rex Kerr]

Shortest and fastest:
  Vector(xs: _*)

Runners up:
  Vector() ++ xs
  Vector.empty ++ xs

--Rex

[Josh Suereth]

In 2.10.x

List().to[Vector]

And

List().toVector

In 2.9.x, fastest may be

Vector.empty ++ list

[Russ P.]

Thanks to everyone who answered. You guys are incredibly helpful.

For my purposes, it appears that Vector is usually preferable to List. In the few cases where List might be slightly preferable, the difference is not enough to worry about (for me, anyway). So I'm wondering if Vector is going to be put into predef so I don't have to clutter my code with

import scala.collection.immutable.Vector

If it's feasible, I'd say just rename Vector to List, and rename List to something else. That would save me some time, and it would also save the name Vector for other uses. But I assume it's not feasible at this point.

--Russ P.

[Derek Williams]

On Wed, Sep 12, 2012 at 7:51 PM, Russ P. <russ.p...@gmail.com> wrote:

For my purposes, it appears that Vector is usually preferable to List. In the few cases where List might be slightly preferable, the difference is not enough to worry about (for me, anyway). So I'm wondering if Vector is going to be put into predef so I don't have to clutter my code with

import scala.collection.immutable.Vector

IndexedSeq is in Predef, and that will give you a Vector

 

--

Derek Williams

[Rex Kerr]

I benchmarked both Vector(xs: _*) and Vector.empty ++ xs, and the former won (by a small margin with lists with a handful of items) in 2.9.  This makes sense because there's a little extra overhead with adding nothing to the vector builder with Vector.empty ++ xs.  (The ++ code in TraversibleLike does not check whether either side is empty before attempting to build.)

  --Rex

[Josh Suereth]

That's surprising considering the byte code.  How/what did you use to benchmark?  I may run my own to validate.

[Seth Tisue]

On Wed, Sep 12, 2012 at 9:51 PM, Russ P. <russ.p...@gmail.com> wrote:
> I'm wondering if Vector is going
> to be put into predef so I don't have to clutter my code with
> import scala.collection.immutable.Vector

Eh? It's in Predef already.

--
Seth Tisue | Northwestern University | http://tisue.net
lead developer, NetLogo: http://ccl.northwestern.edu/netlogo/

[Russ P.]

On Wednesday, September 12, 2012 7:57:40 PM UTC-7, Seth Tisue wrote:

On Wed, Sep 12, 2012 at 9:51 PM, Russ P. <russ.p...@gmail.com> wrote:
> I'm wondering if Vector is going
> to be put into predef so I don't have to clutter my code with
> import scala.collection.immutable.Vector

Eh? It's in Predef already.

 

And so it is. I was confused due to a name clash with my own Vector class (as in vectors and matrices). I guess I'll have to rename my class to Vectr or something like that. Vector is such a nice name for vectors in the mathematical and physical domains, it's a shame that it is taken for what is really just a list.

--Russ P.

[Rex Kerr]

Why is that surprising?  ++ on TraversibleLike creates a builder and adds both empty and the collection to it using ++=.  GenericCompanion's apply just ++='s the passed-in list.  I didn't look at the bytecode, but adding is more work than creating (both logically and in the code).

  --Rex

[Josh Suereth]

Var-args usually involves creating an ArrayWrapper of values, just for fun.   Perhaps I'm misremembering the Java case, and Scala short-circuits List directly into it.

In Any case,  2.10.x w/   to[Collection] should be more efficient, but we should check.

[Rex Kerr]

The whole point of changing varargs from array to Seq was so that you only needed to create an ArrayWrapper when you were passing in separately-specified arguments.  Sequences go in as-is.  I don't see how to[Collection] could be any better (though if it's lucky it may not be any worse).

  --Rex

[Alex Cruise]

On Wed, Sep 12, 2012 at 6:51 PM, Russ P. <russ.p...@gmail.com> wrote:
> Thanks to everyone who answered. You guys are incredibly helpful.
>
> For my purposes, it appears that Vector is usually preferable to List. In
> the few cases where List might be slightly preferable, the difference is not
> enough to worry about (for me, anyway). So I'm wondering if Vector is going
> to be put into predef so I don't have to clutter my code with
>
> import scala.collection.immutable.Vector
>
> If it's feasible, I'd say just rename Vector to List, and rename List to
> something else. That would save me some time, and it would also save the
> name Vector for other uses. But I assume it's not feasible at this point.

I don't think that's ever going to happen. :)

But my rule of thumb is:
- Always use Seq in APIs, never List (unless you're forced to by inheritance)
- When you need to construct a new Seq, use Vector.
- (Important!) On a regular basis, go through your codebase and replace this:

someSeq match {
case x :: xs => ...
case Nil =>
}

with this (note that it will still work fine on s.c.i.List):

someSeq match {
case Seq(x, xs @ _*) => ...
case Seq() => ...
}

in 2.10, we have generalized Seq extractors, so you can do this:

someSeq match {
case x +: xs => ...
case Seq() => ...
}

HTH!

-0xe1a

[Russ P.]

I'm sure that's all good information, Alex, but what bothers me is that I should have to remember stuff like that. I would much rather focus on my problem domain than on arbitrary details of what to call a List or how to do a match on a List. That I should need to remember arbitrary details like that to compensate for a design mistake made long ago is not a good sign. Also, call me sloppy, but my chances of recalling these rules when I actually need them are negligible.

--Russ P.

[Michael Schmitz]

What is the design mistake? Scala has multiple implementations of
Seq. You chose one and now want to switch to another.

Peace. Michael

[Michael Schmitz]

> List().to[Vector]

Cool!

[Alex Cruise]

On Thu, Sep 13, 2012 at 5:11 PM, Russ P. <russ.p...@gmail.com> wrote:

I'm sure that's all good information, Alex, but what bothers me is that I should have to remember stuff like that. I would much rather focus on my problem domain than on arbitrary details of what to call a List or how to do a match on a List. That I should need to remember arbitrary details like that to compensate for a design mistake made long ago is not a good sign.

I wouldn't call the popularity of s.c.i.List a design mistake, it's the classic data structure for functional programming.  It just so happens that the data structure that underlies s.c.i.Vector was discovered/invented fairly recently, and turns out to be more broadly applicable, while still retaining many of the classic cons list's attractive qualities.  

In the Java 1.0.x days no one complained much about all the Vectors and Hashtables that littered our APIs; they only became distasteful in retrospect once we learned that List and Map were better choices.  :)

Also, call me sloppy, but my chances of recalling these rules when I actually need them are negligible.

*shrug* eventually one's sense of code smell becomes proactive, and a collection of memorized arbitrary rules gradually becomes muscle memory. :)

-0xe1a

[Russ Paielli]

On Thu, Sep 13, 2012 at 6:45 PM, Alex Cruise <al...@cluonflux.com> wrote:

On Thu, Sep 13, 2012 at 5:11 PM, Russ P. <russ.p...@gmail.com> wrote:

I'm sure that's all good information, Alex, but what bothers me is that I should have to remember stuff like that. I would much rather focus on my problem domain than on arbitrary details of what to call a List or how to do a match on a List. That I should need to remember arbitrary details like that to compensate for a design mistake made long ago is not a good sign.

I wouldn't call the popularity of s.c.i.List a design mistake, it's the classic data structure for functional programming.  It just so happens that the data structure that underlies s.c.i.Vector was discovered/invented fairly recently, and turns out to be more broadly applicable, while still retaining many of the classic cons list's attractive qualities.

I shouldn't have called it a design mistake. It's just a slightly unfortunate clash of names across domains. Having been formally trained as an aerospace engineer, I think of a vector as an n x 1 matrix that can be used to represent position, velocity, force, and other physical concepts, such as a state vector. An entire academic field known as "state estimation and control theory" is based on the concept of a state vector. The CS concept of a vector is related but not quite the same because the contents are not necessarily even numbers, and there is no inherent concept of vector addition or vector/matrix multiplication, for example.

My use of Scala collections comes down to mainly Lists, Sets, and Maps. Now I am realizing that Vectors are usually preferable to Lists, but for my purposes they are just an improved form of List. Efficient random access is usually more important to me than a slight difference in iteration efficiency. Most of my use of Vectors will be for lists rather than for representation of physical vectors. The name List would be more appropriate in most cases, and the use of Vectors for lists creates a slight cognitive dissonance for me, but I'll get over it. Maybe I could come up with some elegant type aliases, but that would probably just confuse readers of my code.

--Russ P.

 

--
http://RussP.us

[Dennis Haupt]

was vector really only invented recently? i mean, basically it's just a tree of lists. i can't really imagine that it hasn't been used before scala 2.9

-------- Original-Nachricht --------
> Datum: Thu, 13 Sep 2012 21:25:18 -0700
> Von: Russ Paielli <russ.p...@gmail.com>
> An: Alex Cruise <al...@cluonflux.com>
> CC: scala...@googlegroups.com
> Betreff: Re: [scala-user] converting a List to a Vector

[Raoul Duke]

On Thu, Sep 13, 2012 at 9:25 PM, Russ Paielli <russ.p...@gmail.com> wrote:
> representation of physical vectors. The name List would be more appropriate
> in most cases, and the use of Vectors for lists creates a slight cognitive
> dissonance for me, but I'll get over it. Maybe I could come up with some
> elegant type aliases, but that would probably just confuse readers of my
> code.

naming is both important and impossible to get right all the time e.g.
vector means yet another thing to an epidemiologist. 'vector' in
java-related things probably comes from java's name, at least a
little. (consider how many different meanings 'gene' has in biology,
as an extreme example of even a single domain having name issues. :-)

if you went to work with epidemiologists you wouldn't tell them to
change their use of 'vector' i would guess. of course, the scala/java
vector is a little too close to your own vector, making it more
confusing, than a disease one.

as you say, even if the core language has some really bad choices of
naming (val vs. var is probably my top scala example, all languages
have some doozy somewhere in their design), it is best to stick with
that core lingo and not alias things, unless you are sure nobody else
will ever need to read your code :-)

[Alex Cruise]

On Thu, Sep 13, 2012 at 9:25 PM, Russ Paielli <russ.p...@gmail.com> wrote:

I shouldn't have called it a design mistake. It's just a slightly unfortunate clash of names across domains. Having been formally trained as an aerospace engineer, I think of a vector as an n x 1 matrix that can be used to represent position, velocity, force, and other physical concepts, such as a state vector. An entire academic field known as "state estimation and control theory" is based on the concept of a state vector. The CS concept of a vector is related but not quite the same because the contents are not necessarily even numbers, and there is no inherent concept of vector addition or vector/matrix multiplication, for example.

Yeah, another important difference is that the data structure flavour of Vectors are variable length. :)  Yet another example of CS misappropriating mathematical terms. :)

 

My use of Scala collections comes down to mainly Lists, Sets, and Maps. Now I am realizing that Vectors are usually preferable to Lists, but for my purposes they are just an improved form of List. Efficient random access is usually more important to me than a slight difference in iteration efficiency.

In that case, you should definitely be using Vectors, at least internally.  But remember the API design best practice: when producing or consuming a collection, use the least specific trait that meets your requirements, rather than the specific implementation class.  

On the consuming side, that way your client code has the flexibility to provide their own implementation; on the producing side, it provides client code fewer opportunities to make assumptions that would constrain your design choices in future.

So, if your implementation will be random-accessing a collection provided by client code, you should declare the method as requiring an IndexedSeq, which doesn't add any methods to Seq, it just serves as a promise of efficient random access.

 

Most of my use of Vectors will be for lists rather than for representation of physical vectors. The name List would be more appropriate in most cases, and the use of Vectors for lists creates a slight cognitive dissonance for me, but I'll get over it. Maybe I could come up with some elegant type aliases, but that would probably just confuse readers of my code.

For math-and-physics vectors, tuples are probably a lot closer to what you want.  But there are a fair number of linear algebra libraries in Scala so I wouldn't reinvent the wheel there. :)

-0xe1a

[Alex Cruise]

On Fri, Sep 14, 2012 at 12:10 AM, Dennis Haupt <h-s...@gmx.de> wrote:

was vector really only invented recently? i mean, basically it's just a tree of lists. i can't really imagine that it hasn't been used before scala 2.9

s.c.i.Vector arrived in 2.8:

http://www.scala-lang.org/node/9375 

https://issues.scala-lang.org/browse/SI-3724?focusedCommentId=50842&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-50842

-0xe1a

[Alan Burlison]

On 13/09/2012 18:12, Alex Cruise wrote:

> - (Important!) On a regular basis, go through your codebase and replace this:
>
> someSeq match {
> case x :: xs => ...
> case Nil =>
> }
>
> with this (note that it will still work fine on s.c.i.List):
>
> someSeq match {
> case Seq(x, xs @ _*) => ...
> case Seq() => ...
> }

Why?

--
Alan Burlison
--

[Alex Cruise]

Hah, someone else asked me this in a private email.  Here's my response:

The former will only match instances of s.c.i.List, and no other kind of collection. This is because "::" and "Nil" are the names of its implementation classes, not special syntax.

The latter pattern match uses an extractor defined on s.c.i.Seq's companion object (or one of its supers), and it's implemented to operate on arbitrary implementations of Seq, including List, Vector, Stream, Array, etc. If you want to see how the extractor works, it's a method called "unapplySeq".

Extractors can be bewildering at first, so don't get discouraged if they don't make sense to you; just think of them as how you customize pattern matching.

Seq is abstract, so this generality of its extractor makes a certain intuitive sense. At least, it's intuitive once you've internalized the basic look and feel of Scala. :)

HTH!

-0xe1a

[Josh Suereth]

Note in 2.10.x:

someSeq match {
     case x +: xs =>  ...

     case _ =>  ...
}

Although, I think for efficiency, sticking with list and :: is better.

[Alan Burlison]

On 17/09/2012 18:13, Alex Cruise wrote:

> The former will only match instances of s.c.i.List, and no other kind of
> collection. This is because "::" and "Nil" are the names of its
> implementation classes, not special syntax.

Which leads to the followup question ;-)

Why is :: not defined for Vector?

--
Alan Burlison
--

[Josh Suereth]

case class ::[A](x: A) extends List[A]

How do you want that defined for vector?

[Erik Osheim]

Hi Alan,

I think you misunderstood Alex's email. The name "::" is the name of
one of List's subclasses (the other name being "Nil"). Obviously, you
can't define two classes of the same name, so there can't be another
class named "::" for Vector, or any other class.

Hope this helps,

-- Erik

[Josh Suereth]

Oh, also if you're specifically asking why the :: deconstructor/extractor doesn't exist for vector, it does.  It's called +: in 2.10.   The reason it's *slower* is because case class deconstruction is very fast.   For Vector, we have to use an object to do the extraction, and it look like:

object +: {

  def unapply[T,Coll <: SeqLike[T, Coll]](

      t: Coll with SeqLike[T, Coll]): Option[(T, Coll)] =

    if(t.isEmpty) None

    else Some(t.head -> t.tail)

}

So for efficient head/tail decomposition it's fast, but not all of the overhead of tuplizing and such is removed.  i.e. :: for List is faster.   Now, how much?  I haven't profiled.  It could be hotspot optimised in some cases.  There's just more initial bytecode for hotspot to wade through.

- Josh

On Mon, Sep 17, 2012 at 4:04 PM, Alan Burlison <alan.b...@gmail.com> wrote:

[Alan Burlison]

On 17/09/2012 21:08, Erik Osheim wrote:

> I think you misunderstood Alex's email. The name "::" is the name of
> one of List's subclasses (the other name being "Nil"). Obviously, you
> can't define two classes of the same name, so there can't be another
> class named "::" for Vector, or any other class.

Ah, of course - that makes sense. And I suppose it forms a cautionary
tale as well - when using classnames-that-look-like-syntax, you only get
to use them once, so choose wisely.

> Hope this helps,

It does, thank you.

--
Alan Burlison
--

[Alan Burlison]

On 17/09/2012 21:17, Josh Suereth wrote:

> Oh, also if you're specifically asking why the :: deconstructor/extractor
> doesn't exist for vector, it does. It's called +: in 2.10. The reason
> it's *slower* is because case class deconstruction is very fast. For
> Vector, we have to use an object to do the extraction, and it look like:
>
> object +: {
> def unapply[T,Coll<: SeqLike[T, Coll]](
> t: Coll with SeqLike[T, Coll]): Option[(T, Coll)] =
> if(t.isEmpty) None
> else Some(t.head -> t.tail)
> }
>
>
> So for efficient head/tail decomposition it's fast, but not all of the
> overhead of tuplizing and such is removed. i.e. :: for List is faster.
> Now, how much? I haven't profiled. It could be hotspot optimised in some
> cases. There's just more initial bytecode for hotspot to wade through.

Ah, I see. So, to go back to the two variants that Alex gave:

someSeq match {
case Seq(x, xs @ _*) => ...
case Seq() => ...
}

or

someSeq match {
case x +: xs => ...
case Seq() => ...
}

either of these will work not just on Lists but also on Vectors (or
indeed any Seq subclass). However the first form should be faster than
the second.

Thanks, that's an interesting insight into the design trade-offs of
these classes.

--
Alan Burlison
--

[Josh Suereth]

You may want to profile this.   For Vector/List +: may be faster than Seq(...).    For List specifically :: should be best.

[Alan Burlison]

On 18/09/2012 12:14, Josh Suereth wrote:

>> either of these will work not just on Lists but also on Vectors (or
> indeed any Seq subclass). However the first form should be faster than the
> second.
>
> You may want to profile this. For Vector/List +: may be faster than
> Seq(...). For List specifically :: should be best.

Good idea :-) The units below are seconds and have been rounded as
there's quite a bit of variation between runs, even after heating up the
JVM. The List and Vector tests both use a 3-element list of integers,
(1, 2, 3).

List Vector
:: 6 N/A
case Seq(...) 10 100
+: 25 200

I suspect there's some sort of optimisation kicking in here in the case
of list, because an empty 'do nothing' loop takes 5 seconds.

--
Alan Burlison
--

[Josh Suereth]

Wow, that extra overhead for +: extractor is more than expected, ugh.  Thanks for the numbers!

[Naftoli Gugenheim]

On Mon, Sep 17, 2012 at 4:17 PM, Josh Suereth <joshua....@gmail.com> wrote:

    else Some(t.head -> t.tail)

Is the -> implicit step inlined?

[Josh Suereth]

In 2.10.

[Grzegorz Kossakowski]

On 24 September 2012 04:49, Josh Suereth <joshua....@gmail.com> wrote:

In 2.10.

I don't think we have tests for that and my experience with complete inlining of -> has been rather flaky so far.

--
Grzegorz Kossakowski

[Josh Suereth]

That's fair.   The byte code I inspected looked fine.   One time I used anecdotal evidence and everything was OK.

[Daniel Sobral]

On Mon, Sep 24, 2012 at 7:30 AM, Josh Suereth <joshua....@gmail.com> wrote:
> That's fair. The byte code I inspected looked fine. One time I used
> anecdotal evidence and everything was OK.

Isn't -> one of the methods that can no longer be AnyVal? Or has that
been circumvented by that scala-library-only get-out-of-jail card?

>
> On Sep 24, 2012 5:08 AM, "Grzegorz Kossakowski"
> <grzegorz.k...@gmail.com> wrote:
>>
>> On 24 September 2012 04:49, Josh Suereth <joshua....@gmail.com> wrote:
>>>
>>> In 2.10.
>>
>> I don't think we have tests for that and my experience with complete
>> inlining of -> has been rather flaky so far.
>>
>> --
>> Grzegorz Kossakowski
>>
>

--
Daniel C. Sobral

I travel to the future all the time.

[Josh Suereth]

hasn't been removed yet, AFAIK.  I think we may have a work around the previous issue.