functional-programming - OCaml で 'a 型のキーと 'b 型の値を取るツリーのユニオン型を作成するにはどうすればよいですか?

Question

bst(二分探索木) ユニオン型を作りたいです。

またはのいずれleafかnodeです。ノードの場合、'aキーと'b値を取ります。

これは私がしました：

type 'a*'b bst = 
  | Node of 'a * 'b * ('a*'b) bst * ('a*'b) bst
  | Leaf;;

しかし、それは機能しません

どうすればいいですか？

Answer 1

探している構文は次のとおりです。

# type ('a, 'b) bst =                              
      | Node of 'a * 'b * ('a,'b) bst * ('a,'b) bst
      | Leaf;;                                     
type ('a, 'b) bst = Node of 'a * 'b * ('a, 'b) bst * ('a, 'b) bst | Leaf

Answer 2

マルチパラメータ多相型の構文は次のとおりです。

type ('a, 'b) bst = 
  | Node of 'a * 'b * ('a, 'b) bst * ('a, 'b) bst
  | Leaf;;

Answer 3

'aまた、比較演算子が必要なため、トラブルが発生する可能性があります。これが、標準ライブラリでMapおよびSetモジュールがファンクタとして実装されている理由であり、比較順序を指定できるようになっています。

ポリモーフィズムの方法に従うこと'aにした場合は、「魔法の」デフォルトの比較演算子を使用する必要がありますcompare。

比較演算子を型にアタッチする方法があるため、F# では問題が異なります。