CODEWITHSUNDEEP
haskelloptimizationfunctional-programming
Siva
Siva

Reputation: 123

Optimal use of intermediate results in a functional program

Suppose I have two computations which could use the same intermediate result. If I wrote an imperative program, I would pass the same (relatively) "global" state to both functions, to be more efficient.

When writing functional code, I would use a function that computes the intermediate value as part of both functions which need that value. Should I be expecting my compiler to optimize that function call, or is there a more intelligent way for me to design the program?

To clarify, here's an example.

Let's say I have a function to compute some property a after a long and tedious computation. From a, I need to calculate two other properties b and c. For eg: b = a^2 and c = a^7 + a^(1/7). Now, as part of my main program, I invoke the functions to compute b and c. Will the computation to find a be done exactly once and the result reused, or will a be computed multiple times?

Ps: In case it's relevant, I'm learning Haskell.

Upvotes: 2

Views: 510

Answers (1)

Don Stewart
Don Stewart

Reputation: 137947

Suppose I have two computations which could use the same intermediate result. If I wrote an imperative program, I would pass the same (relatively) "global" state to both functions, to be more efficient.

When writing functional code, I would use a function that computes the intermediate value as part of both functions which need that value. Should I be expecting my compiler to optimize that function call, or is there a more intelligent way for me to design the program?

So to be concrete, you have two functions which both compute the same thing as part of a sub-computation. E.g.

f x = y + 3
   where
      y = x ^ 2

g x = y * 7
   where
      y = x ^ 2

z = f 2 + g 2

So you want to "float out" the common subexpression, x ^ 2, and share it.

This is "common subexpression elimination". It is an optimization a compiler can performn, or something you can do by hand. GHC, a Haskell compiler, will do CSE in some cases. In other cases, you can do it by hand by naming the intermediate computation explicitly.

It's better when the compiler does it.

Upvotes: 3

Related Questions