Comment by thaumasiotes | Hacker News Reader

Comment by thaumasiotes | Hacker News Reader

> Yeah, if you run this function, you will notice that the result is in the reverse order of what they should be ([ 3, 2, 1 ] instead of [ 1, 2, 3 ] for instance). And that’s because the last x will be at the very start of the accumulator, and inversely the first x will be at the very end.

> So… 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.

> Surely we can do better than this, right?! Let’s take a look at how List.map is implemented in the core library.

> That’s surprisingly simple. 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!

> Ugh… if you’ve opened the link, you know that we have gone far from the elegant solution described at the beginning.

But List.foldr is using almost exactly the same strategy that is considered and rejected in the early draft of mapHelper. Visit the list in reverse order and then reverse the result. (Technically, reverse the input list and then visit it in reverse order, instead of visiting the input list in reverse order and then reversing the output. foldr's output isn't a list.)

The only difference is that List.foldr will visit the first ~2000 elements of the list in correct order, just in case, and if the list is still going it will give up and reverse it at that point.

How far is that from the solution described at the beginning?

The mapHelper version that was rejected changed the order. The one that did `List.reverse` had the correct order, and this one is equivalent to the List.foldr solution.

The only difference is List.foldr's implementation is more performant (up to a certain number of elements as you say). If this is not what you asked, then I did not understand the question.

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?

Oh ok. I didn't mean to "reject" the solution, since that's what I see done most of the time in practice, because of the current limitations of the language regarding stack safety.

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).

Reply on news.ycombinator.com