Efficient functional list iteration in Python
Question: So suppose I have an array of some elements. Each element have some number of
properties.

I need to filter this list from some subsets of values determined by
predicates. This subsets of course can have intersections. I also need to
determine amount of values in each such subset.

So using imperative approach I could write code like that and it would have
running time of 2*n. One iteration to copy array and another one to filter it
count subsets sizes.

    
    
    from split import import groupby
    
    a = [{'some_number': i, 'some_time': str(i) + '0:00:00'} for i in range(10)]
    
    
    # imperative style
    
    wrong_number_count = 0
    wrong_time_count = 0
    
    for item in a[:]:
        if predicate1(item):
            delete_original(item, a)
            wrong_number_count += 1
    
        if predicate2(item):
            delete_original(item, a)
            wrong_time_count += 1
    
        update_some_data(item)
    
    do_something_with_filtered(a)
    
    
    def do_something_with_filtered(a, c1, c2):
        print('filtered a {}'.format(a))
        print('{} items had wrong number'.format(c1))
        print('{} items had wrong time'.format(c2))
    
    
    def predicate1(x):
        return x['some_number'] < 3
    
    
    def predicate2(x):
        return x['some_time'] < '50:00:00'
    

Somehow I can't think of the way to do that in Python in functional way with
same running time. So in functional style I could have used groupby multiple
times probably or write a comprehension for each predicate, but that's
obviously would be slower than imperative approach.

I think such thing possible in Haskell using Stream Fusion (am I right?) But
how do that in Python?


Answer: Yes, fusion in Haskell will often turn something written as two passes into a
single pass. Though in the case of lists, it's actually foldr/build fusion
rather than stream fusion.

That's not generally possible in languages that don't enforce purity, though.
When side effects are involved, it's no longer correct to fuse multiple passes
into one. What if each pass performed output? Unfused, you get all the output
from each pass separately. Fused, you get the output from both passes
interleaved.

It's possible to write a fusion-style framework in Python that will work
correctly if you promise to only ever use it with pure functions. But I'm
doubtful such a thing exists at the moment. (I'd loved to be proven wrong,
though.)

