Re: Decent datastructure for queue operations


Edi Weitz wrote:
> On 31 Jan 2006 01:42:49 -0800, "meng" <meng234@xxxxxxxxx> wrote:
>
> > By the way, LISP has a function `last' which points directly to the
> > last item of a list without needing to traverse it.
>
> No, that's wrong. LAST has to traverse the list and is thus an O(n)
> operation.
>
> We recently had this discussion whether it's possible for an
> ANSI-compliant implementation to internally represent lists in a way
> that would make your behaviour possible. I forgot the outcome but in
> pratice it doesn't matter because all existing Common Lisps do it
> alike.

It seems to me if you want to know the length of the list and rapidly
access the last element you should use a vector instead.

Justin

.

Relevant Pages

  • Re: Cons cell archaic!?
    ... How would the implementation of a Lisp without a using cons look like? ... the irregularity in its often cited regular syntax. ... Lisp at core is based on functional programing on lists. ...
    (comp.lang.lisp)
  • Re: How powerful macros are?
    ... >> for software engineers to use arrays for everything, ... Did I miss something or is #an impossibly unbearable syntax in Lisp? ... and arrays are often slower for very short lists. ... I've also extended the language so that I have re-readable hash tables ...
    (comp.lang.lisp)
  • Re: Cons cell archaic!?
    ... why lisp has the cons problem and was never ... langs that deal with lists, vast majority of list usage is just simple ... and if it's not done in those other languages it must be ... Java and Lisp as languages worth consiering, ...
    (comp.lang.lisp)
  • Re: Lisp collections
    ... If a programming language specification talks about a data type, ... For example, The Common Lisp Hyperspec talks about lists, ... misapprehension that Lisp programmers generally just used lists to store ...
    (comp.lang.lisp)
  • Static or runtime type-checking (was: Program compression)
    ... I know that everything and the kitchen sink has been added to LISP. ... Seed7 seems to be rather limited in what it can easily support. ... list-processing primitives as applied to linked lists (push new ... Only internal types can be checked at compile time. ...
    (comp.programming)