Counting elements that satisfy property
Source file: filter-length.futSuppose we wish to count the number of positive integers in some array. We might write the following:
let number_pos (xs: []i32) =
0) xs) length (filter (>
This is inefficient, because the program will manifest the result of the filter in memory. A better solution is to rewrite this as a map
-reduce
composition, where we turn positive integers into 1
and others into 0
:
let number_pos_better (xs: []i32) =
if x > 0 then 1 else 0) xs) i64.sum (map (\x ->
This is much more efficient, because the map
can be fused into the reduce
that is used to implement i64.sum
.
We can write it more concisely by using a built-in function to convert booleans to integers:
let number_pos_best (xs: []i32) =
0) >-> i64.bool) xs) i64.sum (map ((>
And of course, we can factor all of this into a handy function:
let count p xs =
i64.sum (map (p >-> i64.bool) xs)
And now we can define our original function as follows:
let count_number_pos (xs: []i32) =
0) xs count (>
See also
Reducing the result of a filter, Scattering the result of a filter.