Here is an answer in the CS Theory Stack Exchange that explains how: https://cstheory.stackexchange.com/a/18399/13730 https://cstheory.stackexchange.com/a/18399

Here is an answer in the CS Theory Stack Exchange that explains how: https://cstheory.stackexchange.com/a/18399/13730 https://cstheory.stackexchange.com/a/18399/13730 (I'm not endorsing it as a practical way of doing it, mind you.) The idea is that the only explicit recursion is contained in generic combinators "fold_result" and "unfold_result" that are "boring" in the sense that they can be derived mechanically from the "resultF" data type and do not actually know about the binary search; they just do recursion. In practice, folds and unfolds tend to be more useful for other things.