Mark Summerfield <[EMAIL PROTECTED]> writes: > > Yes. It should use a functional data structure. > Could you elaborate?
I mean use a data structure like an AVL tree, that can make a new dict object quickly, whose contents are the same as the old object except for one element (i.e. most of the contents are shared with the old dict). You should also have ordered versions of both lists and sets. Consider the situation with lists: a = some 1000 element list b = a + [23] Now a has 1000 elements and b has 1001 elements (23 followed by a's elements), but constructing b required copying all of a's elements. It's sort of the same with sets: a = 1000 element set b = a + set((23,)) b had to copy the contents of a. By using a tree structure, you can construct b in O(log(1000)) operations so that most of the elements are shared with a, while at the same time you don't mutate a. That makes it a lot easier to program in a style where you have a bunch of slightly different versions of some set or dict flying around. For an example of where this came up, see this thread: http://groups.google.com/group/comp.lang.python/browse_thread/thread/78b5953488d772e9/82f701c302122777 For sample implemetations and API's, you could look at the Hedgehog Lisp version of AVL trees (including a Python dict-like interface): http://hedgehog.oliotalo.fi/ and Haskell's Data.Map library: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Map.html I think there is something similar in the ML Basis library but I'm not familiar with that. For more about functional data structures, see some of Chris Okasaki's articles: http://www.eecs.usma.edu/webs/people/okasaki/pubs.html Dr. Okasaki also has written a book about the topic, called "Purely Functional Data Structures", which is very good. That said, in Python maybe this stuff would be easier to use improperly because Python coding style uses mutation so much. It might be best to limit sharing to the case of frozen dicts and frozen sets. -- http://mail.python.org/mailman/listinfo/python-list
