| Your post goes in several stages. First you create an accumulator version of map that reverses the result: > It’s a bit more verbose, but it’s not that bad. Honestl… Sorry, what did you say? Wrong order? Oh, right… Then you modify that version to accumulate a reversed result, but reverse it (into the correct order) before returning it: > we’ll just add a small List.reverse on the accumulator at the very end… It will hurt performance quite a bit but correctness is more important. Then you reject that solution: > Surely we can do better than this, right?! Let’s take a look at how List.map is implemented in the core library. > The order is right because the list is being visited in reverse order (that’s what foldr does, in contrast to foldl). But we need to look at the implementation of List.foldr to see if we can reuse the same idea for our custom functioOH GOD CLOSE THE TAB! You then complain that the implementation of foldr is too complex to generalize. But it's the same thing you've already explained: accumulate the result, but reverse the list so that when you report the result it's in the right order. This will easily generalize to any other function you care to write. The standard progression, by the way, as other comments in the thread have pointed out, goes from a recursive solution, to a tail-recursive solution, to a tail-recursive solution with an accumulator, to a tail-recursive solution written in continuation-passing style. Continuations provide the structure to hold your "holes" until they can be filled in. Why didn't you mention this? |
For foldr, I mean that specific implementation - which fully prioritizes performance and uses several levels of unwrapping, etc. - is hard to reuse for functions we wish to maintain. Using List.foldr is fine (when applicable, which is not always), but copy-pasting its implementation to adapt it to our need isn't, from a maintenance point of view.
On the topic of continuation-passing style, I don't personally believe that the solution I've highlighted uses CPS. At least from my shallow understanding, CPS uses functions, which my solution doesn't. CPS can easily emulate TRMC, but TRMC works differently (and is more performant though is applicable to less situations).
My understanding of CPS is maybe shallow, so I could be missing some understanding, but to me they're different and therefore not part of my explanation.
> Continuations provide the structure to hold your "holes" until they can be filled in
That's one mental model to view it, but there isn't actually any "real" hole to fill with CPS, whereas with TRMC there is (at least for data construction).