But it would be nice if you could make it O(1) anyway without linked lists.

You could implement cdr as returning a shared hash slice. With some XS hacking you can probably make it work for some cases. Though you may have to make arrays immutable to do it right :-)

update: it seems to me you could implement this in pure perl using tied arrays. But it would get more inefficient for each slice-of-a-slice-of-a-slice.