Should DRY entail call-by-need evaluation?

By: Jeremy W. Sherman. Published: . Categories: Haskell DRY.

Swift brings Cocoa devs a standard library that includes map, filter, and reduce. But in a strict language such as Swift, you’ll likely find yourself hand-fusing a composition of these operations at some point as a result of profiling-directed performance optimization.

This isn’t new to Swift. Lennart Augustsson observed in 2011 in More points for lazy evaluation:

Strict evaluation is fundamentally flawed for function reuse.

That’s because:

With strict evaluation you can no longer with a straight face tell people: don’t use recursion, reuse the recursion patterns in map, filter, foldr, etc. It simply doesn’t work (in general).

The strict evaluation order means naïve combination of functions will do more work than needed to produce a value: for example, in the case of any, which should short-circuit, reduce must still traverse its entire input.

Using macros doesn’t really save us this time, because of the recursive definitions. I don’t really know of any way to fix this problem short of making all (most?) functions lazy, because the problem is pervasive. I.e., in the example it would not be enough to fix foldr [AKA reduce]; all the functions involved need to be lazy to get the desired semantics.

Strict evaluation gets us a simple space-usage model, but it leaves us holding the bag when it comes to function composition.