Write this accumuator in a functional style

[Alain Ketterlin]

Steven D'Aprano <steve at pearwood.info> writes:

> 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?

Here is a sketch in OCaml-style (incomplete of course):

type color = Blue | Green | Red;;
type parrot = { c: color; ... };;

let rec collect list_of_parrots =
    match list_of_parrots with
    | nil -> (nil,nil,nil)
    | h :: q ->
        let b,g,r = collect q in
        match h with
        | {c=Blue}  -> (h::b,g,r)
        | {c=Green} -> (b,h::g,r)
        | {c=Red}   -> (b,g,h::r)
;;

The function returns a triple of lists in this case. The first match
drives list-traversal, the second selects between colors. Both can be
(sub-optimally) turned into cascades of "if", i.e., in Python:

def collect(list_of_parrots):
    if not list_of_parrots:
        return [],[],[]
    else
        b,g,r = collect(list_of_parrots[1:])
        h = list_of_parrots[0]
        if h.color == 'blue':
            return ([h]+b,g,r)
        elif h.color == 'green':
            ... and so on

-- Alain.