Just a small point: it's easy to write a purely functional list with logarithmic time random access. They're called "random access lists", and Chris Okasaki det

Just a small point: it's easy to write a purely functional list with logarithmic time random access. They're called "random access lists", and Chris Okasaki detailed them in his thesis on purely functional data structures. More complicated structures like finger trees or whatever else provide similar benefits.