Search code examples
haskelllet

Haskell | Are let expressions recalculated?


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?


Solution

  • 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.