dlist provides Data.DList, a list type supporting O(1) append and snoc operations.
darcs get http://code.haskell.org/~dons/code/dlist