Adding a functional list type to the standard library.
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
On Sun, Apr 05, 2009, Alexandre Vassalotti wrote:
I would like to have your opinion whether a functional list type would be welcomed in the standard library.
My head hurts. Are you sure you didn't intend to send this four days ago? ;-)
Where is ``goal`` defined? At this point, I'm unable to make any headway on understanding what you're trying here. -- Aahz (aahz@pythoncraft.com) <*> http://www.pythoncraft.com/ "Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." --Brian W. Kernighan
On Sun, Apr 5, 2009 at 2:38 AM, Alexandre Vassalotti <alexandre@peadrop.com>wrote:
If you would find it useful, write it and distribute it as an extension module on PyPi. -- Daniel Stutzbach, Ph.D. President, Stutzbach Enterprises, LLC <http://stutzbachenterprises.com>
Alexandre Vassalotti wrote:
For example, if two new implementations of tuple were added: slice_tuple(parent_tuple, slice) and subst_tuple(parent_tuple, slice, inserted_tuple) to obviate copying the needed parts of the parent_tuple, then: tuple[slice] => return slice_tuple(tuple, slice) tuple.delete(slice) => return subst_tuple(tuple, slice, ()) tuple.with_append(x) => return subst_tuple(tuple, slice(len(tuple), len(tuple)), (x,)) tuple.extended_by(tuple_b) => tuple + tuple_b => return subst_tuple(tuple, slice(len(tuple), len(tuple)), x) tuple.with_subst(slice, tuple_b) => return subst_tuple(tuple, slice, tuple_b) tuple.reversed() => return slice_tuple(tuple, slice(None, None, -1)) If it's not clear, I'm imagining that slice_tuple (for example) be implemented something like: class slice_tuple(base_tuple): def __init__(self, parent_tuple, slice): self.parent = parent_tuple self.step = slice.step or 1 # Convert negative and out of bound slice.starts to make 0 <= self.start < len(self.parent). if slice.start is not None: self.start = slice.start if slice.start >= 0 else slice.start + len(self.parent) if self.start < 0: self.start = 0 elif self.start > len(self.parent): self.start = len(self.parent) else: self.start = 0 if self.step > 0 else len(self.parent) - 1 # Convert negative and out of bound slice.stops to make -1 <= self.stop <= len(self.parent) # and (self.stop >= self.start if self.step > 0 else self.stop <= self.start). if slice.stop is not None: self.stop = slice.stop if slice.stop >= 0 else slice.stop + len(self.parent) if self.step > 0: if self.stop < self.start: self.stop = self.start elif self.stop > len(self.parent): self.stop = len(self.parent) else: if self.stop > self.start: self.stop = self.start elif self.stop < -1: self.stop = -1 else: self.stop = len(self.parent) if self.step > 0 else -1 def __len__(self): if self.step > 0: return (self.stop - self.start + self.step - 1) // self.step return (self.stop - self.start + self.step + 1) // self.step def __getitem__(self, i): if i < 0: i += len(self) if i < 0 or i >= len(self): raise IndexError("tuple index out of range") return self.parent[self.start + i * self.step] ... etc ... -bruce frederiksen
On Sun, Apr 05, 2009, Alexandre Vassalotti wrote:
I would like to have your opinion whether a functional list type would be welcomed in the standard library.
My head hurts. Are you sure you didn't intend to send this four days ago? ;-)
Where is ``goal`` defined? At this point, I'm unable to make any headway on understanding what you're trying here. -- Aahz (aahz@pythoncraft.com) <*> http://www.pythoncraft.com/ "Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." --Brian W. Kernighan
On Sun, Apr 5, 2009 at 2:38 AM, Alexandre Vassalotti <alexandre@peadrop.com>wrote:
If you would find it useful, write it and distribute it as an extension module on PyPi. -- Daniel Stutzbach, Ph.D. President, Stutzbach Enterprises, LLC <http://stutzbachenterprises.com>
Alexandre Vassalotti wrote:
For example, if two new implementations of tuple were added: slice_tuple(parent_tuple, slice) and subst_tuple(parent_tuple, slice, inserted_tuple) to obviate copying the needed parts of the parent_tuple, then: tuple[slice] => return slice_tuple(tuple, slice) tuple.delete(slice) => return subst_tuple(tuple, slice, ()) tuple.with_append(x) => return subst_tuple(tuple, slice(len(tuple), len(tuple)), (x,)) tuple.extended_by(tuple_b) => tuple + tuple_b => return subst_tuple(tuple, slice(len(tuple), len(tuple)), x) tuple.with_subst(slice, tuple_b) => return subst_tuple(tuple, slice, tuple_b) tuple.reversed() => return slice_tuple(tuple, slice(None, None, -1)) If it's not clear, I'm imagining that slice_tuple (for example) be implemented something like: class slice_tuple(base_tuple): def __init__(self, parent_tuple, slice): self.parent = parent_tuple self.step = slice.step or 1 # Convert negative and out of bound slice.starts to make 0 <= self.start < len(self.parent). if slice.start is not None: self.start = slice.start if slice.start >= 0 else slice.start + len(self.parent) if self.start < 0: self.start = 0 elif self.start > len(self.parent): self.start = len(self.parent) else: self.start = 0 if self.step > 0 else len(self.parent) - 1 # Convert negative and out of bound slice.stops to make -1 <= self.stop <= len(self.parent) # and (self.stop >= self.start if self.step > 0 else self.stop <= self.start). if slice.stop is not None: self.stop = slice.stop if slice.stop >= 0 else slice.stop + len(self.parent) if self.step > 0: if self.stop < self.start: self.stop = self.start elif self.stop > len(self.parent): self.stop = len(self.parent) else: if self.stop > self.start: self.stop = self.start elif self.stop < -1: self.stop = -1 else: self.stop = len(self.parent) if self.step > 0 else -1 def __len__(self): if self.step > 0: return (self.stop - self.start + self.step - 1) // self.step return (self.stop - self.start + self.step + 1) // self.step def __getitem__(self, i): if i < 0: i += len(self) if i < 0 or i >= len(self): raise IndexError("tuple index out of range") return self.parent[self.start + i * self.step] ... etc ... -bruce frederiksen
participants (4)
-
Aahz -
Alexandre Vassalotti -
Bruce Frederiksen -
Daniel Stutzbach