generic rose tree とは

gistfile1.txt

Ruby の Array は関数型プログラミングの List とは違います。

が、Ruby 1.8.7 以上で Enumerable は大きく変わりました。
その結果、関数型プログラミングの文脈における List のかなりのことが、
短いプログラム断片で書けるようになったと理解しています。

関数型プログラミングでは、さらに List を抽象化できます。
その一つが Rose tree [Bird 1998] です。

Ruby でも、このような抽象化があれば役にたつと思います。
そのために、筆をとりました。

gistfile2.lhs

Haskell の例で恐縮ですが、関数型プログラミング全てで可能だと思います。
静的型つきのない言語でも、トリックを用いれば代数的データ型の実装が可能です。

> data List a = Nil | Cons a (List a)

Haskell のリストを、組込みのリストではなく、代数的データ型で書きます。

> -- []    === Nil
> -- [1]   === Cons 1 Nil
> -- [1,2] === Cons 1 (Cons 2 Nil)

となります。以下では Cons を連ねるのが辛いのでリスト表記を許してください。
[1, 2] は Array ではなく Cons 1 (Cons 2 Nil) です。

次に Rose tree の定義を書きます。

> data Rose a = Branch a (List (Rose a))

具体例を示します。

> Branch 5 [ Branch 3 [ Branch 1 [], Branch 4 [] ] ], Branch 7 [] ]

これは、二分木の枝をさらに増やすこともできる抽象化です。
書くのも読むのも面倒なので、二分木の例っぽいのを描きますが、
リストは伸ばすことができることを想像してください。

rose.png

読者の皆様へ、せっかく書いた gist ですが、推敲の時点で、僕の中で別の結論が出てしまいました。ので、これは書き途中でやめます。