What happened to the thread that optionsScalper referred to? It doesn't seem to exist anymore.

By on 4/8/2008 4:12 PM ()

Hi mstump,

There are a few forums that were designated "contributor-only" (for organizational and admin work) when we first started the site. Andy (The Armed Geometer) had inadvertently posted this question to one of those forums.

Andy's original post and Dr. Syme's response are included in this thread in their entirety. I should have made that clear when I wrote this. My apologies for not calling that out appropriately.

---O

By on 4/15/2008 11:10 PM ()

I would use three constructors rather than carrying a red/black tag:

1
type 'a t = E | R of 'a t * 'a * 'a t | B of 'a t * 'a * 'a t

However, RB-trees are less prevelant in functional programming. In OCaml, they are not significantly faster than AVL trees for the operations they support (e.g. add, remove). Moreover, RB-trees cannot implement some important operations (e.g. union) as efficiently as AVL trees because the information required to balance pairs of trees is not present.

I'd like to see the F# standard library include fast set theoretic operations, generic AVL trees and a balanced-binary-tree-based functional array data structure.

Cheers,
Jon.

By on 11/22/2006 12:47 PM ()

@jdh30 F# does indeed use an AVL tree for its Set implementation.

1
2
3
4
5
6
// taken from FSharp-2.0.0.0\source\fsharp\FSharp.Core\set.fs

type SetTree<'T> when 'T : comparison = 
        | SetEmpty                                          // height = 0   
        | SetNode of 'T * SetTree<'T> *  SetTree<'T> * int    // height = int 
        | SetOne  of 'T
By on 1/6/2011 6:25 PM ()
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