StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Note that while Russel's Paradox helps to suggest that this might be non-computable, it still fails even if you change it to <code>s = [e | e <- x, elem e s]</code>.</p> <p>Here's an instructive manual expansion. For any non-empty list, <code>x</code></p> <pre><code>s = [e | e <- x, not (e `elem` s)] </code></pre> <p>simplifies to</p> <pre><code>s = do e <- x guard (not (e `elem` s)) return e s = x >>= \e -> if (not (e `elem` s)) then return e else mzero s = concatMap (\e -> if (not (e `elem` s)) then [e] else []) x s = foldr ((++) . (\e -> if (not (e `elem` s)) then [e] else [])) [] x s = foldr (\e xs -> if (not (e `elem` s)) then (e:xs) else xs) [] x s = foldr (\e ys -> if (e `elem` s) then ys else (e:ys)) [] x </code></pre> <p>which we can then begin evaluating. Since <code>x</code> was non-empty we can replace it with <code>x:xs</code> and inline a <code>foldr</code></p> <pre><code>let f = (\e ys -> if (e `elem` s) then ys else (e:ys)) s = f x (foldr f [] xs) s = (\ys -> if (x `elem` s) then ys else (x:ys)) (foldr f [] xs) s = (\ys -> if (x `elem` f x (foldr f [] xs)) then ys else (x:ys)) (foldr f [] xs) </code></pre> <p>which is where we have our infinite loop—in order to evaluate <code>f x (foldr f [] xs)</code> we must evaluate <code>f x (foldr f [] xs)</code>. You might say that the definition of <code>s</code> is not "productive enough" to kickstart its self-recursion. Compare this to the trick <code>fibs</code> definition</p> <pre><code>fibs = 1:1:zipWith (+) fibs (tail fibs) </code></pre> <p>which is kick-started with <code>1:1:...</code> in order to be "productive enough". In the case of <code>s</code>, however, there's no (simple) way to be productive enough (see Will Ness' comment below for a fiendish workaround).</p> <hr> <p>If we don't have the not there, it just switches the order of the branches on the <code>if</code>, which we never reach anyway.</p>

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