While I haven’t done a thorough historical survey, I have looked a little bit into the question of what languages first had functional collections, and how they worked.
Lists in Lisp programs can be, and often are, used functionally, though even early Lisps had
mutating operators (then called rplaca (“replace car”) and rplacd (“replace
cdr”); in CL they are called (setf car) and (setf cdr)). So with that caveat,
I think Lisp has to be considered as among the first.
But the earliest language I am aware of that had resizable collections with language-enforced functional semantics was APL (1962). Its collections were restricted to be arrays of numbers; assignment of an array in one variable to another variable copied the contents, preventing aliasing.
Another early language with functional collections was SETL (1969). This was, to my knowledge, the
first language with collection semantics influenced by set theory. SETL strongly influenced a
little-known proprietary language called Refine that I worked in a lot between 1987 and 2003;
Refine, in turn, strongly influenced the design of FSet. In particular, the operator names
with and less come to FSet from SETL via Refine.
(Wikipedia’s SETL page tells me that SETL influenced another language called ABC, which Guido van Rossum has referred to as “Python’s predecessor”. Alas, while ABC’s collections had value semantics, Python’s built-in collections have reference semantics. An opportunity lost, I’d call that.)