[racket] I don't understand structural recursion.
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.
@sk
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.