Why is List:+ deprecated?

you can find the reason here: http://www.nabble.com/problem-with-printing-list-td17263436.html#a17263436

On Thu, Feb 26, 2009 at 5:45 PM, Sciss <contact@sciss.de> wrote:

hi,

why is the following deprecated:

       private var  collAllClients : List[Client]              = Nil

       def addListener( ... ) {
               val mc = new Client( ... )
               collAllClients += mc    // --> deprecated
       }

i know i can write instead

               collAllClients :::= List( mc )

but this is more ugly, probably less efficient, and i don't understand why that should be preferred over the += approach?

ciao, -sciss-

> private var collAllClients : List[Client] = Nil
>
> def addListener( ... ) {
> val mc = new Client( ... )
> collAllClients += mc // --> deprecated
> }
>
> i know i can write instead
>
> collAllClients :::= List( mc )

I thought you could use

collAllClients ::= mc

what is more concise than collAllClients :::= List(mc).

But AFAIC both have *different* result than += ,
as that would append the mc to the *end*.

So you would indeed have to write
collAllClients = collAllClients ::: List(mc)
to get the same effect.

What's the solution now?
(I detected += in my sources too, as I often want
to construct a list from left to right)

KR
Det

On Thu, Feb 26, 2009 at 6:56 PM, Detering Dirk
wrote:
>>       private var  collAllClients : List[Client]              = Nil
>>
>>       def addListener( ... ) {
>>               val mc = new Client( ... )
>>               collAllClients += mc    // --> deprecated
>>       }
>>
>> i know i can write instead
>>
>>               collAllClients :::= List( mc )
>
> I thought you could use
>
>  collAllClients ::= mc
>
> what is more concise than collAllClients :::= List(mc).
>
> But AFAIC both have *different* result than += ,
> as that would append the mc to the *end*.
>
> So you would indeed have to write
>   collAllClients = collAllClients ::: List(mc)
> to get the same effect.
>
> What's the solution now?
> (I detected += in my sources too, as I often want
> to construct a list from left to right)

In that case you really should use a ListBuffer, not a List.

Cheers

martin odersky
> In that case you really should use a ListBuffer, not a List.

Hey Sciss,

in a nice way Martin told us: RTFSB * :-)

KR
Det

* Read The Fine Stairway Book - precisely: Chapter 22.2 Page 494

"Richard T. Farmer School of Business" ?

a pity, i'm trying to switch to scala.collection.immutable.List
whereever possible. i still don't understand why that doesn't define
an append( elem: A ) method... (could have any other name, like 'add')

still haven't ordered my book, broke ATM :-/ doesn't EPFL offer
grants for scala based projects? ...

ciao, -sciss-

Am 27.02.2009 um 09:26 schrieb Detering Dirk:

> martin odersky
>> In that case you really should use a ListBuffer, not a List.
>
> Hey Sciss,
>
> in a nice way Martin told us: RTFSB * :-)
>
> KR
> Det
>
>
> * Read The Fine Stairway Book - precisely: Chapter 22.2 Page 494
>

Appending to a singly linked list is an O(n) operation.  Appending n elements is O(n^2).

A far better mechanism is to append to a ListBuffer, which is O(1), or prepend instead of append to a List, then reverse the result.  Each prepend is O(1) and reverse is O(n), so the overall complexity is O(n).  Of course, prepending when you really want to append makes for harder-to-read code, hence the suggestion of using ListBuffer.

You might like to implement List yourself in some other language to get a good idea of how Scala's works and why certain things are slow enough to deprecate.

2009/2/27 Sciss <contact@sciss.de>

"Richard T. Farmer School of Business" ?

a pity, i'm trying to switch to scala.collection.immutable.List whereever possible. i still don't understand why that doesn't define an append( elem: A ) method... (could have any other name, like 'add')

still haven't ordered my book, broke ATM :-/  doesn't EPFL offer grants for scala based projects? ...

ciao, -sciss-


Am 27.02.2009 um 09:26 schrieb Detering Dirk:

martin odersky

In that case you really should use a ListBuffer, not a List.

 Hey Sciss,

in a nice way Martin told us:  RTFSB *  :-)

KR
Det


* Read The Fine Stairway Book - precisely: Chapter 22.2 Page 494

Please describe what should happen when you append an element to an immutable List.

2009/2/27 Sciss <contact@sciss.de>

i thought List keeps a Head and Tail field? if not, isn't there any such immutable linked list, or is that a contraction (immutable / linked)?

Am 27.02.2009 um 10:12 schrieb Ricky Clarkson:

Appending to a singly linked list is an O(n) operation.  Appending n elements is O(n^2).

A far better mechanism is to append to a ListBuffer, which is O(1), or prepend instead of append to a List, then reverse the result.  Each prepend is O(1) and reverse is O(n), so the overall complexity is O(n).  Of course, prepending when you really want to append makes for harder-to-read code, hence the suggestion of using ListBuffer.

You might like to implement List yourself in some other language to get a good idea of how Scala's works and why certain things are slow enough to deprecate.

2009/2/27 Sciss <contact@sciss.de>
"Richard T. Farmer School of Business" ?

a pity, i'm trying to switch to scala.collection.immutable.List whereever possible. i still don't understand why that doesn't define an append( elem: A ) method... (could have any other name, like 'add')

still haven't ordered my book, broke ATM :-/  doesn't EPFL offer grants for scala based projects? ...

ciao, -sciss-


Am 27.02.2009 um 09:26 schrieb Detering Dirk:


martin odersky
In that case you really should use a ListBuffer, not a List.

 Hey Sciss,

in a nice way Martin told us:  RTFSB *  :-)

KR
Det


* Read The Fine Stairway Book - precisely: Chapter 22.2 Page 494

i thought List keeps a Head and Tail field? if not, isn't there any
such immutable linked list, or is that a contraction (immutable /
linked)?

Am 27.02.2009 um 10:12 schrieb Ricky Clarkson:

> Appending to a singly linked list is an O(n) operation. Appending
> n elements is O(n^2).
>
> A far better mechanism is to append to a ListBuffer, which is O(1),
> or prepend instead of append to a List, then reverse the result.
> Each prepend is O(1) and reverse is O(n), so the overall complexity
> is O(n). Of course, prepending when you really want to append
> makes for harder-to-read code, hence the suggestion of using
> ListBuffer.
>
> You might like to implement List yourself in some other language to
> get a good idea of how Scala's works and why certain things are
> slow enough to deprecate.
>
> 2009/2/27 Sciss
> "Richard T. Farmer School of Business" ?
>
> a pity, i'm trying to switch to scala.collection.immutable.List
> whereever possible. i still don't understand why that doesn't
> define an append( elem: A ) method... (could have any other name,
> like 'add')
>
> still haven't ordered my book, broke ATM :-/ doesn't EPFL offer
> grants for scala based projects? ...
>
> ciao, -sciss-
>
>
> Am 27.02.2009 um 09:26 schrieb Detering Dirk:
>
>
> martin odersky
> In that case you really should use a ListBuffer, not a List.
>
> Hey Sciss,
>
> in a nice way Martin told us: RTFSB * :-)
>
> KR
> Det
>
>
> * Read The Fine Stairway Book - precisely: Chapter 22.2 Page 494
>
>
>

On Fri, Feb 27, 2009 at 9:15 AM, Sciss <contact@sciss.de> wrote:

i thought List keeps a Head and Tail field?

Yes, it does. the head is the head of the list, the tail is, well, the tail of a list.

i.e. given List(1, 2, 3, 4) the head is 1 and the tail is List(2, 3, 4).

What it doesn't keep is a reference to the last element. But there's no reason for it to be. Basically by definition, appending to the end of an immutable singly linked list has to create a new list of N + 1 elements, so has to be O(N)

An immutable doubly linked list wouldn't have this property. Instead it would have the property that appending to either the front or the end of the list would be an O(N) - you'd have to recreate the entire list in either direction.

if not, isn't there any such immutable linked list,

What you want is not an immutable linked list. You want an immutable persistent vector structure like a finger tree, but unfortunately there's none in the standard library (I think daniel spiewak has one? Maybe there will be one in 2.8)

In the meantime, my recommendation would be to append with a ListBuffer and then convert to a List when you're done. Or turn the problem around and prepend to the list.
 

or is that a contraction (immutable / linked)?

It's not a contradiction. It's just that immutable and mutable linked lists behave fairly differently.

ok, got it... i'm using prepend now since it's ok in that particular
application to reverse the order.

Am 27.02.2009 um 12:35 schrieb David MacIver:

> On Fri, Feb 27, 2009 at 9:15 AM, Sciss wrote:
> i thought List keeps a Head and Tail field?
>
> Yes, it does. the head is the head of the list, the tail is, well,
> the tail of a list.
>
> i.e. given List(1, 2, 3, 4) the head is 1 and the tail is List(2,
> 3, 4).
>
> What it doesn't keep is a reference to the last element. But
> there's no reason for it to be. Basically by definition, appending
> to the end of an immutable singly linked list has to create a new
> list of N + 1 elements, so has to be O(N)
>
> An immutable doubly linked list wouldn't have this property.
> Instead it would have the property that appending to either the
> front or the end of the list would be an O(N) - you'd have to
> recreate the entire list in either direction.
>
> if not, isn't there any such immutable linked list,
>
> What you want is not an immutable linked list. You want an
> immutable persistent vector structure like a finger tree, but
> unfortunately there's none in the standard library (I think daniel
> spiewak has one? Maybe there will be one in 2.8)
>
> In the meantime, my recommendation would be to append with a
> ListBuffer and then convert to a List when you're done. Or turn the
> problem around and prepend to the list.
>
> or is that a contraction (immutable / linked)?
>
> It's not a contradiction. It's just that immutable and mutable
> linked lists behave fairly differently.

In principle, it is possible that both append and prepend are O(1),
might I also add "of course".

Now (::)'s head is just an element, while tail is a list. Another List's
implementation could just do the opposite, i.e. have a list as head and
an element as tail. So, list could be prepending by returning a "::",
and appending by returning a instance of that other class, both in
constant time.

Unfortunately, this would complicate current patterns such as:
xss match {
case x :: xs => ...
}

There is also the possibility of a List-like implementation with head
and tail both being Lists, with an implementation of singleton lists too
(along with Nil). Which would also not be able to take advantage of
pattern matching. This would be rather costly though.

Anyway, if someone needs fast appends and prepends, perhaps should
create such a structure, and not depend scala's List.

(I have a similar implementation here:
http://139.91.183.8:3026/hudson/job/FlexiGraph/ws/flexigraph/trunk/main/...
where "Path" is the analog of such a List, and the elements of it (which
can only be nodes and edges) are converted to singleton paths, and can
be appended/prepended in constant time)

O/H Ricky Clarkson έγραψε:
> Please describe what should happen when you append an element to an
> immutable List.
>
> 2009/2/27 Sciss >
>
> i thought List keeps a Head and Tail field? if not, isn't there
> any such immutable linked list, or is that a contraction
> (immutable / linked)?
>
> Am 27.02.2009 um 10:12 schrieb Ricky Clarkson:
>
>
> Appending to a singly linked list is an O(n) operation.
> Appending n elements is O(n^2).
>
> A far better mechanism is to append to a ListBuffer, which is
> O(1), or prepend instead of append to a List, then reverse the
> result. Each prepend is O(1) and reverse is O(n), so the
> overall complexity is O(n). Of course, prepending when you
> really want to append makes for harder-to-read code, hence the
> suggestion of using ListBuffer.
>
> You might like to implement List yourself in some other
> language to get a good idea of how Scala's works and why
> certain things are slow enough to deprecate.
>
> 2009/2/27 Sciss >
> "Richard T. Farmer School of Business" ?
>
> a pity, i'm trying to switch to
> scala.collection.immutable.List whereever possible. i still
> don't understand why that doesn't define an append( elem: A )
> method... (could have any other name, like 'add')
>
> still haven't ordered my book, broke ATM :-/ doesn't EPFL
> offer grants for scala based projects? ...
>
> ciao, -sciss-
>
>
> Am 27.02.2009 um 09:26 schrieb Detering Dirk:
>
>
> martin odersky
> In that case you really should use a ListBuffer, not a List.
>
> Hey Sciss,
>
> in a nice way Martin told us: RTFSB * :-)
>
> KR
> Det
>
>
> * Read The Fine Stairway Book - precisely: Chapter 22.2 Page 494
>
>
>
>
>

O/H David MacIver έγραψε:
> What it doesn't keep is a reference to the last element. But there's
> no reason for it to be. Basically by definition, appending to the end
> of an immutable singly linked list has to create a new list of N + 1
> elements, so has to be O(N)
I just sent an email without reading this reply. I don't understand what
definition you refer to. Why can't you just create a (custom) list with
a "head" and "tail", where head is the existing immutable list, and
"tail" the element to be appended? O(1).
>
> An immutable doubly linked list wouldn't have this property. Instead
> it would have the property that appending to either the front or the
> end of the list would be an O(N) - you'd have to recreate the entire
> list in either direction.
This also should be O(1). Perhaps you implicitly add some constraints in
the design (that force you back to O(n)) which are unclear to me.

O/H Dimitris Andreou έγραψε:
> O/H David MacIver έγραψε:
>> What it doesn't keep is a reference to the last element. But there's
>> no reason for it to be. Basically by definition, appending to the end
>> of an immutable singly linked list has to create a new list of N + 1
>> elements, so has to be O(N)
> I just sent an email without reading this reply. I don't understand
> what definition you refer to. Why can't you just create a (custom)
> list with a "head" and "tail", where head is the existing immutable
> list, and "tail" the element to be appended? O(1).
>>
>> An immutable doubly linked list wouldn't have this property. Instead
>> it would have the property that appending to either the front or the
>> end of the list would be an O(N) - you'd have to recreate the entire
>> list in either direction.
> This also should be O(1). Perhaps you implicitly add some constraints
> in the design (that force you back to O(n)) which are unclear to me.
>
I think I got what the constraints you imply are: to specifically form a
single chain, as in a totally unbalanced left- (or right-)oriented tree,
while with what I proposed, the same list could be represented with many
more different trees than just those (I don't handily remember the
cardinality of all the representations)

On Fri, Feb 27, 2009 at 12:58, Dimitris Andreou <jim.andreou@gmail.com> wrote:

O/H David MacIver έγραψε:

What it doesn't keep is a reference to the last element. But there's no reason for it to be. Basically by definition, appending to the end of an immutable singly linked list has to create a new list of N + 1 elements, so has to be O(N)

I just sent an email without reading this reply. I don't understand what definition you refer to. Why can't you just create a (custom) list with a "head" and "tail", where head is the existing immutable list, and "tail" the element to be appended? O(1).

An immutable doubly linked list wouldn't have this property. Instead it would have the property that appending to either the front or the end of the list would be an O(N) - you'd have to recreate the entire list in either direction.

This also should be O(1). Perhaps you implicitly add some constraints in the design (that force you back to O(n)) which are unclear to me.

Well you could _create_ the list O(1) maybe, but then some of it's methods will become more complex.

Just try to work out in your head an implementation that only creates a new list on appends/prepends and that is immutable. I think you'll see that it's just not doable. You either need to make complete copies in the append/prepend method or you have to start creating lists when calling tail().

(at least, that's what I think, don't take my word for it)

--

-Tako

Dimitris Andreou schrieb:
> In principle, it is possible that both append and prepend are O(1),
> might I also add "of course".
[...]
> Anyway, if someone needs fast appends and prepends, perhaps should
> create such a structure, and not depend scala's List.

That structure is called a deque, and can be implemented with most important
operations being O(1) worst case:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.3451

- Florian

O/H Tako Schotanus έγραψε:
>
>
> On Fri, Feb 27, 2009 at 12:58, Dimitris Andreou > wrote:
>
> O/H David MacIver έγραψε:
>
> What it doesn't keep is a reference to the last element. But
> there's no reason for it to be. Basically by definition,
> appending to the end of an immutable singly linked list has to
> create a new list of N + 1 elements, so has to be O(N)
>
> I just sent an email without reading this reply. I don't
> understand what definition you refer to. Why can't you just create
> a (custom) list with a "head" and "tail", where head is the
> existing immutable list, and "tail" the element to be appended? O(1).
>
>
> An immutable doubly linked list wouldn't have this property.
> Instead it would have the property that appending to either
> the front or the end of the list would be an O(N) - you'd have
> to recreate the entire list in either direction.
>
> This also should be O(1). Perhaps you implicitly add some
> constraints in the design (that force you back to O(n)) which are
> unclear to me.
>
>
> Well you could _create_ the list O(1) maybe, but then some of it's
> methods will become more complex.
Sure. You optimize for your most common usage patterns.
But also keep in mind that the amortized cost of accessing any element
of a tree is the same, regardless of the tree's structure, so this is
always a limit for what "more complex" means.
>
> Just try to work out in your head an implementation that only creates
> a new list on appends/prepends and that is immutable. I think you'll
> see that it's just not doable.
Not doable? I have already implemented it.
> You either need to make complete copies in the append/prepend method
> or you have to start creating lists when calling tail().
>
> (at least, that's what I think, don't take my word for it)
I think Florian's link answers the issues you raise, I copy it here again:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.3451
(Thanks!)

>

On Friday February 27 2009, Ricky Clarkson wrote:
> Please describe what should happen when you append an element to an
> immutable List.

Clojure's immutable, persistent vectors and hash maps have good
amortized modification (perhaps "augmentation" would be a better term?)
behavior and share content between the original and the "modified"
result.

I don't know the detail of the data structures and algorithms used.

Naturally, cons-cell lists prepend immutably without any extra effort.
And in an immutable setting (Clojure certainly and Scala's immutables,
presumably) you'd not have replaca or replacd or any other destructive
operations list / cons cell operations, either.

Randall Schulz

For a good introduction to functional data structures, I recommend this
View this message in context: Re: Why is List:+ deprecated?
Sent from the Scala - User mailing list archive at Nabble.com.

On Friday February 27 2009, Dave Griffith wrote:
> For a good introduction to functional data structures, I recommend
>521663504/>

Thanks.

For those on limited budgets, I found this excerpt / overview of the
same title and author:

Using that title ("Purely Functional Data Structures") as a Google
Scholar search finds many seemingly interesting papers and books.

Randall Schulz

There is also Okasaki's (similarly titled) theses here:
http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

O/H Randall R Schulz έγραψε:
> On Friday February 27 2009, Dave Griffith wrote:
>
>> For a good introduction to functional data structures, I recommend
>> 521663504/>
>>
>
> Thanks.
>
> For those on limited budgets, I found this excerpt / overview of the
> same title and author:
>
>
>
>
> Using that title ("Purely Functional Data Structures") as a Google
> Scholar search finds many seemingly interesting papers and books.
>
>
> Randall Schulz
>
>

On Friday February 27 2009, Dimitris Andreou wrote:
> There is also Okasaki's (similarly titled) theses here:
> http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
>

Thanks. Theses are the best!

> O/H Randall R Schulz έγραψε:
> > ...

I love seeing different language's words for "wrote." Would that
transliterate to something like "ecrapse?" It suggests a long-ago
common root with the English "scribe" and its derivatives / relatives.

Randall Schulz

On Fri, Feb 27, 2009 at 14:29, Dimitris Andreou <jim.andreou@gmail.com> wrote:

O/H Tako Schotanus έγραψε:

On Fri, Feb 27, 2009 at 12:58, Dimitris Andreou <jim.andreou@gmail.com <mailto:jim.andreou@gmail.com>> wrote:

   O/H David MacIver έγραψε:

       What it doesn't keep is a reference to the last element. But
       there's no reason for it to be. Basically by definition,
       appending to the end of an immutable singly linked list has to
       create a new list of N + 1 elements, so has to be O(N)

   I just sent an email without reading this reply. I don't
   understand what definition you refer to. Why can't you just create
   a (custom) list with a "head" and "tail", where head is the
   existing immutable list, and "tail" the element to be appended? O(1).


       An immutable doubly linked list wouldn't have this property.
       Instead it would have the property that appending to either
       the front or the end of the list would be an O(N) - you'd have
       to recreate the entire list in either direction.

   This also should be O(1). Perhaps you implicitly add some
   constraints in the design (that force you back to O(n)) which are
   unclear to me.


Well you could _create_ the list O(1) maybe, but then some of it's methods will become more complex.

Sure. You optimize for your most common usage patterns.
But also keep in mind that the amortized cost of accessing any element of a tree is the same, regardless of the tree's structure, so this is always a limit for what "more complex" means.

Just try to work out in your head an implementation that only creates a new list on appends/prepends and that is immutable. I think you'll see that it's just not doable.

Not doable? I have already implemented it.

You either need to make complete copies in the append/prepend method or you have to start creating lists when calling tail().

(at least, that's what I think, don't take my word for it)

I think Florian's link answers the issues you raise, I copy it here again:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.3451
(Thanks!)

Yeah, I read it, quite interesting.
Obviously (and luckily) there are people  a lot smarter than me.

The only thing I can be glad of is that the solution at least isn't too obvious :)

Cheers,
 -Tako

Randall R Schulz schrieb:
> On Friday February 27 2009, Dimitris Andreou wrote:
>> O/H Randall R Schulz έγραψε:
>>> ...
> It suggests a long-ago
> common root with the English "scribe" and its derivatives / relatives.

Actually, it is a form of http://en.wiktionary.org/wiki/γράφω which is cognate with
English carve and derived from Proto-Indo-European *gerbʰ- while scribe is derived
from PIE *skrībʰ- via Latin http://en.wiktionary.org/wiki/scribo

And it is, to be even marginally on-topic, a valid identifier name:

scala> val έγραψε = 1
έγραψε: Int = 1

More fun with unicode:

scala> val e = 1
e: Int = 1

scala> val е = 2
е: Int = 2

scala> e == е
res0: Boolean = false

- Florian.

IIRC, a more familiar cognate would be "graph", as in "calligraphy",
and "photography".

-jn-

On Sat, Feb 28, 2009 at 5:01 AM, Florian Hars wrote:
> Randall R Schulz schrieb:
>>
>> On Friday February 27 2009, Dimitris Andreou wrote:
>>>
>>> O/H Randall R Schulz έγραψε:
>>>>
>>>> ...
>>
>> It suggests a long-ago common root with the English "scribe" and its
>> derivatives / relatives.
>
> Actually, it is a form of http://en.wiktionary.org/wiki/γράφω which is
> cognate with
> English carve and derived from Proto-Indo-European *gerbʰ- while scribe is
> derived
> from PIE *skrībʰ- via Latin http://en.wiktionary.org/wiki/scribo
>
> And it is, to be even marginally on-topic, a valid identifier name:
>
> scala> val έγραψε = 1
> έγραψε: Int = 1
>
> More fun with unicode:
>
> scala> val e = 1
> e: Int = 1
>
> scala> val е = 2
> е: Int = 2
>
> scala> e == е
> res0: Boolean = false
>
> - Florian.
>

On Fri, Feb 27, 2009 at 8:29 AM, Dimitris Andreou wrote:
> I think Florian's link answers the issues you raise, I copy it here again:
> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.3451
> (Thanks!)

VLists are another structure that fits in this area.

But here is a simple implementation based on IntMap:

object IntMapDeque {

import scala.collection.immutable.IntMap;

/** A double ended queue. This implementation uses a backing IntMap and
* is limited to about 2^30 endeque/deque pairs before
* it slides off the underlying IntMap.
*/

class Deque[+A](private val imap:IntMap[A]) extends Seq[A]{

private lazy val start:Int=if (isEmpty) Deque.center+1 else imap.firstKey;
private lazy val end:Int=if (isEmpty) Deque.center else imap.lastKey;

/** Returns the n-th element of this deque.
* The first element is at position 0.
*
* @param n index of the element to return
* @return the element at position n in this deque.
* @throws Predef.NoSuchElementException if the deque is too short.
*/
def apply(n: Int): A = {
get(n) match {
case None => throw new NoSuchElementException("element "+n+" not found");
case Some(a) => a;
}
}

/** Returns the n-th element of this deque.
* The first element is at position 0.
*
* @param n index of the element to return
* @return the element at position n in this deque.
* @throws Predef.NoSuchElementException if the deque is too short.
*/
def get(n: Int): Option[A] = imap.get(start+n);

/* this is like apply, but this uses underlying indexes */
private def lookup(n:Int):A = imap.get(n) match {
case None =>
{
if (isEmpty) {
throw new NoSuchElementException("deque empty");
} else {
// can't happen
throw new NoSuchElementException("element with private index
"+n+" not found");
};
}
case Some(a) => a;
}

/** Returns the elements in the list as an iterator
*/
def elements: Iterator[A] = imap.values

/** Checks if the deque is empty.
*
* @return true, iff there is no element in the deque.
*/
override def isEmpty: Boolean = imap.isEmpty;

/** Returns the length of the deque.
*/
def length = imap.size;

override def size=imap.size;

/** Creates a new deque with element added at the end
* of the old deque. This is the same as push.
*
* @param elem the element to insert
*/
def +[B >: A](elem: B) = push(elem)

/** Creates a new deque with element added at the end
* of the old deque. This is the same as push.
*
* @param elem the element to insert
*/
def enqueue[B >: A](elem: B) = push(elem);

/** Creates a new deque with element added at the end
* of the old deque. This is the same as push.
*
* @param elem the element to insert
*/
def push[B >: A](elem: B) = new Deque(imap.update(end + 1,elem));

/** Returns a tuple with the last element in the deque,
* and a new deque with this element removed.
*
* @throws Predef.NoSuchElementException
* @return a tuple with the last element of the deque
* and the rest of the Deque
*/
def pop:(A,Deque[A]) = (lookup(end),new Deque(imap-end));

/** Creates a new deque with element added at the front
* of the old deque.
*
* @param elem the element to insert
*/
def unshift[B >: A](elem: B) = new Deque(imap.update(start-1,elem));

/** Returns a tuple with the first element in the Deque,
* and a new deque with that element removed.
*
* @throws Predef.NoSuchElementException
* @return a tuple with the first element of the Deque
* and the rest of the Deque
*/
def shift:(A,Deque[A]) = (lookup(start),new Deque(imap-start));

/** Same as shift.
*
* @throws Predef.NoSuchElementException
* @return a tuple with the first element of the Deque
* and the rest of the Deque
*/
def dequeue: (A, Deque[A]) = shift

/** Returns the first element in the Deque, or throws an error if there
* is no element contained in the queue.
*
* @throws Predef.NoSuchElementException
* @return the first element.
*/

def front: A =apply(0);

override def first:A=front;
override def firstOption:Option[A]=get(0);
override def last:A=apply(size-1);
override def lastOption:Option[A]=get(size-1);

override def stringPrefix= "Deque";

/** Compares two deques for equality by comparing
* each element in the deques.
*
* @return true, iff the two deques are structurally equal.
*/
override def equals(o: Any): Boolean = o match {
case q: Deque[_] =>
imap == q.imap;
case _ => false
}

override def hashCode(): Int =imap.hashCode;

}

object Deque{
/* where to start putting elements in the IntMap. 0 would be
obvious, but it
* is an unhappy choice on account of IntMap's sorting by unsigned ints.
*/
private final val center=1<<30;

// should this override equals?
object Empty extends Deque[Nothing](IntMap.empty);

def empty=Empty;
}

}

Nevermind that last version this version is much faster. Still upto
about twice as slow as scala.collection.immutable.Queue, but its O(1)
worst case.

import scala.collection.immutable.IntMap;

object Deque{
/* where to start putting elements in the IntMap. 0 would be
obvious, but it
* is an unhappy choice on account of IntMap's sorting by unsigned ints.
*/
private final val center=1<<30;
val empty =new Deque[Nothing](center,center,IntMap.empty);
}

/** A double ended queue. This implementation uses a backing IntMap and
* is limited to about 2^30 enqueue/deque pairs before
* it slides off the underlying IntMap.
*/

final class Deque[+A](private val start:Int,private val end:Int,
private val imap:IntMap[A]) extends Seq[A]{

/** Returns the n-th element of this deque.
* The first element is at position 0.
*
* @param n index of the element to return
* @return the element at position n in this deque.
* @throws Predef.NoSuchElementException if the deque is too short.
*/
def apply(n: Int): A = {
get(n) match {
case None => throw new NoSuchElementException("element "+n+" not found");
case Some(a) => a;
}
}

/** Returns the n-th element of this deque.
* The first element is at position 0.
*
* @param n index of the element to return
* @return the element at position n in this deque.
* @throws Predef.NoSuchElementException if the deque is too short.
*/
def get(n: Int): Option[A] = {
val ret=imap.get(start+n);
ret;
}
/* these are like apply/get, but this uses underlying/private indexes */
private def lookupOption(n:Int):Option[A] = imap.get(n);
private def lookup(n:Int):A = imap.get(n) match {
case None =>
{
if (isEmpty) {
throw new NoSuchElementException("deque empty");
} else {
// can't happen
throw new NoSuchElementException("element with private index
"+n+" not found");
};
}
case Some(a) => a;
}

/** Returns the elements in the list as an iterator
*/
def elements: Iterator[A] = imap.values

/** Checks if the deque is empty.
*
* @return true, iff there is no element in the deque.
*/
override def isEmpty: Boolean = start==end;

/** Returns the length of the deque.
*/
def length = end-start;

override def size=end-start;

/** Creates a new deque with element added at the end
* of the old deque. This is the same as push.
*
* @param elem the element to insert
*/
def +[B >: A](elem: B) = push(elem)

/** Creates a new deque with element added at the end
* of the old deque. This is the same as push.
*
* @param elem the element to insert
*/
def enqueue[B >: A](elem: B) = push(elem);

/** Creates a new deque with element added at the end
* of the old deque. This is the same as push.
*
* @param elem the element to insert
*/
def push[B >: A](elem: B) = new Deque(start,end+1,imap.update(end,elem));

/** Returns a tuple with the last element in the deque,
* and a new deque with this element removed.
*
* @throws Predef.NoSuchElementException
* @return a tuple with the last element of the deque
* and the rest of the Deque
*/
def pop:(A,Deque[A]) = (last,new Deque(start,end-1,imap-(end-1)));

/** Creates a new deque with element added at the front
* of the old deque.
*
* @param elem the element to insert
*/
def unshift[B >: A](elem: B) = new
Deque(start-1,end,imap.update(start-1,elem));

/** Returns a tuple with the first element in the Deque,
* and a new deque with that element removed.
*
* Shift 'shifts' the index of all elements.
*
* @throws Predef.NoSuchElementException
* @return a tuple with the first element of the Deque
* and the rest of the Deque
*/
def shift:(A,Deque[A]) = (first,new Deque(start+1,end,imap-start));

/** Same as shift.
*
* @throws Predef.NoSuchElementException
* @return a tuple with the first element of the Deque
* and the rest of the Deque
*/
def dequeue: (A, Deque[A]) = shift

/** Returns the first element in the Deque, or throws an error if there
* is no element contained in the queue.
*
* @throws Predef.NoSuchElementException
* @return the first element.
*/

def front: A =apply(0);

override def first:A=lookup(start);
override def firstOption:Option[A]=lookupOption(start);
override def last:A=lookup(end-1);
override def lastOption:Option[A]=lookupOption(end-1);

override def stringPrefix= "Deque";

/** Compares two deques for equality by comparing
* each element in the deques.
*
* @return true, iff the two deques are structurally equal.
*/
override def equals(o: Any): Boolean = o match {
case q: Deque[_] =>
imap == q.imap;
case _ => false
}

override def hashCode(): Int =imap.hashCode;

// override def toString=
super.toString+"["+start+","+end+","+(end-start)+"]";
}