StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The difference in behavior is not specified by the Haskell standard. All it has to say is that the functions are the same (will result in the same output given the same input).</p> <p>However in this case there is a simple way to predict time and memory performance that most compilers adhere to. Again I stress that this is not essential, only that most compilers do it.</p> <p>First rewrite your two examples as pure lambda expressions, expanding the section:</p> <pre><code>f = let fA = listArray ... in \n -> fA ! n f' = \n -> let fA = listArray ... in fA ! n </code></pre> <p>Compilers use let binding to indicate sharing. The guarantee is that in a given environment (set of local variables, lambda body, something like that), the right side of a let binding with no parameters will be evaluated at most once. The environment of fA in the former is the whole program since it is not under any lambda, but the environment of the latter is smaller since it is under a lambda.</p> <p>What this means is that in the latter, fA <em>may</em> be evaluated once for each different n, whereas in the former this is forbidden. </p> <p>We can see this pattern in effect even with multi argument functions:</p> <pre><code>g x y = (a ! y) where a = [ x ^ y' | y' <- [0..] ] g' x = (\y -> a ! y) where a = [ x ^ y' | y' <- [0..] ] </code></pre> <p>Then in:</p> <pre><code>let k = g 2 in k 100 + k 100 </code></pre> <p>We might compute 2^100 more than once, but in:</p> <pre><code>let k = g' 2 in k 100 + k 100 </code></pre> <p>We will only compute it once.</p> <p>If you are doing work with memoization, I recommend data-memocombinators on Hackage, which is a library of memo tables of different shapes, so you don't have to roll your own.</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