Write this accumuator in a functional style

[Terry Reedy]

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