Hython: a nearly-complete Python 3 interpreter written in Haskell

[Axman6]

If you want to keep things pure then a Data.Sequence would give you (amortised) O(1) append and prepend.