Databases
StackOverflow2013
Postsdbo
POHaskell Constant Propagation on Data Structures?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHaskell Constant Propagation on Data Structures?
    primarykey
    data
    text
    <p>I want to know how deeply Haskell evaluates data structures at compile time.</p> <p>Consider the following list:</p> <pre><code>simpleTableMultsList :: [Int] simpleTableMultsList = [n*m | n &lt;- [1 ..9],m &lt;- [1 ..9]] </code></pre> <p>This list gives a representation of the multiplication table for 1 through 9. Now, suppose we want to change it so that we represent the product of two one digit numbers as a pair of numbers (first digit, second digit). Then we may consider</p> <pre><code>simpleTableMultsList :: [(Int,Int)] simpleTableMultsList = [(k `div` 10, k `rem` 10) | n &lt;- [1 ..9],m &lt;- [1 ..9],let k = n*m] </code></pre> <p>Now we can implement multiplication on one digit numbers as a table lookup. YAY!! However, we want to be more efficient than this! So we want to make this structure an unboxed array. Haskell gives a really great way to do this using </p> <pre><code>import qualified Data.Array.Unboxed as A </code></pre> <p>Then we can do:</p> <pre><code>simpleTableMults :: A.Array (Int,Int) (Int,Int) simpleTableMults = A.listArray ((1,1),(9,9)) simpleTableMultsList </code></pre> <p>Now if I want a constant time multiplication of two one digit numbers n and m, I can do:</p> <pre><code>simpleTableMults ! (n,m) </code></pre> <p>This is great! Now suppose I compile this module we've been working on. Does the simpleTableMults get fully evaluated so that when I run the computation simpleTableMults ! (n,m), the program literally makes a lookup in memory ... or does it have to build the data structure in memory first. Since it is an unboxed array, my understanding is that the Array must be created at once and is completely strict in its elements -- so that all the elements of the array are fully evaluated. </p> <p>So really my question is: when does this evaluation occur, and can I force it to occur at compile time?</p> <p>------- Edit ---------------</p> <p>I tried to dig further on this! I tried compiling and examining information about the core. It seems GHC is performing a lot of reductions on the code at compile time. I wish I knew more about core to be able to tell. If we compile with</p> <pre><code>ghc -O2 -ddump-simpl-stats Main.hs </code></pre> <p>We can see that 98 beta reductions are performed, an unpack-list operation is carried out, many things are unfolded, and a bunch of inlines are performed (around 150). It even tells you where the beta reductions occur, ... since the word IxArray is coming, I am more curious if some sort of simplification is occuring. Now the interesting thing from my point of view is that adding </p> <pre><code>simpleTableMults = D.deepseq t t where t = A.listArray ((1,1),(9,9)) simpleTableMultsList </code></pre> <p>increases the number of beta reductions, inlines, and simplifications quite substantially at compile time. It would be really great if I could load the compiled into a debugger of some sort and "view" the data structure! I am, as it stands, more mistified than before.</p> <p>------ Edit 2 -------------</p> <p>I still don't know what beta reductions are being performed. However, I did find out some interesting things based on sassa-nf's repsonse response. For the following experiment, I used the ghc-heap-view package. I changed the way Array was represented in the source according to the Sassa-NF answer. I loaded the program into GHCi, and immediately called </p> <pre><code>:printHeap simpleTableMults </code></pre> <p>And as expected got a index too large exception. But under the suggested unpacked datatype, I got a let expression with a toArray and a bunch of _thunks, and some _funs. Not really sure yet what these mean ... The other interesting thing is that by using seq, or some other strictness forcing in the source code, I ended up with all _thunks inside of the let. I can upload the exact emission if that helps.</p> <p>Also, if I perform a single indexing, the array gets completely evaluated in all cases.</p> <p>Also, there is no way to call ghci with optimizations, so I might not be getting the same results as when compiled with GHC -O2.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USJonathan Gallagher
    1. USJonathan Gallagher
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHaskell Constant Propagation on Data Structures?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POHaskell Constant Propagation on Data Structures?
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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