tl;dr: State is bad for optimizations, FP encourages you to write most of the code state-free.
One of the perks of FP is that it exposes pure functions, functions that have a fixed output for a given input. Since it's really bad at storing and mutating state(canonically can only be done via monads), it encourages you to separate your code into pure and mutable states. Let's take, for instance, a function that reads a file and xor's that with a random byte stream. A non functional approach would be something like this:
void xor_file_stream(file input, stream random_stream){
result = []
file_byte = read_byte(input)
while(file_byte != EOF){
stream_byte = read_byte(random_stream)
res.append(file_byte^stream_byte)
file_byte = read_byte(input)
}return result
}
A possible way to write the same function using FP, using currying[1] and map[2](a fundamental construct in FP), one can write the code as this:
byte xor(byte b1, byte b2){
return byte(byte b2){
return b1^b2
}
}
//Here I assume the language has file and random_stream as iterables
void xor_file_stream(file input,stream random_stream){
return map(map(xor,random_stream),input)
}
While, in a naive implementation, this would be much slower than the procedural implementation, there are much stronger assumptions one can make in respect to the functions while optimizing the compiler. First, the function xor is a pure function with 2^9 possible input values, and can be substituted by a precomputed lookup table, speeding up the map function. Since the function is guaranteed not to hold state, one can also unroll the map loops, or paralelize it if needed.
But remember that most "pure" FP languages are bad at keeping state, turning a huge game(for instance) into a challenge both to the programmer and to the compiler.
[1] - http://en.wikipedia.org/wiki/Currying
[2] - http://en.wikipedia.org/wiki/Map_%28higher-order_function%29
EDIT: Formmating, not used to posting to hackernews comments