data Animal = Animal { name :: String,
is_awake :: Time -> Bool,
lives_in :: Environment -> Bool }
and so on, with the "methods" actually being bound at the time of creation of the Animal. See: http://lukepalmer.wordpress.com/2010/01/24/haskell-antipatte...Other OO things could be built as well in a perfectly functional way, picking and choosing the bits of the definition of OO you want. What you can't do is choose exactly what C++ or Java gives you, and what you don't get is a Blessed Object Orientation Technique like you do with those languages. But you can program OO just as you can in C. (Only better in most ways. Note you don't get a BOOT in C either, but there are nevertheless OO C programs.)
Mutability is merely one dimension of OO, a term that is so flexible it basically means nothing without further qualification. OO has its place even in a functional program sometimes, as that link shows.
We can also define OO as the use of inheritance. The problem with inheritance is that it spurs the violation of decoupling. More often than not, derived classes are tightly coupled to their base class. I don't like that. This paper also suggest that inheritance is not very good, because it would increase the error rate by 6: http://www.leshatton.org/Documents/OO_IS698.pdf (Note that I don't take this paper as a proof that OO is bad in general. Rather, it strongly suggest that C++ without templates nor the STL, used in an OO fashion, is worse than plain C).
Now, if you forbid (or severely limit) both mutable state and inheritance, I really don't see what is left to OO. We could see you `Animal` data type and the Ocaml module system as forms of OO, but at this point, "OO" would mean anything (and therefore be meaningless).
(Note: when I say "I don't like X", I mean I will avoid X as long as the resulting solution isn't demonstrably simpler.)
Check out Erlang's parametrized modules, a form of functional OO.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.58....
Most probably. But there's a reason for that: I don't like mutable state[1]. And I'm not sure you can try to avoid mutable state and still do OO.
[1]: http://www.loup-vaillant.fr/articles/assignment