osdir.com


[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Write this accumuator in a functional style


On Tuesday, July 11, 2017 at 4:11:50 PM UTC+5:30, Alain Ketterlin wrote:
> Steven D'Aprano 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)
> ;;

Separating the recursion from the pattern-match-to-discriminate
[Also its in haskell since I dont have an *ML handy]

Code
-------------
data Color   = Red|Blue|Green deriving (Show)
type Species = String
type Status  = String
type Parrot  = (Color, Species, Status)

-- discriminating cons
discons :: Parrot -> ([Parrot], [Parrot], [Parrot]) -> ([Parrot], [Parrot], [Parrot])
discons p@(Red,_,_) (r,g,b)   = (p:r, g, b)
discons p@(Green,_,_) (r,g,b) = (r, p:g, b)
discons p@(Blue,_,_) (r,g,b)  = (r, g, p:b)

-- Loop
disc :: [Parrot] -> ([Parrot], [Parrot], [Parrot])
disc = foldr discons ([],[],[])

-------------

Run:
-------------
?> let parrotlist = [(Blue, "norwe", "happy"), (Green, "austral", "tired"), (Red, "amer", "god-knows")] 
?> disc parrotlist
([(Red,"amer","god-knows")],[(Green,"austral","tired")],[(Blue,"norwe","happy")])
?> 
-----------------

Getting it into python would need a foldr (python's reduce is a foldl)
There is an identity
foldl op id l = foldr (flip op) id (reverse l)
However for this we need the list to be a real (finite) list; not an iterator/infinite etc

OTOH I suspect the spec as returning a bunch of lists is more likely to be
a bunch of bags (Counter in python); in which case foldr can be replaced by foldl(reduce)