template for output <-> inversion problem (was: Re: [plt-scheme] HtDP: Question on 10.1.9)

On Sep 19, 2008, at 7:08 AM, Matthias Felleisen wrote:

>  	
> Here I am responding to myself -)
>
> This problem is a bit of a "look ahead" or "cheat" given to where I  
> am posing it.
>
> Why? In general, it's a "parsing" problem and as such deserves a  
> "structural output" recipe. PLAI is the correct place to look for  
> this. For "freshmen" it's too challenging.
>
> ** The structure of the INPUT does not help you at all when you  
> solve this problem.
>
> ** The structure of the OUTPUT though suggests an organization and  
> arithmetic operations that help.

More generally; it would appear to me that this inversion  
(structuring the program around the output rather than the input)  
occurs whenever the program you're defining is the inverse of a nice  
simple structural recursion.  In the case of parsing, it's the  
inverse of a simple flattening operation.

This also provides another way to look at a function that consumes a  
number and produces a list of the given length (containing arbitrary  
data); it's just the inverse of length.

Of course, most of the HtDP functions are not 1-to-1, hence not  
invertible, so this is pretty rarely useful.

This is all fairly obvious, I suppose, but I've never heard parsing  
described as the inversion of a flattening function, or the  
difficulty of parsing described as being a consequence of the  
difficulty (or impossibility) of inverting a simple structurally  
recursive flatten operation.

I suppose in a logic language you could just define the flatten  
function and run it backwards.

John Clements

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2484 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20080930/5cb94b80/attachment.p7s>