You can represent the list as a zipper data structure[1]. The idea is to represent a "cursor" pointing to some point in the list as a triple: (list of points be

You can represent the list as a zipper data structure[1]. The idea is to represent a "cursor" pointing to some point in the list as a triple: (list of points before, point at current position, list of points after). So a zipper for an arbitrary list "xs" pointing to the beginning would be (() (car xs) (cdr xs)). There are some things you can do to handle the case with empty lists, which I'll leave to the reader :). Given a zipper (as x bs) you can move the cursor right (rather, compute the zipper with the cursor one step further to the right, since we're purely functional) as ((cons x as) (car bs) (cdr bs)). You can insert a new element "y" into you current position by computing (as y (cons x bs)). If you discard the old version of the zipper every time you move or insert, this will use the same amount of memory as just storing the list, and you get insertions in O(N) time and O(1) memory. There's a whole field devoted to making data structures like this for purely functional languages, and this zipper concept extends itself rather naturally to trees. [1]https://en.wikipedia.org/wiki/Zipper_%28data_structure%29 https://en.wikipedia.org/wiki/Zipper_%28data_structure%29