Some operations that are efficient on lists and less efficient on arrays:
cons(q,l)
append(l1,l2) (also shares structure of l2 with other uses)
delete(b,l)
merge sort
Some operations that are efficient on arrays and less efficient on lists:
l[n]
l[n]: 5
binary search
in-place sort
For small lists/arrays, in many applications, it simply doesn't
matter. I agree with Robert that we should move to a system where the
abstract concept is primary, and the underlying implmentation
secondary. Ideally, we would have representation be "advice" to the
system which does not change semantics, only performance, e.g.
declare( li, listarray)
declare( ar, arrayarray)
li: ar: [1,2,3]$
length(li) = length(ar) = 3
li => [1,2,3]
ar => [1,2,3]
append(li,ar) => [1,2,3,1,2,3]
(what are the sharing semantics here?)
(what is the representation of the intermediate result?)
etc.
-s