Slices time complexity

[Rustom Mody]

On Tuesday, May 19, 2015 at 1:20:55 AM UTC+5:30, Ian wrote:
> It may be possible that lists in CPython could be made to share their
> internal arrays with other lists on a copy-on-write basis, which could
> allow slicing to be O(1) as long as neither list is modified while the
> array is being shared. I expect this would be a substantial piece of
> work, and I don't know if it's something that anybody has looked into.

One fundamental difference/choice in language semantics is copy vs reference
C#/.Net call it value-type and reference-type. [The names may be a bit odd...]

Functional languages OTOH tend to the philosophy:
- maximise sharing internally
- mutability taboo
which has its own costs -- eg 'obvious' data structures like arrays become hard/impossible

Its quite likely that your proposal - slices as COW-views -- will have 
significant penalties in other usage scenarios.  Imagine plastering more and 
more complex slice-views on an array inter-mixed with updates.

I must say I am impressed by C#/.Net for making the value/object distinction
first-class all the way from language to VM.