.net - 在纯函数设置中重用具有不同区分联合的逻辑

Question

我正在 F# 中实现几棵树:标准 BST、红黑树、AVL 树、Treaps 等。

除了 insert/remove 操作，它们似乎都共享同一组函数:size、height, get, contains, floor, ceil, toSeq, blablabla .我们称它们为“不变树函数”。

尽管这些函数的核心几乎相同，但它们在不同的可辨别联合上运行，即不同的树由不同的可辨别联合定义。有没有一种方法可以轻松地参数化我的不变树函数，这样每次我实现一种新的树时，我只需要将可区分的联合与那些不变的实现结合起来？

这是 BST 的可区分联合及其 get 函数的示例:

(* 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)

谢谢

Answer 1

您可以使用 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

您实现使用事件模式参数化的通用树函数。然后，对于每种树类型，您需要在共享实现的那些函数中实现通用解构的事件模式。