Re: Decent datastructure for queue operations

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.

--

Lisp is not dead, it just smells funny.

Real email: (replace (subseq "spamtrap@xxxxxxxxxx" 5) "edi")
.

Relevant Pages

  • 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: 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)
  • Re: When is Xah going to ease up on Emacs...
    ... there are many concepts how to build trees with lists. ... I don't understand the syntax. ... You can achieve this in Common Lisp just with a quote in front of the list. ... only the leaf nodes holds data. ...
    (comp.lang.lisp)
  • Re: the necessity of Lisps Objects?
    ... Lists have a data syntax that can be printed and read. ... When the lisp system prints a list ... If you print the Mathematica list and then read it back. ... independent implementations of the programming language ...
    (comp.lang.lisp)
  • Re: Program compression
    ... In Common Lisp it's just one line of code: ... In OCaml with OCaml's notation: ... In Common Lisp, it's another one line of code: ... Consider parsing Mathematica expressions including lists, rules, sums, ...
    (comp.programming)