data types a la carteもcofree annotationもデータ型をopenにするという方向では一緒なのですが,それぞれ方向性はdata types a la carteはsumに対してのopen性,cofree annotationはrecursion schemeに関してのopen性みたいな感じで異なるのでそこらへんは注意です(まあ結果的に,これらを併用することが可能なのですが)
で,実際にどのようにcofree annotationが解決するかなのですが,ASTを以下のようにrecursion schemeのBaseで定義しておきます. data ExprF e = ValF Int | AddF e e (ここでeは元のaと関係なく,再帰する箇所を表します.まあこの辺はdata types a la carteと一緒で,それが併用できる所以なんですが)
で,通常はこれをFix f = f (Fix f)という原始的なオペレータでfixするんですが,Cofree f a = (a, f (Cofree f a))というオペレータでfixすることで,再帰する箇所全てに後から任意の注釈を埋め込めるようにできるというのがcofree annotatingと言われる手法ですね