Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>When you write <code>[1..1000000]</code>, what GHC really does is create an object that contains <code>1</code> and <code>1000000</code> that describes how to build the list of interest; that object is called a "thunk". The list is only built as necessary to satisfy case scrutinees; for example, you might write:</p> <pre><code>printList [] = putStrLn "" printList (x:xs) = putStrLn (show x) &gt;&gt; printList xs main = printList [1..1000000] </code></pre> <p>Which evaluates like this:</p> <pre><code>main = { definition of main } printList [1..1000000] = { list syntax sugar } printList (enumFromTo 1 1000000) = { definition of printList } case enumFromTo 1 1000000 of [] -&gt; putStrLn "" x:xs -&gt; putStrLn (show x) &gt;&gt; printList xs = { we have a case, so must start evaluating enumFromTo; I'm going to skip a few steps here involving unfolding the definition of enumFromTo and doing some pattern matching } case 1 : enumFromTo 2 1000000 of [] -&gt; putStrLn "" x:xs -&gt; putStrLn (show x) &gt;&gt; printList xs = { now we know which pattern to choose } putStrLn (show 1) &gt;&gt; printList (enumFromTo 2 1000000) </code></pre> <p>Then you'd find that <code>1</code> was printed to the console, and we'd start from near the top with <code>enumFromTo 2 1000000</code> instead of <code>enumFromTo 1 1000000</code>. Eventually, you'd get all the numbers printed and it would come time to evaluate</p> <pre><code>printList (enumFromTo 1000000 1000000) = { definition of printList } case enumFromTo 1000000 1000000 of [] -&gt; putStrLn "" x:xs -&gt; putStrLn (show x) &gt;&gt; printList xs = { skipping steps again to evaluate enumFromTo } case [] of [] -&gt; putStrLn "" x:xs -&gt; putStrLn (show x) &gt;&gt; printList xs = { now we know which pattern to pick } putStrLn "" </code></pre> <p>and evaluation would be finished.</p> <p>The reason we need streams is a bit subtle. The original paper, <a href="http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.104.7401" rel="nofollow noreferrer">Stream fusion: From lists to streams to nothing at all</a>, probably has the most complete explanation. The short version is that when you have a long pipeline:</p> <pre><code>concatMap foo . map bar . filter pred . break isSpecial </code></pre> <p>...it's not so obvious how to get the compiler to compile away all the intermediate lists. You might notice that we can think of the lists as having a sort of "state" that's being iterated, and that each of these functions, rather than traversing a list, is just changing the way the state gets modified on each iteration. The <code>Stream</code> type tries to make this explicit, and the result is stream fusion. Here's how it looks: we first convert all these functions into stream versions:</p> <pre><code>(toList . S.concatMap foo . fromList) . (toList . S.map bar . fromList) . (toList . S.filter pred . fromList) . (toList . S.break isSpecial . fromList) </code></pre> <p>then observe that we can always annihilate <code>fromList . toList</code>:</p> <pre><code>toList . S.concatMap foo . S.map bar . S.filter pred . S.break . fromList </code></pre> <p>...and then the magic happens because the chain <code>S.concatMap foo . S.map bar . S.filter pred . S.break</code> builds up an iterator explicitly rather than building it implicitly by internally building and then immediately annihilating actual lists.</p>
    singulars
    1. This table or related slice is empty.
    1. POHaskell: Lists vs Streams
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USChris Martin
    1. USDaniel Wagner
    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. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI've had a look at the `Data.Vector.Fusion.Stream` source, and I can't find `fromList` and `toList`. My feeling is that `Data.Vector.Fusion.Stream` avoids creating lists in the first place. Is that wrong?
      singulars
      1. PO
      1. USClinton
    2. CO@Clinton I'm not really sure what part of my post made you think I'm suggesting that stream fusion goes via lists. It's quite the opposite: list fusion goes via streams. Getting list fusion right is the whole reason streams exist, as I tried to explain in my answer.
      singulars
      1. PO
      1. USDaniel Wagner
    3. COThe part of the comment where the you said: "The Stream type tries to make this explicit, and the result is stream fusion. Here's how it looks: we first convert all these functions into stream versions: (toList . S.concatMap foo . fromList)...". But when I look at the source of `Data.Vector.Fusion.Stream`, I can't find such a conversion.
      singulars
      1. PO
      1. USClinton
 

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