Back to Questions
3.1k
views2
comments
How do I?
f#

How do I create the equivalent of a red-black tree in F# where each node has a key that is two floats: x,y and has a value that is four floats x1,y1,x2,y2 ? I would also like to be able to specify how the keys get compared so I can decide what is less than based on comparing y then x. Any ideas or examples you could point me to?

Basically I would like to see how you would re-create the functionality of C++'s std::map with an overloaded operator< for the class point.

.

First take a look at the 'set.fs' implementation of binary trees in the distribution. For example, binary trees for implementing sets are defined as follows:

1

type 'a tree = SetEmpty | SetNode of 'a * 'a tree * 'a tree * int

A red-black tree will usually carry a reb/black flag, e.g. 

1
2
3

type color = R | B

type 'a tree = E | T of color * 'a tree * 'a * 'a tree

or use a boolean. Samples on the web show examples of rebalancing such a tree using pattern matching, e.g. [link:www.msu.edu], about half way down.

In F#, you have a number of choices as to how the comparer function is handled. The design I like best (but which is not yet used in the Set and Map implementations, though we may move to it) is to store the comparison function as a value in the root node of the tree, and pass it down explicitly through the functions that implement the operations on the trees (e.g. 'add', which I'm not showing here as I'll get it wildly wrong :-) ). You can then pass in the comparer as a function value when an tree is constructed. You can also provided a constructor function that fills in this with the default value of Pervasives.compare, which is F#'s default structural comparison operator and works over the 'default' comparison semantics associated with types via the IComparable interface. For example.

1
2
3
4
5
6
7
8
9
10

type 'a comparer = 'a -> 'a -> int
type color = R | B
type ('a,'b) tree = 
{ cf: 'a comparer;
  top: ('a,'b) node }

and ('a,'b) node = E | T of color * ('a,'b) node * 'a * 'b * ('a,'b) node

let empty_explicit cf = { cf=cf; top=E }
let empty = { cf=Pervasives.compare; top=E }

You would use this as follows:

1
2
3
4
5
6
7
8
9

/// This gets the string comparison implemented by
/// Pervasives.compare, which is case insensitive, culture neutral
let myTree1 : (string,int) tree = RBTree.empty

let case_sensitive s1 s2 = System.String.Compare(s1,s2,false)
let myTree2 : (string,int) tree = RBTree.empty_explicit case_sensitive

let case_insensitive s1 s2 = System.String.Compare(s1,s2,true)
let myTree3 : (string,int) tree = RBTree.empty_explicit case_insensitive

Finally, some people like using the 'functor' style, where you give the comparison operator once and for all and return a whole record of functions for use with trees specialized for that particular comparison operator. See, for example, Set.Make in the distribution. I personally don't think this buys too much in practice.

Next, to get your floats, use something like

1
2
3
4
5
6
7
8
9

type fpair = float * float
type fquad = float * float * float * float

let cf (x1,y1) (x2,y2) = 
  let c = compare y1 y2 in 
  if c <> 0 then c 
  else compare x1 x2

let myTree4 : (fpair,fquad) tree = empty_explicit cf

Finally, I think you were hinting at the case where the keys are just a logical projection from the data carried at each node of the tree (indeed sometimes both the key and value are just such a projection). In this case you can change your tree structure to reflect this, parameterizing it by both key extraction and value extraction functions:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

type 'a comparer = 'a -> 'a -> int
type('k,'v,'data) tree = 
{ cf: 'k comparer;
  kf: ('data -> 'k);
  vf: ('data -> 'v);
  top: 'data node }

and 'data node = E | T of color * 'data node * 'data * 'data node

/// Simple trees just have data that is a key, value pair. 
type ('k,'v) simpleTree = ('k,'v, ('k*'v)) tree

/// This one creates a simple tree where the data is just a 
/// key, value pair and the keys are compared using structural
/// comparison.
// val empty : ('k,'v) simpleTree

let empty = 
{ cf = (fun (k1,_) (k2,_) -> Pervasives.compare k1 k2);
  kf = (fun (k,v) -> k);
  vf = (fun (k,v) -> v);
  top=E }

/// This one creates a simple tree where the data is just a 
/// key, value pair and the keys are compared using the explicit
/// comparison function.

// val empty_cf : ('k,'v) simpleTree

let empty_cf cf =
{ cf = (fun (k1,_) (k2,_) -> cf k1 k2);
  kf = (fun (k,v) -> k);
  vf = (fun (k,v) -> v);
  top=E }

/// This one is the most general: all three functions are given
/// explicitly. If you like you can accept an obejct model
/// interface as the input: this is normal practice once
/// multiple related function arguments are used to parameterize
/// a function. 

let empty_kf_vf_cf (kf,vf,cf) =
{ cf = cf;
  kf = kf;
  vf = vf;
  top=E }
By on 2/24/2006 5:50 PM ()

Thank you. That is exactly what I was looking for.

By on 2/24/2006 6:18 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper