2

Lets say we have this function:

foo n = let comp      n = n * n * n + 10
            otherComp n = (comp n) + (comp n)
        in  (otherComp n) + (otherComp n)

How many times will comp n get actually executed? 1 or 4? Does Haskell "store" function results in the scope of let?

Petras Purlys
  • 1,093
  • 6
  • 18
  • 2
    https://stackoverflow.com/questions/40694437/under-what-circumstances-could-common-subexpression-elimination-affect-the-lazin – hegel5000 Jan 25 '18 at 19:36
  • This is implementation dependant. Any reasonable compiler is likely to call `comp` and `otherComp` only once, unless it inlines the whole thing to `4 * (n*n*n+10)` to take advantage of unboxing and remove the calls. Implementations are not required to do common subexpression elimination – Dan Robertson Jan 25 '18 at 19:37

1 Answers1

10

In GHCi, without optimization, four times.

> import Debug.Trace
> :{
| f x = let comp n      = trace "A" n
|           otherComp n = comp n + comp n
|       in  otherComp x + otherComp x
| :}
> f 10
A
A
A
A
40

With optimization, GHC might be able to inline the functions and optimize everything. However, in the general case, I would not count on GHC to optimize multiple calls into one. That would require memoizing and/or CSE (common subexpression elimination), which is not always an optimization, hence GHC is quite conservative about it.

As a thumb rule, when evaluating performance, expect that each (evaluated) call in the code corresponds to an actual call at runtime.

The above discussion applies to function bindings, only. For simple pattern bindings made of just a variable like

let x = g 20
in x + x

then g 20 will be computed once, bound to x, and then x + x will reuse the same value twice. With one proviso: that x gets assigned a monomorphic type.

If x gets assigned a polymorphic type with a typeclass constraint, then it acts as a function in disguise.

> let x = trace "A" (200 * 350)
> :t x
x :: Num a => a
> x + x
A
A
140000

Above, 200 * 350 has been recomputed twice, since it got a polymorphic type.

This mostly only happens in GHCi. In regular Haskell source files, GHC uses the Dreaded Monomorphism Restriction to provide x a monomorphic type, precisely to avoid recomputation of variables. If that can not be done, and duplicate computation is needed, GHC prefers to raise an error than silently cause recomputation. (In GHCi, the DMR is disabled to make more code work as it is, and recomputation happens, as seen above.)

Summing up: variable bindings let x = ... should be fine in source code, and work as expected without duplicating computation. If you want to be completely sure, annotate x with an explicit monomorphic type annotation.

chi
  • 111,837
  • 3
  • 133
  • 218
  • I honestly had no idea about this. Does this mean that if I put something marginally expensive (like `length` on a list I know might be quite long) in a `let`, that Haskell may end up calling `length` a whole bunch of times? Argh! – Adam Smith Jan 25 '18 at 20:16
  • Yeah, that's what this question is also about. So what can one do to avoid multiple expensive reevaluations? – Petras Purlys Jan 25 '18 at 20:38
  • 4
    But `let x = in x + x` will only evaluate `x` once, it just doesn't share function calls. If you need more than local sharing of single calls like this, you can [memoize](https://wiki.haskell.org/Memoization). – luqui Jan 25 '18 at 21:10
  • 1
    @luqui I added some comment about that. Note that even that `x` might be computed twice, if it gets a polymorphic type with constraints (with the DMR off). Actually, when polymorphic values are around, it is a bit tricky to guess what is recomputed and what is not. Experimenting with GHCi, I found my guesses on a few corner cases to be pretty wrong... ;-) – chi Jan 25 '18 at 21:50
  • @chi, care to share some of your wrong guesses? I'm curious. – luqui Jan 25 '18 at 22:36
  • 1
    @luqui GHCi, DMR on: `let x = let y = trace "y" [] in (trace "a" (show y), trace "b" y)`, evaluating `x :: (String, [Int])` and `x :: (String, [Char])`. I got the latter wrong, both in the recomputation, and even in the value (!). Here, I think the extended default rules of GHCi got me. – chi Jan 25 '18 at 23:06
  • @luqui With scoped variables, no ext-defaulting rules, ambiguous types: `let z :: forall a. Show a => (String, [a]) ; z = trace "z" (show ([] :: [a]), [])` does more or less what I expected in the first place. – chi Jan 25 '18 at 23:12