CODEWITHSUNDEEP
functional-programmingocaml
Jackson Tale
Jackson Tale

Reputation: 25812

How can I create a union type for a tree, where it takes 'a type of key and 'b type of value in OCaml?

I wish to create a bst (binary search tree) union type.

It is either leaf or node. For node, it takes 'a key and 'b value.

I did this:

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

but it doesn't work

How should I do it?

Upvotes: 1

Views: 264

Answers (3)

David Monniaux
David Monniaux

Reputation: 2004

In addition, you may get into trouble because 'a needs a comparison operator. This is why in the standard library, the Map and Set modules are implemented as functors, so that it is possible to specify the comparison ordering.

If you decide to go along the 'a polymorphism way, you'll have to use the "magical" default comparison operator compare.

The problem is different in F#, because there are ways to attach a comparison operator to a type.

Upvotes: 0

Thomas
Thomas

Reputation: 5048

The syntax for multi-parameter polymorphic types is the following:

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

Upvotes: 4

Pascal Cuoq
Pascal Cuoq

Reputation: 80276

The syntax you are looking for is:

# 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

Upvotes: 4

Related Questions