StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>No such function exists that is useful. You want a function <code>enc : X → Y</code> and <code>dec : Y → X</code> so that</p> <pre><code>∀ x ∈ X: dec(enc(x)) = x </code></pre> <p>(that is, <code>dec</code> is the inverse of <code>enc</code>),</p> <p>with the additional constraint that</p> <pre><code>∀ x ∈ X : dec(enc(enc(x))) = x </code></pre> <p>Therefore, <code>X = Y</code> and <code>enc(x) = x</code>!</p> <p>The <code>enc</code> and <code>dec</code> functions are <em>the same</em>, and are the <em>unit function</em> (the function that returns its input):</p> <pre><code>enc(x) = x dec = enc </code></pre> <hr> <p>What does this mean in practical terms? Let's assume we have an escaping scheme that backslashes the forbidden characters <code>'</code> and <code>\</code>. So we have</p> <pre><code>enc( 'foo\ ) = \'foo\\ </code></pre> <p>Now let's assume the user inputs a string <code>\'foo\\</code>, then the escaped output should be</p> <pre><code>enc( \'foo\\ ) = \\\'foo\\\\ </code></pre> <p>Which is the same result as <code>enc(enc( 'foo\ ))</code>.</p> <p>There is no way to tell for this function whether it is an output of <code>enc</code> or not.</p> <p>This changes when <code>X ≠ Y</code> (i.e. the output of <code>enc</code> has a different type than unencoded input). Let us define a polymorphic <code>enc</code> like so:</p> <pre><code>enc : X → Y | Y → Y dec : Y → X ∀ x ∈ X : dec(enc(x)) = x ∀ x ∈ X : dec(enc(enc(x))) = x ∀ y ∈ Y : enc(y) = y </code></pre> <p>In most programming languages, this could be implemented with object orientation:</p> <pre><code>class Str { method enc() : EncodedStr { some encoding code } } class EncodedStr { method enc() : EncodedStr { return self } // the unit function method dec() : Str { some decoding code } } </code></pre> <p>That is, <code>∀ x ∈ Str : x.enc.enc.dec = x</code> etc..</p> <p>The abstract concepts of this answer can be summarized as</p> <blockquote> <p>You simply have to remember if you already encoded that input or not.</p> </blockquote>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload