As delnan said, these problems are with using the wrong data structure, such as a linked list when you want a vector.
Your particular operations
append: cons is O(1), so I suspect you are referring to the act of allocating a cons cell, pattern matching on the cell, and eventual GC of the cell. This is rather unavoidable unless you optimize away the list, which does happen in certain situations.
sort: I suggest you look at the ST monad, which allows you to use algorithms that require mutation inside a pure context. See the vsort implementation for an example.
length: Sure, the only way to get the length of a linked list is to traverse the list. If you need the length often then consider using a Set, Map, or Vector - all of which record a total size that can be accessed in O(1).
In General
- Look into
ST
for mutability. - Use the right data structure for the right problem. Learn what structures Hackage has to offer (vectors, arrays, hashmaps, hashtables, bloomfilters, and more).