Reusing logic with different discriminated unions in a purely functional setting

Question

I am implementing a couple of trees in F#: a standard BST, a Red Black Tree, AVL tree, Treaps, etc.

Other than the insert / remove operations, they all seem to share the same set of functions: size, height, get, contains, floor, ceil, toSeq, blablabla. Let's call them "invariant tree functions".

Although the core of those functions is pretty much the same, they operate over different discriminated unions, that is, different trees are defined by different discriminated unions. Is there a way to easily parameterize my invariant tree functions such that every time I implement a new kind of tree I only have to glue the discriminated union with those invariant implementations?

Here is an example of a BST's discriminated union and its get function:

(* Searches for a node with the given key in this BST and returns the 
   result in the form of an option. Executes in O(lg n) time. *)
type t<'K, 'V> =
    | Empty
    | Node of 'K * 'V * t<'K, 'V> * t<'K, 'V>

let rec get k = function
    | Empty -> None
    | Node(k', v, l, r) ->
        if k < k' then get k l
        elif k > k' then get k r
        else Some(v)

Thanks

if you can find a generic `fold` for all of your trees you can use this for the rest - but it depends a bit on if all your trees have the same generic parameters(count), etc. - sadly it's hard to abstract over this in F# and you usually have separate `map`, `filter`, ... operations in modules like `Seq`, `List`, ... although they too share their concepts (here is a related question to the `fold` I mentioned: https://stackoverflow.com/questions/196294/what-is-a-catamorphism-and-can-it-be-implemented-in-c-sharp-3-0/4413645#4413645) — Random Dev, Aug 20 '15 at 06:40
I think part of this problem would also happen in other OO languages (I'm thinking Java or C#, for instance). Of course that one could have a generic Node object and then inherit from it, but that would also bring some drawbacks. — devoured elysium, Aug 20 '15 at 06:45
if you find an OO solution you like/accept go on and use it - F# is an hybrid language - the thing is just that usually the abstractions are so messy in .net (there are a couple of projects on github where they try to implement typeclass-like things in F# and it works - but it's almost unusable from a practical perspective and to much to learn for your *normal programmer*) that it's just easier to reimplement the stuff in their modules - especially since it's usually only a couple of lines — Random Dev, Aug 20 '15 at 06:49
Were I implementing this in OCaml and would the situation be any better? — devoured elysium, Aug 20 '15 at 07:02
if you use OCamls modules/functors then probably yes (but I never used OCaml myself so I am by no means the right person to decide ;) ) — Random Dev, Aug 20 '15 at 07:09

score 3 · Answer 1 · answered Aug 20 '15 at 07:05

You can get some help by using active patterns:

let get (|Empty|Node|) k t =
    let rec get' k = function
    | Empty -> None
    | Node (k', v, l, r) ->
        if k < k' then get' k l
        elif k > k' then get' k r
        else Some v

    get' k t

type T1<'k, 'v> =
    | Empty
    | Node of 'k * 'v * T1<'k, 'v> * T1<'k, 'v>

let getT1 k t =
    let (|Empty|Node|) = function
    | Empty -> Empty
    | Node (k, v, l, r) -> Node (k, v, l, r)

    get (|Empty|Node|) k t

type T2<'k, 'v> =
    | Empty2
    | Node2 of 'k * 'v * T2<'k, 'v> * T2<'k, 'v>

let getT2 k t =
    let (|Empty|Node|) = function
    | Empty2 -> Empty
    | Node2 (k, v, l, r) -> Node (k, v, l, r)

    get (|Empty|Node|) k t

You implement your generic tree functions parametrized with an active pattern. Then, for each tree type, you need to implement an active pattern for generic destructuring in those functions that share implementation.

Basically, you wrap (and unwrap) in a separate generic type. A type like [`Choice<'T1,'T2>`](https://msdn.microsoft.com/library/Ee353439.aspx), the predefined discriminated union into which a two-case active pattern (and active recognizer) desugar. While it's nice to have the active pattern, there are enough examples out there of using these union cases directly to think of it as somewhat idiomatic. — kaefer, Aug 20 '15 at 19:41
Yes, the active pattern is just a nice touch to make the `get` implementation look pretty. You can do the same with just a function of `'a -> Choice`. — MisterMetaphor, Aug 20 '15 at 21:01

Reusing logic with different discriminated unions in a purely functional setting

1 Answers1