# 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>