[Python-ideas] Adding a functional list type to the standard library.

[Alexandre Vassalotti]

Hello,

I would like to have your opinion whether a functional list type would
be welcomed in the standard library. A functional list type would
provide an efficient data-structure for keeping many lists with
partial modifications. In particular, a such data-structure would be
obsolete many, if not all, use-cases of copy.deepcopy on lists. Here
is a simple example how a such list would be used:

  # The constructor does a deep conversion of the list to its internal
representation.
  state = FunctionalList([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12],
[13, 14, 15, None]])
  print(goal[0])   # This would print a FunctionalList object, i.e.,
FunctionalList([1, 2, 3, 4])

  # Do a lazy copy of the list.
  new_state = state.copy()

  # Modify the list—many (possibly all) unchanged items are shared between
  # the original list and its copy. The original list remains unchanged.
  new_state[3][3] = new_state[3][2]
  new_state[2][3] = None

  # Show the unchanged list. This prints:
  #   FunctionalList([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12],
[13, 14, 15, None]])
  print(state)

  # Show the modified list. This prints:
  #   FunctionalList([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, None],
[13, 14, 15, 12]])

Attentive readers will remark the above example comes from a attempt
of an 15-puzzle solver. There are many use-cases for a such
data-structure. In particular, any problem that requires backtracking
search would be benefit from having a functional list. Peter Norvig
[1], for example, had to resort to use strings to implement his soduku
solver efficiently. Fortunately for him, the state of a soduko puzzle
fits well in a string as each soduko's cell can be stored in a single
single character. For more complex problems, using strings is not
always a suitable option.

Also, it would also be interesting to consider the addition of
functional dictionaries and sets as well. These twos would probably
more useful to have since the most common usage of copy.deepcopy seems
to be on dictionaries. [2] Finally, I would like to say that I am
willing to write a Python and an optimized C implementation of my
proposal.

Regards,
-- Alexandre

[1]: http://norvig.com/sudoku.html
[2]: http://google.com/codesearch?q=copy\.deepcopy+lang:python