Haskell list comprehension code#

What gives then? Should this not indicate that A should run faster than B? (we naively expect A to perform similarly to C, given that they implement the same constraints). Where we see the enumeration range from a given induction variable ds3_dxb to 1000, as opposed to remaining as a static range ( ).

In comparing A.core and B.core, we immediately see a familiar structure (a nested pair of recursive functions each called over an enumeration) and in-fact, it appears that the core output for A and B are nearly identical! The difference, it seems, lies in the innermost Of note, we can see that in B.core we seeĬorresponding to a naive filter of all the possible values conforming to our constraint, whereas in C.core, we instead have:Ĭase GHC.Classes.$fOrdInteger ds8_dxj ds3_dxfĬorresponding to the addition of an extra >= constraint before our triplet constraint, and hence searching through fewer integers for a shorter runtime, just as our intuition expects. We call each of these defined functions on an enumeration of the Īnd perform our logic within the innermost defined function.

Next, we define a pair of nested recursive functions with signature: If we compare B.core and C.core, we'll note that both files have roughly the same structure:īegin by calling a few familiar functions (System.IO.print. Lets dump the core for our 3 programs (sans optimizations): Now, since we can't always trust our intuition we should investigate what's really going on in the generated GHC Core. We might think then that A should run faster than B (as indeed, it should run similarly to C). here we have it encoded as the range of values b may attain in the List Monad). The next is a bit trickier: It appears that A has the same constraint as C ( b >= a), but encoded differently (i.e.

Haskell list comprehension code#

Presumably, the check for whether or not b >= a produces a little bit of extra code (the comparison) that is outweighed by computation avoided by running the comparison, hence we note a (slight) speed-up. We can rationalize this by noting that instead of ranging over every possibly permuted pair a, b (of which we know there are 1000^2=1000000 possible pairs) we instead do not consider all those cases where b is smaller than a. Intuitively, this means that the search space traversed in C is smaller than that of B. We'll begin with the simplest: C has an extra constraint ( b >= a) relative to B. Let's name the three programs A, B and C respectively.