Of course, cdr doesn't have to be O(N) if you implement lists like lisp does (in Lisp, lists are just particular arrangements of 2-element cons cells):

# pack 2 elements into a cons cell
# if the second element is a cons cell or undef, the result is conside
+red a list
sub cons {
  [$_[0],$_[1]];
}

# return the first element in a list.
# or to put it another way, return the first of the 2 elements of the 
+given cell
sub car {
  ref $_[0] ? $_[0][0] : undef;
}

# return the "remaining list" (everything except the first element) in
+ a list.
# or to put it another way, return the second element of a cons cell
sub cdr {
  ref $_[0] ? $_[0][1] : undef;
}
[download]

The disadvantage ofcourse is that these lists don't act like perl arrays.

update: fixed the cdr() definition