Write this accumuator in a functional style
Rustom Mody
rustompmody at gmail.com
Wed Jul 12 03:32:16 EDT 2017
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)
More information about the Python-list
mailing list