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