StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>First of all, you should understand how to interface with haskell arrays. The <code>Array</code> datatype is found in <code>Data.Array</code>, so for full details, look at the docs for that module. </p> <p>Note that I omit the <code>Ix i</code> constraint you would find on all of these functions. It isn't really important for this situation.</p> <p><code>bounds :: Array i e -> (i, i)</code>: This function returns the min and max indices of the array. For a 1D array, these are just numbers. For a 2D array, it the the top left and bottom right corners (for a matrix).</p> <p><code>array :: (i, i) -> [(i, e)] -> Array i e</code>: This function creates an array from a min/max pair for the bounds, and a list of associations; that is, a map from indices to values. Your intial example can be written as <code>array ((0,0),(1,1)) [((0,0),1),((0,1),2),((1,0),3),((1,1),4)]</code></p> <p><code>assocs :: Array i e -> [(i, e)]</code>: This is the 'opposite' of <code>array</code>. So, <code>arr == array (bounds arr) (assocs arr)</code>.</p> <p>Now the function:</p> <pre><code>extendArray :: Num e => Array (Int, Int) e -> Array (Int, Int) e extendArray arr = let arr' = assocs arr ((xMin, yMin), (xMax, yMax)) = bounds arr newCol = [ ((n, yMax + 1) , sum [ v | ((x,_),v) <- arr', x == n] ) | n <- [xMin .. xMax]] newRow = [ ((xMax + 1, n) , sum [ v | ((_,y),v) <- arr', y == n] ) | n <- [yMin .. yMax]] newCorner = [((xMax + 1, yMax + 1), sum $ map snd arr')] newArr = array ((xMin, yMin), (xMax + 1, yMax + 1)) (arr' ++ newCol ++ newRow ++ newCorner) in newArr </code></pre> <p>Lets break down what is happening here. The first two lines in the <code>let</code> statement should be self-explanatory by now. The third line, <code>newCol</code>, is where the magic happens. It uses list comprehensions so if you are unfamiliar with them, see <a href="http://learnyouahaskell.com/starting-out" rel="nofollow">here</a>. </p> <p><code>n <- [xMin .. xMax]</code>: This part gets all the possible x-values.</p> <p><code>[ v | ((x,_),v) <- arr', x == n]</code>: This reads as, for all values in the list <code>arr'</code> such that the x-coordinate of the index is equal to n, return the value at that coordinate.</p> <p><code>((n, yMax + 1) , sum ...</code> Create a new index, whose column is 1 plus the maximum of the old array (so 1 column to the right of the old matrix), whose row is <code>n</code> and whose value is the sum of the previous line (ie - the sum of all the values in row <code>n</code>).</p> <p><code>newRow</code> works the same way, but rows and columns reversed.</p> <p><code>newCorner</code> gets all the values in the matrix, computes their sum, and places this value at the appropriate index in the new array.</p> <p><code>newArr</code> simply combines all the steps into a new array. Obviously the bounds will grow by one in each direction. The associations of the new array are going to include all the old associations, as well as the new ones we have computed. </p> <p>So: </p> <pre><code>>let x = array ((0,0),(1,1)) [((0,0),1),((0,1),2),((1,0),3),((1,1),4)] >x array ((0,0),(1,1)) [((0,0),1),((0,1),2),((1,0),3),((1,1),4)] >extendArray x array ((0,0),(2,2)) [((0,0),1),((0,1),2),((0,2),3),((1,0),3),((1,1),4),((1,2),7),((2,0),4),((2,1),6),((2,2),10)] </code></pre> <p>Note that this implementation isn't efficient (it is however simple). In <code>newRow</code>, we traverse the entire matrix <code>xMax - xMin</code> times (once for each <code>n</code> value). Since <code>assocs</code> always returns elements in the same order (rows from left to right, columns from up to down) it would be better to split the list <code>arr'</code> into lists each with length <code>yMax - yMin</code>; this would get us a list of the rows. But I will leave this optimization to you.</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