OEISにぶち込んだところ、これは oeis.org/A051924 で、カタラン数C(n)を使って

F_{n+1} = (3*n - 2)*C(n-1)

だそうです。少なくともn=15ぐらいまでは合っています。

長さn+1の語はちょうどC(n)個あり、カタラン数はC(n)=2(2n-1)/(n+1)*C(n-1)という関係が成り立つので、（もし上記の式が正しければ）F_{n+1}/C(n) ~ (3/4)n + O(1/n) となり、ランダムな語に対する最小コストの期待値は語の長さの3/4に漸近することがわかります。

ここで、この括弧の記法が平均してどの程度役に立つのか、すなわち最短表記のコストは n-1 からどの程度小さくなるのか、という問題を考えました。

f(-)を、語Xに対してXの最短表記のコストf(X)を与える関数とします。長さがnの語 X の語すべてにわたるf(X)の合計をF_nと書くとき、数列 F_n がわかればf(X)の平均も得られます。プログラムで列挙して計算してみたところ次のようになりました。

n: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
F_n: 0, 1, 4, 14, 50, 182, 672, 2508, 9438, 35750

ある語Xに対して、最短の表記を与えることは難しくありません。語Xの長さが1なら、それは葉`x`だけです。これはそのままコスト0の表記です。語Xの長さが1より大きいなら、それは常にX = ((...(x,X₁),X₂), ... , X_n)のように左端が葉のn+1個の語の列です。ここでn=1つまりX=(x,X₁)ならX₁の最短表記xs₁に対して".x" ++ xsが最短で、n>1なら"{x" ++ xs₁ ++ ... ++ xs_n ++ "}"が最短です。

ここで更に、括弧"{}"でいくつかの語をくくった場合、それらを左結合で掛けた語を意味するという略記法を導入します。すなわち、"{xyzw}"は ((x,y), z), w) を意味し、"{x.yz.wz}" は ((x, (y,z)), (w,z)) を意味します。

長さnの語をドット"."や括弧"{}"を使って文字列表記したとき、その文字列の長さからnを引いた値(つまり、文字列に含まれる`.`,`{`,`}`の数)をその表記の_コスト_と呼ぶことにします。例えば、最初に例に挙げた"..x.yz.zx"は、長さ5の語に対するコスト4の表記です。

親は新PCについて「初めて体験するのSSDからの起動が滅茶苦茶速い！！！」とのこと

floor(r√2) == floor([r] * sqrt(2))
です

型クラスのインスタンスはその型のアイデンティティとも言うべき情報であり、異なるインスタンスをもつ同型な型は(同型であるが)異なる型だ。逆に言えば、型クラスは必ずそのようになっていて欲しいときに*だけ*有用である。

（時系列的にはAも引用できたはずだけど気付いてなかったんだろうなぁ）

あ、ちゃんと参考文献を見たら、Bが引用してるのは論文AじゃなくてAと共通の著者の学会発表資料だ！それでだ！