A point-free function is shared, yet evaluated twice

Question

I've been trying to understand how shared computation works in Haskell. According to my understanding, point-free shared computation should be evaluated only once (courtesy to CSE).

(A) For example, consider the following code and its output:

*Main> let foo = trace "eval foo" 5 in foo + foo
eval foo
10

*Main> let foo' = \x -> trace "eval foo'" x in (foo' 5) + (foo' 5)
eval foo'
eval foo'
10

As expected, foo is evaluated only once (CSE probably kicks in), while foo' is evaluated lazily twice. That is fine. I tried the above using GHCi, version 7.6.3. Next, I tried the same code in GHCi, version 8.6.5, yielding this result instead:

*Main> let foo = trace "eval foo" 5 in foo + foo
eval foo
eval foo
10

Notice that foo is evaluated twice now.

(B) Similarly, with GHCi, version 7.6.3:

*Main> let goo = const (trace "eval goo" 5) in goo () + goo ()
eval goo
10

but, GHCi, version 8.6.5 evaluates goo twice:

*Main> let goo = const (trace "eval goo" 5) in goo () + goo ()
eval goo
eval goo
10

(C) Finally, both versions yield the same result for the below:

*Main> let foo_wrapper x = let foo = trace "eval foo" x in foo + foo
*Main> foo_wrapper 5
eval foo
10

I wonder if some optimizations have been turned off by default in GHCi-8 or if the side effects of trace force foo to be evaluated somehow twice? Or was there an issue in GHCi-7? How is GHCi supposed to behave with expressions like (A) and (B)?

(Update 1)

For scenario (C) consider the following runs in GHCi-8 (with the main difference in the second argument of trace):

*Main> let foo_wrapper x = let foo = trace "eval foo" x in foo + foo 
*Main> foo_wrapper 5
eval foo
10
*Main> :t (foo_wrapper 5)
(foo_wrapper 5) :: Num a => a

*Main> let foo_wrapper' x = let foo = trace "eval foo" 5 in foo + foo 
*Main> foo_wrapper' ()
eval foo
eval foo
10
*Main> :t (foo_wrapper' ())
(foo_wrapper' ()) :: Num a => a

leftaroundabout leftaroundabout · Accepted Answer · 2019-09-04T14:43:51

As expected, foo is evaluated only once (CSE probably kicks in)

No, this has nothing to do with CSE, it's just how lazy evaluation (aka call by need) works: foo is a constant applicative form, as such it just needs to be computed (forced from a thunk to WHNF) once and can then simply be reused without any further computation. The reason that this doesn't work in GHCi-8 anymore is that 7.8 has removed the monomorphism restriction in GHCi. Why is this relevant? Well, trace "eval foo" 5 is a polymorphic expression of type Num a -> a. And polymorphic expressions can not be CAFs. Thus instead of call-by-need, you get call-by-name–semantics.

The simplest way to get sharing again is to enforce CAF by making the type monomorphic, by adding an explicit signature:

Prelude Debug.Trace> let foo = trace "eval foo" 5 :: Int in foo + foo
eval foo
10

A point-free function is shared, yet evaluated twice

(Update 1)

1 Answers