>>881
O(n)だと思う。参照されなくなったリストはGCによって回収されるので。
Haskellのリストは書き換えられない。破壊的に更新したいなら専用のデータ構造が要る、例えば
http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Array-IO.html

>>882
列挙型の値を指定するというのが良く分からん。列挙値はそれ自体で値じゃないか？
Cのenum { a = 3};みたいな指定がしたいということなら、それは不可能。
必要なら整数と相互変換する関数を書けば良い。

>列挙型の値の名前空間というかスコープは、グローバルということでしょうか。
そう。正確にはモジュールレベル。