Immutability or mutability are not a concepts that make sense in functional programming.
The computational context
This is a very good question that is an interesting follow up (not a
duplicate) to another recent one: What is the difference between
assignment, valuation and name binding?
Rather that replying to your statements one by one, I am trying here
to give you a structured overview of what is at stakes.
There are several issues to be considered to answer you, including:
What is a model of computation, and what concepts make sense for a
given model
What is the meaning of the words you are using, and how does it
depend on the context
Functional programming style seems silly because you see it with an
imperative programmer eye. But it is a different paradigm, and your
imperative concepts and perception are alien, out of place. The
compilers have no such prejudices.
But the end conclusion is that it is possible to write programs in a
purely functional way, including for machine learning, thought
functional programming does not have the concept of storing data. I
seem to disagree on this point with other answers.
In the hope a few will be interested despite the length of this answer.
Computational paradigms
The question is about functional programming (aka applicative
programming), a specific model of computation, whose theoretical and
simplest representative is the lambda calculus.
If you stay at a theoretical level, there are many models of
computation: the Turing machine (TM), the RAM machine and others, the
lambda calculus, combinatory logic, recursive function theory,
semi-Thue systems, etc.
The more powerful computational models have been proved equivalent in
terms of what they can address, and that is the gist of the
Church-Turing thesis.
An important concept is reducing models to each other, which is the
basis for establishing the equivalences that lead to the Church-Turing
thesis. Seen from a programmers perspective, reducing one model to
another is pretty much what is usually called a compiler. If you take
logic programming as your model of computation, it is quite different
from the model provided by the PC you bought in a store, and the
compiler does translate programs written in logic programming language
to the computational model represented by your PC (pretty much the RAM
computer).
However, it does not mean that the two models do things the same ways,
or that a concept meaningful for one can be transferred as such to
another. Typically, a computation step in a TM has little relation to
a ($\beta$-)reduction step in Lambda Calculus, though they are
inter-translatable. The concept of optimal evaluation of lambda
expression is quite remote from complexity issues in TM models.
In practice, the programming languages that we use tend to mix
concepts from different theoretical origins, trying to do it so that
selected parts of a programs can benefit from the properties of some
model where appropriate. Similarly, people building systems may choose
different languages for different components, to best suit the language
to the task at hand.
Hence, you seldom see a programming paradigm in a pure state in a
programming language. Programming languages are still classified
according to the dominant paradigm, but properties of the language may
be affected when concepts from other paradigms are involved, often
blurring distinctions and conceptual issues.
Typically, languages like Haskell and ML or CAML are considered functional,
but they can allow for imperative behavior ... Else why would one talk
of the "purely functional subset"?
Then one can claim that, you can do this or that in my functional
programming language, but it is not really answering a question on
functional programming when it is relying on what can be considered
extra-functional.
The answers should be more precisely related to a specific paradigm,
without the extras.
What is a variable?
Another problem is the use of terminology. In mathematics a variable
is an entity that stand for an undetermined value in some domain. It
is used for various purposes. Used in an equation, it may stand for
whatever value such that the equation is verified. This vision is
used in logic programming under the name of "logical variable",
probably because the name variable already had another meaning when
logic programming was developed.
In traditional imperative programming, a variable is understood as
some kind of container (or memory location) that can memorise the
representation of a value, and possibly get its current value replaced
by another one).
In functionnal programming, a variable has the same purpose it does in
mathematics as a place-holder for some value, yet to be provided. In
traditional imperative programming this role is actually played by
constant (not to be confused with literals which are determined
value expressed with a notation specific to that domain of values,
such as 123, true, ["abdcz",3.14]).
Variables of whatever kind, as well as constant, may be represented by
identifiers.
The imperative variable can have its value changed and that is the
basis for mutability. The functional variable cannot.
Programming languages usually allow for larger entities to be build
from the smaller ones in the language.
Imperative languages allow for such constructs to include variables
and that is what gives you mutable data.
How to read a program
A program is fundamentally an abstract description of your algorithm
is some language, whether a pragmatic design, or a paradigmatically
pure language.
In principle, you can take every statement for what it is supposed to
mean abstractedly. Then the compiler will translate that to some
appropriate form for the computer to execute, but that is not your
problem in first approximation.
Of course, reality is a bit harsher, and it is often good to have some
idea of what happens so as to avoid structures that the compiler will
not know how to deal with for efficient execution. But that is already
optimization ... which compilers can be very good for, often better
than programmers.
Functional programming and mutability
Mutability is based on the existence of imperative variables that can
contains values, to be changed by assignment. Since these do not exist
in functional programming, everything can be seen as immutable.
Fuctional programming deals exclusively with values.
Your first four statements on immutability are mostly correct, but
describe with imperative view something that is not imperative. It is
a bit like describing with colors in a world where every one is blind.
You are using concepts that are alien to functional programming.
You have only pure values, and an array of integers is a pure
value. To get another array that differs only in one element, you
have to use a different array value. Changing an element is just a concept
that does not exists in this context. You may have a function that has
an array and some indices as argument, and returns a result that is an
almost identical array which differs only where indicated by the
indices. But it is still an independent array value. How are these
value represented is not your problem. Maybe they "share" a lot in the
imperative translation for the computer
... but that is the compiler's job ... and you do not even want to
know for what kind of machine architecture it is compiling.
You do not copy values (it make no sense, it is an alien concept).
You just use values that exist in the domains you have defined in your
program. Either you describe them (as literals) or they are the result
of applying a function to some other values. You can give them a name
(thus defining a constant) to make sure the same value is used in
different places in the program. Note that function application should
not be perceived as a computation but as the result of the application
to the given arguments. Writing 5+2
or writing 7
amounts to the same. Which
is consistent with the previous paragraph.
There are no imperative variables. No assignment is possible. You can
bind names to values only (to form constants), unlike imperative
languages where you can bind names to assignable variables.
Whether that has a cost in complexity is totally unclear. For one
thing, you reference to complexity concerns imperative paradigms. It
is not defined as such for functional programming, unless you choose to
read your functional program as an imperative one, which is not the
intent of the designer. Indeed the functional view is intended to let
you not worry about such issues and concentrate on what is being
computed. It is a bit like specification versus implementation.
The compiler has to take care of implementation, and to be smart
enough to best adapt what is to be done to the hardware that will do
it, whatever it is.
I am not saying programmers never worry about that. I am also not
saying that programming languages and compiler technology are as
mature as we might wish them to be.
Answering the questions
You do not modify existing value (alien concept), but compute new
values that differ where desired, possibly by having one extra element
it it is a list.
The program can get new data. The whole point is how you express
that in the language. You can for example consider that the program
works with one specific value, possibly unbounded in size, which is
called the input stream. It is a value that is supposed to be sitting
there (whether it is already known fully or not is not your problem).
Then you have a function that returns a pair composed of the first
element of the stream, and the rest of the stream.
You can use that to build networks of communicating components
in a purely applicative way (coroutines)
Machine learning is just another problem when you have to accrete
data and modify values. In functional programming you do not do that:
you just compute new values that differ appropriately according to the
training data. The resulting machine will work as well. What you worry
about is computing time and space efficiency. But, again, that is a
different issue, that ideally should be dealt with by the compiler.
Final remarks
It is quite clear, from the comments or the other answers, that
practical functionnal programming languages are not purely functional.
That is a reflection on the fact that our technology is still to be
improved, especially where compiling is concerned.
Is it possible to write in a purely applicative style? The answer has
been known for about 40 years and it is "yes". The very purpose of
denotational semantics as it appeared in the 1970's was precisely to
translate (compile) languages into purely functional style, deemed
better understood mathematically and thus considered a better
fundation to define the semantics of programs.
The interesting aspect ot it is that imperative programming structure,
including variables, can be translated into a functional style by
introducing appropriate domains of values, such as a data store.
And despite the functional style, it remains surprisingly similar to
the code of actual compilers written in imperative style.