[Haskell-cafe] Shared thunk optimization. Looking to solidify my understanding

[Daniel Fischer]

On Wednesday 22 September 2010 17:10:06, David Sankel wrote:
> The following code (full code available here[1], example taken from
> comments here[2]),
>
> const' = \a _ -> a
>
> test1 c = let a = const' (nthPrime 100000)
>           in (a c, a c)
>
> test2 c = let a = \_ -> (nthPrime 100000)
>           in (a c, a c)
>
>
>  in a ghci session (with :set +s):
>
> *Primes> test1 1
> (9592,9592)
> (0.89 secs, 106657468 bytes)
> *Primes> test2 1
> (9592,9592)
> (1.80 secs, 213077068 bytes)
>
>
> test1, although denotationally equivalent to test2 runs about twice as
> fast.
>
> My questions are:
>
>    - What is the optimization that test1 is taking advantage of called?

Sharing. test1 computes nthPrime 100000 only once, test2 twice.
Note that when compiled with optimisations, test1 and test2 give exactly 
the same core.

>    - Is said optimization required to conform to the Haskell98 standard?
> If so, where is it stated?

No, it's not required. Unconditional sharing may be bad, so it would be 
unwise to demand sharing.

>    - Could someone explain or point to a precise explanation of this
>    optimization? If I'm doing an operational reduction by hand on paper,
> how would I take account for this optimization?

More or less

test1 c =
    let v = nthPrime 100000
        a = const' v
    in (a c, a c)

You (the compiler) give(s) a name to a value, when the value is referred to 
via that name, it's not recalculated (it's calculated on first demand).

>
> Thanks,
>
> David
>
> [1] http://hpaste.org/40033/operational_semantics
> [2] http://conal.net/blog/posts/lazier-functional-programming-part-2/