Two smaller disagreements and a note: > We take a branch and return the “key not found” value. But now the caller tests the return value against “key not found

Two smaller disagreements and a note: > We take a branch and return the “key not found” value. But now the caller tests the return value against “key not found” and it, too, takes a branch. We only take the true branch in the caller if the true branch was taken in the callee and we only take the false branch in the caller if the false branch was taken in the callee. In essence, we are branching on the exact same condition twice. If we can inline the lambdas, we can inline the lookup. In that case, the sufficiently smart compiler can just as easily tell we're doing "variable = a if test else b; if (variable == a) x else y" and optimize to "if (test) x else y". > It's a bit vacuous to observe that an inlined function performs better. Not necessarily - inlining a cold-path function can blow the instruction cache for no speed benefit. For instance, if the key is almost always going to be found, you may not want to inline the "key not found" lambda on performance grounds. Instead, you should allow the lookup function to assure the compiler that it won't leak its lambda arguments, at which point the closure allocation can be replaced with a stack pointer. > Unfortunately, we cannot declare answer to be an integer because it might be the “key not found” value. Alternatively, we might decide to reserve a special integer to indicate “key not found”. The answer can then be declared an integer, but there is now a magic integer that cannot be stored in the table. In a language with sumtypes: (Value | :notFound) lookup(Key key) { ... } This can be optimized by the compiler to a "special integer" if the Value type doesn't cover the entire integer range. (I believe Rust does this.)