可以从这个广义的集合定义中删除操作字典吗？

Question

我试图在 F# 中概括 Set 的概念。除其他事项外，我想使用不等式定义集合。这将帮助我简化代码的某些部分。所以我创建了一个类型 MySet 如下：

type Comparison = | GE
                  | GT
                  | LE
                  | LT
                  | EQ

type ComparisonOps<'t> = { gt: 't->'t->bool
                           ge: 't->'t->bool
                           eq: 't->'t->bool
                           le: 't->'t->bool
                           lt: 't->'t->bool }

type MySet<'t when 't : comparison> =
    | List of list<'t>
    | Sequence of seq<'t>
    | Array of 't []
    | String of string
    | Set of Set<'t>
    | Compare of (ComparisonOps<'t>*Comparison*'t)

注意：我打算稍后使 MySet 递归，允许并集和交集，但对于这个问题的目的，这不是必需的。

新 MySet 类型的重点是允许检查不同类型的元素是否属于不同情况的集合。这是通过这个函数实现的：

let elementOf<'t when 't : comparison> (st: MySet<'t>) (x: 't) : bool =
    match st with
    | List xs    -> List.contains x xs   
    | Sequence s -> Seq.contains x s
    | Array a    -> Array.contains x a
    | Set st     -> Set.contains x st
    | String str -> match box str with
                    | :? string as s -> match box x with
                                        | :? string as z -> s.Contains z
                                        | _ -> false
                    | _ -> false
    | Compare (comp: ComparisonOps<'t>*Comparison*'t) ->
        let compOps, cmp, y = comp
        match cmp with
        | GT -> compOps.gt x y
        | GE -> compOps.ge x y
        | EQ -> compOps.eq x y
        | LE -> compOps.le x y
        | LT -> compOps.lt x y

注意：我还计划泛化 elementOf 以允许函数应用，但这里也不需要。

函数有效：

let myStringSet = MySet.String("XYZ")
let strb = "X" |> elementOf<string> myStringSet
printfn "strb = %b" strb // strb = true

let myListSet = MySet.List([0..10])
let listb = 5 |> elementOf<int> myListSet
printfn "listb = %b" listb // listb = true

let myCompSet = MySet.Compare((ComparisonFloat, GT, 0.0))
let compb = -1.0 |> elementOf<float> myCompSet
printfn "compb = %b" compb // compb = false

let myCompSet2 = MySet.Compare((ComparisonString, LT, "XYZ"))
let compb2 = "XA" |> elementOf<string> myCompSet2
printfn "compb2 = %b" compb2 // compb2 = true

太好了，但我想知道我是否真的需要创建操作字典 ComparisonOps，因为像 < 这样的操作在 int、float 和 string 类型上都是多态的。

消除 ComparisonOps 可以大大简化代码。这可能吗？

Answer 1

如 Fyodor Soikin 所述，听起来您可能想要将一个集合定义为满足谓词的所有元素：

type MySet<'t> = | MySet of ('t -> bool)

那么集合操作就很容易定义了：

let intersect (MySet p1) (MySet p2) = MySet(fun t -> p1 t && p2 t)

并且您所有的特定构造函数都可以变成简单的函数：

let ofList l = MySet(fun t -> List.contains t l)
let lt x = MySet(fun t -> t < x)

可以从这个广义的集合定义中删除操作字典吗？

Could the dictionary of operations be eliminated from this generalized Set definition?

polymorphism

comparison

f#

set

discriminated-union