Write this accumuator in a functional style
Terry Reedy
tjreedy at udel.edu
Tue Jul 11 04:48:35 EDT 2017
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
More information about the Python-list
mailing list