Vector details

this comes pretty close:
http://www.scala-lang.org/docu/files/collections-api/collections_15.html

-------- Original-Nachricht --------
> Datum: Tue, 3 May 2011 00:18:47 -0700 (PDT)
> Von: Michael Allman
> An: scala-user [at] googlegroups [dot] com
> Betreff: [scala-user] Vector details

> Hi,
>
> Has anyone written a paper on the data structure behind Scala's Vector
> class? I'd like to learn more about it.
>
> Cheers,
>
> Michael

I've seen this. It doesn't say anything about where this data structure
came from. Is this just something someone on the Scala team thought up?
Who invented it? Is it entirely new? Are there any other implementations
in other languages? Does it have a name (Vector is rather generic)? How
does it perform compared to, say,

Chris Otasaki's random access lists
AVL trees
Braun trees

for various operations? When was it invented? What, if anything, were its
predecessors?

Cheers,

Michael

On Tue, 3 May 2011, Dennis Haupt wrote:

> this comes pretty close:
> http://www.scala-lang.org/docu/files/collections-api/collections_15.html
>
> -------- Original-Nachricht --------
>> Datum: Tue, 3 May 2011 00:18:47 -0700 (PDT)
>> Von: Michael Allman
>> An: scala-user [at] googlegroups [dot] com
>> Betreff: [scala-user] Vector details
>
>> Hi,
>>
>> Has anyone written a paper on the data structure behind Scala's Vector
>> class? I'd like to learn more about it.
>>
>> Cheers,
>>
>> Michael
>

On 5/3/11 10:04 AM, Michael Allman wrote:
> I've seen this. It doesn't say anything about where this data structure
> came from. Is this just something someone on the Scala team thought up?
> Who invented it? Is it entirely new? Are there any other implementations
> in other languages? Does it have a name (Vector is rather generic)? How
> does it perform compared to, say,
>
> Chris Otasaki's random access lists
> AVL trees
> Braun trees
>
> for various operations? When was it invented? What, if anything, were
> its predecessors?

This should get you started:

https://lampsvn.epfl.ch/trac/scala/ticket/3724

Is this just something someone on the Scala team thought up?

probably

Am 03.05.2011 19:04, schrieb Michael Allman:
> I've seen this. It doesn't say anything about where this data
> structure came from. Is this just something someone on the Scala team
> thought up? Who invented it? Is it entirely new? Are there any other
> implementations in other languages? Does it have a name (Vector is
> rather generic)? How does it perform compared to, say,
>
> Chris Otasaki's random access lists
> AVL trees
> Braun trees
>
> for various operations? When was it invented? What, if anything, were
> its predecessors?
>
> Cheers,
>
> Michael
>
> On Tue, 3 May 2011, Dennis Haupt wrote:
>
>> this comes pretty close:
>> http://www.scala-lang.org/docu/files/collections-api/collections_15.html
>>
>> -------- Original-Nachricht --------
>>> Datum: Tue, 3 May 2011 00:18:47 -0700 (PDT)
>>> Von: Michael Allman
>>> An: scala-user [at] googlegroups [dot] com
>>> Betreff: [scala-user] Vector details
>>
>>> Hi,
>>>
>>> Has anyone written a paper on the data structure behind Scala's Vector
>>> class? I'd like to learn more about it.
>>>
>>> Cheers,
>>>
>>> Michael
>>
>

>>>>> "Michael" == Michael Allman writes:

Michael> I've seen this. It doesn't say anything about where this data
Michael> structure came from. Is this just something someone on the
Michael> Scala team thought up? Who invented it? Is it entirely new?
Michael> Are there any other implementations in other languages? Does
Michael> it have a name (Vector is rather generic)? How does it perform
Michael> compared to, say,
Michael> Chris Otasaki's random access lists AVL trees Braun trees
Michael> for various operations? When was it invented? What, if
Michael> anything, were its predecessors?

Daniel Spiewak, "Extreme Cleverness: Functional Data Structures in Scala"
- video: http://vimeo.com/20262239
- slides: http://bit.ly/ge1VhF

Thanks Paul. This answers a lot of my questions. Also, I did some digging
in subversion and it looks like "rompf" introduced beginnings of the
current implementation here:

http://lampsvn.epfl.ch/trac/scala/changeset?new=19024%40scala%2Ftrunk%2F...

Cheers,

Michael

On Tue, 3 May 2011, Paul Phillips wrote:

> On 5/3/11 10:04 AM, Michael Allman wrote:
>> I've seen this. It doesn't say anything about where this data structure
>> came from. Is this just something someone on the Scala team thought up?
>> Who invented it? Is it entirely new? Are there any other implementations
>> in other languages? Does it have a name (Vector is rather generic)? How
>> does it perform compared to, say,
>>
>> Chris Otasaki's random access lists
>> AVL trees
>> Braun trees
>>
>> for various operations? When was it invented? What, if anything, were
>> its predecessors?
>
> This should get you started:
>
> https://lampsvn.epfl.ch/trac/scala/ticket/3724
>

On May 3, 2011, at 7:37 PM, Michael Allman wrote:

> Thanks Paul. This answers a lot of my questions. Also, I did some digging in subversion and it looks like "rompf" introduced beginnings of the current implementation here:

That would be me. The conceptual stuff is joint work by Phil Bagwell and me, and is inspired by Rich Hickey's PersistentVector for Clojure, which was again influenced by earlier work of Phil's. We've been meaning to write up a tech report on Vectors for some time now but never gotten around to finishing that. The trac ticket Paul mentioned is the most accurate description available right now.

- Tiark

> http://lampsvn.epfl.ch/trac/scala/changeset?new=19024%40scala%2Ftrunk%2F...
>
> Cheers,
>
> Michael
>
>
> On Tue, 3 May 2011, Paul Phillips wrote:
>
>> On 5/3/11 10:04 AM, Michael Allman wrote:
>>> I've seen this. It doesn't say anything about where this data structure
>>> came from. Is this just something someone on the Scala team thought up?
>>> Who invented it? Is it entirely new? Are there any other implementations
>>> in other languages? Does it have a name (Vector is rather generic)? How
>>> does it perform compared to, say,
>>>
>>> Chris Otasaki's random access lists
>>> AVL trees
>>> Braun trees
>>>
>>> for various operations? When was it invented? What, if anything, were
>>> its predecessors?
>>
>> This should get you started:
>>
>> https://lampsvn.epfl.ch/trac/scala/ticket/3724
>>

Tiark,

Is the "earlier work" you refer to VList:

http://en.wikipedia.org/wiki/VList

?

I would love to see a paper/report on the Vector data structure. It's
exciting to see this kind of deep innovation, but extracting the
abstraction from the implementation can be pretty hard.

Cheers,

Michael

On Tue, 3 May 2011, Tiark Rompf wrote:

> On May 3, 2011, at 7:37 PM, Michael Allman wrote:
>
>> Thanks Paul. This answers a lot of my questions. Also, I did some
>> digging in subversion and it looks like "rompf" introduced beginnings
>> of the current implementation here:
>
> That would be me. The conceptual stuff is joint work by Phil Bagwell and
> me, and is inspired by Rich Hickey's PersistentVector for Clojure, which
> was again influenced by earlier work of Phil's. We've been meaning to
> write up a tech report on Vectors for some time now but never gotten
> around to finishing that. The trac ticket Paul mentioned is the most
> accurate description available right now.
>
> - Tiark
>
>> http://lampsvn.epfl.ch/trac/scala/changeset?new=19024%40scala%2Ftrunk%2F...
>>
>> Cheers,
>>
>> Michael
>>
>>
>> On Tue, 3 May 2011, Paul Phillips wrote:
>>
>>> On 5/3/11 10:04 AM, Michael Allman wrote:
>>>> I've seen this. It doesn't say anything about where this data structure
>>>> came from. Is this just something someone on the Scala team thought up?
>>>> Who invented it? Is it entirely new? Are there any other implementations
>>>> in other languages? Does it have a name (Vector is rather generic)? How
>>>> does it perform compared to, say,
>>>>
>>>> Chris Otasaki's random access lists
>>>> AVL trees
>>>> Braun trees
>>>>
>>>> for various operations? When was it invented? What, if anything, were
>>>> its predecessors?
>>>
>>> This should get you started:
>>>
>>> https://lampsvn.epfl.ch/trac/scala/ticket/3724
>>>
>