@rae: What Haskell's deep subsumption is, why we killed it, and then why we resurrected it.

I review the recent saga about Haskell's deep subsumption feature, demonstrating what it is, what's wrong with it, and discussing why we dropped it and then brought it back.

[JamesSully]

Great explanation, thanks! I peripherally saw the controversy, but didn't understand what it was about

[SuperManitu]

Yes, I think the biggest point is the error message. I recently updated a codebase to GHC 9+ and some places where this popped up, but had to check the issue tracker of the library to find a ticket of someone with the same error that showed where to eta expand. This is the annoying part, because it wastes a lot of time during upgrade. If it would error out and show me where to expand then this would not have been noteworthy at all.

[qseep]

I'm not clear why we need to eta-expand in order to do deep subsumption. Why does the forall have to be on the outside? Even if it does, couldn't we normalize the type by floating the forall to the outside, since the function argument doesn't depend on it? That is, always rewrite (Int -> forall a. Int) to (forall a. Int -> Int).

[ncfavier]

Couldn't we simply "deeply instantiate" the Int → ∀a. Int function to Int → Int without actually modifying the program?

[kurisu-makise]

As always, love your clearly explained videos :D

[mck]

Thanks for the explanation. One question - in new haskell2021 is there a way to avoid eta-expansion by either:

a) changing type of f such that we still get forall a.
b) changing the type of map (pretend map is a function I wrote)

i.e. in Haskell2021 I want to share (fib 25), but with forall a in f's signature

[derelbenkoenig]

Very enlightening explanation. I recently read the proposal that removed deep subsumption, but didn't really fully expand why the eta expansion had to happen or what it meant. In particular, the proposal IIRC said that the eta expansion "changed the semantics" of the program. I was confused as how that was possible... would it be accurate to say that it changes the _operational_ semantics, but not the _denotational_ sematics? I mean, an eta-conversion is considered "equivalent" in lambda calculus if I understand correctly

[jonaskoelker]

Maybe this is a stupid question, but is (map (let x = (fib 25) in f x) [1..3]) distinguishable from (map (f (fib 25)) [1..3])? Won't thunkification or other laziness machinery make (fib 25) cacheable? Can the compiler do this rewrite without changing the meaning of the program? Does it do it?

More fundamentally: why does eta-expansion cause more memory allocation? I gather we're allocating more stack frames (or activation records in some other form) since that's the only apparent difference, but why?

[cblpsu]

why CSE doesn't take (fib 25) out?

[cdsmithus]

Maybe I'm just not understanding something, but don't you always lose memoization when you make types polymorphic?