Is a memoized pure function itself considered pure

Yes, it is possible, depending on the language.

In JavaScript, you can tell if a function is pure by the following criteria:

• It only reads parameters and locals;

• It only writes locals;

• On non-locals, it calls only pure functions;

• All functions it calls implicitly are pure, e.g., toString; and

• It only writes properties of locals if they do not alias non-locals.

Aliasing is not possible to determine in JavaScript in the general case, because you can always look up properties of an object dynamically (object["property"]). Provided you never do that, and you have the source of the whole program, then I think the problem is tractable. You would also need information about which native functions have side-effects, such as console.log or most anything involving the DOM.

The term “pure” could also use some clarification. Even in a strongly, statically typed, purely functional programming language, where all functions are referentially transparent, a function can still fail to terminate. So when we talk about id :: a -> a, what we’re really saying is not:

Given some value of type a, the function id produces a value of type a.

But rather:

Given some value of type a, the function id does not produce a value which is not of type a.

Because a valid implementation of id is error "Not implemented!". As Peteris points out, this nontotality could be seen as a kind of impurity. Koka is a functional programming language—with syntax modelled on JavaScript—which can infer possible effects such as divergence (nontermination), referential transparency, throwing of exceptions, and I/O actions.

No it is not pure, because it has side effect. Concretely it is calling action on each item. Also, it is not threadsafe.

The major property of pure functions is that it can be called any number of times and it never does anything else than return same value. Which is not your case. Also, being pure means you don't use anything else than the input parameters. This means it can be called from any thread at any time and not cause any unexpected behavior. Again, that is not case of your function.

Also, you might be mistaken on one thing: function purity is not question of pros or cons. Even single doubt, that it can have side effect, is enough to make it not pure.

Eric Lippert raises a good point. I'm going to use http://msdn.microsoft.com/en-us/library/dd264808(v=vs.110).aspx as part of my counter-argument. Especially line

A pure method is allowed to modify objects that have been created after entry into the pure method.

Lets say we create method like this:

int Count<T>(IEnumerable<T> e)
{
    var enumerator = e.GetEnumerator();
    int count = 0;
    while (enumerator.MoveNext()) count ++;
    return count;
}

First, this assumes that GetEnumerator is pure too (I can't really find any source on that). If it is, then according to above rule, we can annotate this method with [Pure], because it only modifies instance that was created within the body itself. After that we can compose this and the ApplyIterator, which should result in pure function, right?

Count(ApplyIterator(source, action));

No. This composition is not pure, even when both Count and ApplyIterator are pure. But I might be building this argument on wrong premise. I think that the idea that instances created within the method are exempt from the purity rule is either wrong or at least not specific enough.