StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Let's start a bit simpler, with a function that produces all sets of the given size from the given list elements:</p> <pre><code>getAllSets :: [Int] -> Int -> [[Int]] getAllSets _ 0 = [[]] getAllSets xs n = [(x:ys) | x <- xs, ys <- getAllSets xs (n-1)] </code></pre> <p>You can think of this function as building the sets one element at a time. It adds <code>x</code> onto the front of each shorter set <code>ys</code>, and it does this for as many elements as there are in <code>xs</code>.</p> <p>What we can do to get the final answer is decide to not build a longer set for each element in <code>xs</code>, but only for those <code>x</code> that are less than or equal to every element in <code>ys</code>:</p> <pre><code>getSets :: [Int] -> Int -> [[Int]] getSets _ 0 = [[]] getSets xs n = [(x:ys) | x <- xs, ys <- getSets xs (n-1), all (x <=) ys] </code></pre> <p>This is a nice-looking solution, but it does more work than we actually need. After all, why compare <code>x</code> against every element in <code>ys</code>? We know that <code>ys</code> is already in the right order because we've built it that way recursively, so let's just make sure <code>x</code> is less than or equal to the first element of <code>ys</code>, if there is one:</p> <pre><code>getSets' :: [Int] -> Int -> [[Int]] getSets' _ 0 = [[]] getSets' xs n = [(x:ys) | x <- xs, ys <- getSets' xs (n-1), null ys || x <= head ys] </code></pre> <p><strong>Update</strong>: In addition to incorporating Thomas M. DuBuisson's much cleaner predicate, I also benchmarked his, chrisdb's, and my solutions: <a href="http://hpaste.org/50195" rel="nofollow">http://hpaste.org/50195</a></p> <p><strong>Update x2</strong>: Fixed incorrect Criterion labels; benchmarks were correct but the output was confusing.</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