On 7/11/2017 2:11 AM, Steven D'Aprano wrote:
I have a colleague who is allergic to mutating data structures. Yeah, I
know, he needs to just HTFU but I thought I'd humour him.
Suppose I have an iterator that yields named tuples:
Parrot(colour='blue', species='Norwegian', status='tired and shagged out')
and I want to collect them by colour:
accumulator = {'blue': [], 'green': [], 'red': []}
for parrot in parrots:
accumulator[parrot.colour].append(parrot)
That's pretty compact and understandable, but it require mutating a bunch
of pre-allocated lists inside an accumulator. Can we re-write this in a
functional style?
The obvious answer is "put it inside a function, then pretend it works by
magic" but my colleague's reply to that is "Yes, but I'll know that its
actually doing mutation inside the function".
Help me humour my colleague.
To truly not mutate anything, not even hidden (as in a python list comp,
which buries .append), replace list with linked-list and .append with
head-linkage (Lisp's cons). Something like
blue, green, red = None, None, None
for parrot in parrots:
color = parrot.color
if color == 'blue':
blue = (parrot, blue)
elif color = 'red':
red = (parrot, red)
elif color = 'green':
green = (parrot, green)
else:
raise ValueError(f'parrot {parrot} has unknown color {color}')
At this point, blue, green, and red are linked lists of parrots of the
corresponding color.
Of course, for loops mutate the iterator. Replace that with a tail
recursive function. To make this easy, the input 'parrots' should be a
linked list, which is a recursive data structure. Assignment is also
form of mutation (of a namespace dict), so to be really strict, all the
assignments should be replaced by function calls and returns. That
really requires the use of recursion.
Since this is a thought experiment we can make this easier:
Make accumulator a linked list, perhaps
(('blue':None),(('green',None),(( 'red', None), None)))
Specify that parrots is also a linked list.
Now stipulate the we are using func_py, which compiles Python syntax
such as
for parrot in parrots:
accumulator[parrot.colour].append(parrot)
into a set of recursive functional functions, including tail recursive
'for' such that for(parrots, accumulator) returns a new linked-list.
Note that real functional language compilers do the opposite of this,
compiling tail-recursive syntax into while loops.
--
Terry Jan Reedy
--
https://mail.python.org/mailman/listinfo/python-list
