Reducing the result of a filter

Suppose we wish to sum all the positive values of some array. The obvious way to write it is as follows:

def sum_pos (xs: []i32) = reduce (+) 0 (filter (>0) xs)

This gives the right result, but it is not optimal. Since filter is a reasonably expensive operation, it is better to implement this pattern by maping the “removed” elements to the neutral element:

def sum_pos_better (xs: []i32) =
  reduce (+) 0 (map (\x -> if x > 0 then x else 0) xs)

These map-reduce compositions are one of the most efficient parallel programming patterns - quite parallel, and with low execution overhead. If we wish, we can factor this filter-then-reduce strategy into a separate higher-order function:

def reduce_some 'a (op: a -> a -> a) (ne: a) (p: a -> bool) (xs: []a) : a =
  reduce op ne (map (\x -> if p x then x else ne) xs)

Then we can define our function as simply:

def sum_pos_best (xs: []i32) =
  reduce_some (+) 0 (>0) xs

Reducing the result of a filter

See also