2 ms·
Mapfilter
- paulgb 18y ago> Doing a map and then a filter is O(2N), whereas mapfilter is O(N). That’s twice as a fast! O(2N) is O(N). The function F would have to be as or more trivial than a boolean comparison for the speed to double. > Does mapfilter exist in any programming language? In python, you can use list comprehensions and generators to accomplish this, although it is a bit kludgy: [fx for fx in (f(x) for x in lst) if fx] In haskell you can just use the regular map and filter constructs and the lazyness will ensure that the list is only iterated over once.
- japerk 18y agoYes, saying it's twice as fast is a bit simplistic. And O(2N) is theoretically the same as O(N), but in practice, if you have a large list of IDs that need to be looked up in a database to do the map and the filter, mapfilter can approach "twice as fast" (how close depends on the map function). This is my general use case, and the reason I wrote a mapfilter function. It's cool that haskell can do a single iteration by being lazy. I do wish erlang could do lazy iteration and generators.