Replacing repetitive function applications with deterministic values

Question

f x y z = [n | n <- z, n > x + y]

f 1 2 [3,4]

Would x + y be executed only once at first so that the successive calls be replaced by the value 3 instead? Is GHC Haskell optimized up to this job for FP brings us the virtue of referential transparency?

How to trace to prove it?

Answer 1

I don't think the computed value will be reused.

The general problem with this kind of thing is, x + y is cheap, but you could instead have some operation there that produces an utterly vast result, which you probably don't want to keep in memory. Which is a wordy way of saying "this is a time/space tradeoff".

Because of this, it seems GHC tends to not reuse work, in case the lost space doesn't make up for the gained time.

The way to find out for sure is to ask GHC to dump Core when it compiles your code. You can then see precisely what's going to get executed. (Be prepared for it to be very verbose though!) Oh, and make sure you turn on optimisations! (I.e., the -O2 flag.)

If you rephrase your function as

f x y z = let s = x + y in [ n | n <- z, n > s ]

Now s will definitely be executed only once. (I.e., once per call to f. Each time you call f it'll still recompute s.)

Incidentally, if you're interested in saving already-computed results for the whole function, the search term you're looking for is "memoisation".

Answer 2

What will happen can depend on whether you are using ghci vs. ghc and then, if you are compiling the code, what optimization level is being used.

Here is one way to test the evaluations:

import Debug.Trace

f x y z = [n | n <- z, n > tx x + ty y]
  where tx = trace "x"
        ty = trace "y"

main = print $ f 1 2 [3,4]

With 7.8.3 I get the following results:

1. ghci: x y x y [4]
2. ghc (no optimization): x y x y [4]
3. ghc -O2: x y [4]

It is possible that the addition of the trace calls affects CSE optimization. But this does show that -O2 will hoist x+y out of the loop.