I've heard fixed-point view, open datatypes and some others, but I'm
curious where this pattern comes up in literature and what it is called there.
Tim Sheard and Emir Pasalic call this technique "two-level types" in their JFP'04 paper Two-Level Types and Parameterized Modules:
Apparently from reading Section 2 of that paper, they would call ExprF non-recursive type the structure operator. I think, by itself, the type ExprF doesn't mean much. It really matters how it's used to determine what you call it. Martijn already mentioned the fixed-point view, but that only makes since in the context of something like Fix:
data ExprF r = Add r r | Sub r r | Mul r r | Div r r | Num Int newtype Fix f = In (f (Fix f)) type Expr = Fix ExprF
I believe the F suffix that Martijn used typically means functor, and I sometimes call types like this functors (with an optional but obvious instance of Functor). Regards, Sean