[racket] I don't understand structural recursion.

From: Damien Lee (charlicon at gmail.com)
Date: Sat Sep 17 19:54:32 EDT 2011

Thanks all for the comments. I have solved the problem now. I suppose I 
should refrain from posting my full solution, though I am worried it's a 
bit hacky and inelegant. Basically, I found that the lists contained 
elements suitable of permuting about the leaves of the partial trees. It 
wasn't much code at all, but I imagine there's a better way.

On 18/09/11 00:00, Todd O'Bryan wrote:
> Something else to think about is how you get from one answer to the next.
> For example, it looks like (distinct-trees 2) is just (distinct-trees
> 1) with a new tree added as both a left and right child. Ask yourself
> how (distinct-trees 3) is related to (distinct-trees 2), how
> (distinct-trees 4) is related to (distinct-trees 3), etc.

I admit, I did notice the strikingly recursive nature of the problem 
after my pencil and paper experiments. At first, it reminded me of 
Fibonacci numbers and I was expecting to use memoization. I struggled to 
split the computation into pieces and emit distinct trees with this 
approach however, but I'd imagine it would be significantly more 
pleasant than my recursively nested mappings, the mechanics of which I 
fear I'll forget after a nights  sleep.

That tool was neat, but I found it made a lot of the computation too 
explicit for my brain. Perhaps worryingly, I like to think I have an /*a 
posteriori*/ notion of how the recursion will unfold. It turned out that 
I needed a better visualisation of the structures. I don't know what 
happened, but the tracer language emitted the structures in a list form, 
whereas the racket language emitted them in a #<tree> form, and I was 
relying on the parenthesised dot notation. The list notation allowed me 
to see what I was missing.

In this instance, I was gagging for a tree visualisation of my data, but 
I can appreciate that such a feature would likely be too specific for 
most use cases. I'm tempted to make a Graphviz library for cases like 
this. I noticed some code from the Git repo in play/blame_incremental 
but it doesn't seem to have been abstracted into a useful library, yet.

It would also be nice if the source code browser would omit commented 
sections of code.

Thanks again for all the help.

Posted on the users mailing list.