[Haskell-cafe] using mutable data structures in pure functions

[E R]

Consider the following idea for implementing pure functions:

A pure function can allocate and modify memory as long as a) it never
returns a reference to the memory or b) it never again modifies the
memory once it returns (i.e. it returns an immutable object).

This is based on the idea of "value objects" in object-oriented
languages - the only mutation of a value object occurs in the
constructor. Once the constructor is finished initializing the object
it becomes immutable.

My first question is whether or not this is accurate or does it need
some qualifications / fixing up.

Secondly, where does this idea fit into the Haskell philosophy?

For example, consider the definition of Data.List.nub:

nub l                   = nub' l []
  where
    nub' [] _           = []
    nub' (x:xs) ls
        | x `elem` ls   = nub' xs ls
        | otherwise     = x : nub' xs (x:ls)

Clearly the memory allocated to ls never escapes nub', so it seems
that ls could be replaced with a mutable data structure (with an eye
towards improving performance in special cases).

For another example, consider Data.Map.fromList. I kind of expected
fromList to build up the map using a mutable data structure and then
"seal it up" before returning it, but it seems to call the same insert
that one would call to add to the map after it has been constructed.

So, again, what is the Haskell philosophy towards using mutable data
structures in pure functions? Is it:

1. leave it to the compiler to find these kinds of opportunities
2. just use the immutable data structures - after all they are just as
good (at least asymptotically)
3. you don't want to use mutable data structures because of _____
4. it does happen, and some examples are ______

Thanks,
ER