Для дешевых операций вроде добавления
в списки (не символьные строки) я бы используйте Data.DList.
Что меня сдерживает, так это то, что пакет на Hackage помечен как «экспериментальный», а последнее обновление было в 2009 году.
Можно ли использовать DList для этого в Haskell?