StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Using your representation of tuples and without much an eye for generalities, here's a solution to your problem.</p> <pre><code>type Square2 a = ((a,a), (a,a)) type Square3 a = ((a,a,a), (a,a,a), (a,a,a)) extend1 :: Num a => Square2 a -> Square3 a extend1 ((a,b), (c,d)) = ( (a, b, ab ) , (c, d, cd ) , (ac, bd, abcd) ) where ab = a + b cd = c + d ac = a + c bd = b + d abcd = ab + cd </code></pre> <p>Note how I use variable definitions culled both from the pattern of the input and the definitions in the <code>where</code> clause. Also notice how I destruct and consume the input while building an entirely new output---some of the elements are reused, but the structure itself is destroyed. Finally note how I chose the type inside of the tuples to be constant and constrained by the <code>Num</code> typeclass which allows me use of <code>(+)</code> for addition.</p> <p>A similar function, generalized and using <code>Array</code>s has a type like</p> <pre><code>extend1A :: Num a => Array (Int,Int) a -> Array (Int, Int) a </code></pre> <p>where we've lost the ability to know the exact size of the <code>Array</code>s but it's indicated that our function takes one <code>Array</code> of some size and returns another <code>Array</code> that is indexed identically and containing the same <code>Num</code>-constrained type.</p> <p>The <code>array</code> function takes as its first argument a set of bounds. We need to update those based on the <code>bounds</code> of the input array</p> <pre><code>extend1A ary0 = array bounds1 ... where ((minX, minY), (maxX, maxY)) = bounds ary0 (maxX1, maxY1) = (succ maxX, succ maxY) bounds1 = ((minX, minY, (maxX1, maxY1)) </code></pre> <p>Then <code>array</code> takes a list of "assocs" as its second argument. We can treat any <code>Array ix a</code> as being equivalent (roughly) to a list of assocs <code>[(ix, a)]</code> which list values stating "at the index <code>ix</code> the value is <code>a</code>". To do this we must know the <code>bounds</code> of the <code>ix</code> type which we managed just previously.</p> <p>To update an array using the information from an old one, we can modify the <code>assocs</code> of the old array to include new information. Concretely, this means that <code>extend1A</code> looks a bit like</p> <pre><code>extend1A ary0 = array bounds1 (priorInformation ++ extraInformation) where priorInformation = assocs ary0 extraInformation = ... ((minX, minY), (maxX, maxY)) = bounds ary0 (maxX1, maxY1) = (succ maxX, succ maxY) bounds1 = ((minX, minY, (maxX1, maxY1)) </code></pre> <p>If <code>extraInformation</code> were empty (<code>[]</code>) then <code>extend1A ary</code> would be equal to <code>ary</code> on all indicies in range of the input <code>ary</code> and <code>undefined</code> on all outside of its range. We need to fill in <code>extraInformation</code> with the summation information.</p> <pre><code>extend1A ary0 = array bounds1 (priorInformation ++ extraInformation) where priorInformation = assocs ary0 extraInformation = xExtension ++ yExtension ++ totalExtension xExtension = ... yExtension = ... totalExtension = ... ((minX, minY), (maxX, maxY)) = bounds ary0 (maxX1, maxY1) = (succ maxX, succ maxY) bounds1 = ((minX, minY, (maxX1, maxY1)) </code></pre> <p>If we think of extending the array in three pieces, the <code>xExtension</code> marked by <code>ab</code> and <code>cd</code> in <code>extend1</code>, the <code>yExtension</code> marked by <code>ac</code> and <code>bd</code> in <code>extend1</code> and the <code>totalExtension</code> marked by <code>abcd</code> in <code>extend1</code> we can then compute each part in turn.</p> <p><code>totalExtension</code> is easiest--it's just the sum of the "value component" of each <code>(i,a)</code> pair in <code>priorInformation</code>. It could also be the sum of the "value component" of either <code>xExtension</code> or <code>yExtension</code>, but in order to be as obviously correct as possible, we'll pick the first choice and install that at the lower-right corner.</p> <pre><code>extend1A ary0 = array bounds1 (priorInformation ++ extraInformation) where priorInformation = assocs ary0 extraInformation = xExtension ++ yExtension ++ totalExtension sumValues asscs = sum (map snd asscs) xExtension = ... yExtension = ... totalExtension = [((maxX1, maxY1), sumValues priorInformation)] ((minX, minY), (maxX, maxY)) = bounds ary0 (maxX1, maxY1) = (succ maxX, succ maxY) bounds1 = ((minX, minY), (maxX1, maxY1)) </code></pre> <p>Note that we can use the <code>where</code> clause to define new functions like <code>sumValues</code> which will show up over and over.</p> <p>Then we can compute the extensions as list comprehensions over the <code>priorInformation</code>. We need to collect a particular kind of sum over the old assocs---summing over all the values where one index is fixed.</p> <pre><code>xExtension = [( (maxX1, yix) , sumValues (filter (\((_, j), _) -> j == yix) priorInformation) ) | yix <- [minY .. maxY] ] yExtension = [( (xix, maxY1) , sumValues (filter (\((i, _), _) -> i == xix) priorInformation) ) | xix <- [minX .. maxX] ] </code></pre> <p>And then we're done. It's not efficient, but all the pieces work together.</p> <pre><code>extend1A ary0 = array bounds1 (priorInformation ++ extraInformation) where priorInformation = assocs ary0 extraInformation = xExtension ++ yExtension ++ totalExtension xExtension = [( (maxX1, yix) , sumValues (filter (\((_, j), _) -> j == yix) priorInformation) ) | yix <- [minY .. maxY] ] yExtension = [( (xix, maxY1) , sumValues (filter (\((i, _), _) -> i == xix) priorInformation) ) | xix <- [minX .. maxX] ] totalExtension = [((maxX1, maxY1), sum xExtension)] ((minX, minY), (maxX, maxY)) = bounds ary0 (maxX1, maxY1) = (succ maxX, succ maxY) bounds1 = ((minX, minY), (maxX1, maxY1)) </code></pre>

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