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

 From: John Clements (clements at brinckerhoff.org) Date: Tue Sep 30 04:07:22 EDT 2008 Previous message: [plt-scheme] HtDP: Question on 10.1.9 Next message: template for output <-> inversion problem (was: Re: [plt-scheme] HtDP: Question on 10.1.9) Messages sorted by: [date] [thread] [subject] [author]

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

 Posted on the users mailing list. Previous message: [plt-scheme] HtDP: Question on 10.1.9 Next message: template for output <-> inversion problem (was: Re: [plt-scheme] HtDP: Question on 10.1.9) Messages sorted by: [date] [thread] [subject] [author]