You can also re-use some form of balanced binary trees where all interesting operations are doable in log(n) and adding requires about log(n) (mostly internal) nodes to be rebuild. That is worse than the optimum O(1) for linked lists you can reach --- but it's easy to come up with and often good enough.
Instead of working with [a] lists, work with [a] -> [a] prepender functions. So the analogue of [1, 2, 3] is f: \x -> [1 2 3] ++ x. Then the analogue of the append of f and 4 is f . (\x -> [4] ++ x), where the . represents composition. Appending using these analogues, I believe, is O(1) instead of O(n).
To "evaluate" an element of this "closure space", just apply it to the empty list.