Haskell + ObjectiveでC++のtemplate classに相応する事がしたい

Question

###質問したいこと
Haskell + Objective (GADTs)でC++のSTL Containerの赤黒木みたいなものを作っています。
その際に

data NodeColor = Red | Black
data NodeObject key value color left right where
  ...(メソッドなどの記述)...

といったコードを書くのですが、以下の問題があります。

• Nilをどうするか？ただのOOPLを行わない二分木ならば、data Tree x = Nil | Node x (Tree x) (Tree x)と表現できますが、今回ではどこにNilを記述すればいいか分かりません。
• keyとvalueを任意の型に対して対応させたいのですが、記述方法が分かりません。

###補足情報
処理系はGHCです。

Answer 1

GADTs拡張も、Objectiveも、質問を読んで初めて知ったので外してるかもしれませんが、恐らく、赤黒木を表す代数データ型そのものと、その代数データ型に対するメソッドを定義するオブジェクトデータ型の２つが必要なのだと思います。

仮に前者を Tree 、後者を TreeObject とすると、以下のような定義になるでしょうか？

data NodeColor = Red | Black

data Tree k v = Nil | Node NodeColor (Tree k v) (k,v) (Tree k v)

data TreeObject k v where
  Insert :: Ord k => (k, v) -> TreeObject ()
  Search :: Ord k => k -> Maybe TreeObject v

（TreeObject の Insert と Search の型はかなり適当なので、きっと間違っていると思います...）

TreeObject の実装の内側では Tree データーを状態として持っていて、メソッドが呼ばれたら、それを更新するというイメージです。Tree データーは、TreeObject の中にカプセル化されるので、TreeObject を使う側からは見えません。

こちらの記事の「人間オブジェクトとカプセル化」を参考にしました。
http://tune.hateblo.jp/entry/2015/03/27/035648

Comments

[wqwqw]

メソッドと赤黒木がもつデータそのものを同一の代数データ型に混在できると勘違いしていましたが、この回答により記述方法の理解ができました。ありがとうございます。
key valueについてはそれが未確定の型であるという特別な記述はしなくてもいいみたいですね。