Implementating vs. understanding

Solving a problem and actually understanding what the problem is do not always go hand by hand. Many times not just the problem eludes understanding, but even the solution we just wrote.
Sometimes this is the case when we are dealing with an elusive bug that only happens under very specific conditions, and by the time you realize that something is wrong it is already too late. And then in desperation you change code here and there or rewrite a piece of code... and the problem seems to go away (has it really or is it just playing hide and seek?)

But that can also happen with simple problems. I was asked, out of the blue as a thinking exercise, to provide a solution to a simple problem: Given a single linked list, provide a function that reverses the list in place. Oh, well, that is an easy problem to solve... should have a solution in 20 seconds.

Imagine a list of nodes, linked by a next pointer, and finished in a NULL pointer. To reverse each node you just need to keep pointers to the previous node, the node and the next node, then you make it point back to the previous node, and you advance the list pointer and you

cannot see the forest for the trees

Having to provide an answer in a few seconds has that effect, you work out the details, forget the problem. And you produce a solution:


Then the next day I was cycling to work, and I thought that lists and functional programming tend to go hand by hand, so how would a functional programming solution to the problem look like?


This solves the problem, but not efficiently. The recursion can turn to be expensive, can we turn this into tail recursion? Tail recursion is good, it avoids the need for the call stack providing a restricted form of continuation passing style and the compiler can avoid holding to the stack. Compilers can turn tail recursion into much cheaper loops.


To avoid holding to state until the function returns we can just pass that state in. The first argument is the input list, the second argument the reversed list. We take one element from the input list and put it at the beginning of the reversed list. When the input list is empty, just return whatever is already reversed. I added an extra function so that the signature matches that of the original problem.

Epiphany

Wow, now I understand the problem and I understand the original solution. The problem is not moving pointers around. The solution is to iteratively remove one element from the head of the input list and insert it at the head of the reversed list.


When you have a problem that can be stated in simple terms, the answer should be explainable in similar terms. High level languages have that characteristic, they let you focus on the problem, rather than the nuisances of the implementation. If you have to explain the answer as detailed technical steps, you don't really understand it.