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

Question

I am trying to generalize the concept of a Set in F#. Among other things I want to define sets using inequalities. This would help me simplifying some sections of my code. So I created a type MySet as follows:

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)

Note: I intend to make MySet recursive later, allowing for unions and intersections, but for the purposes of this question this is not necessary.

The whole point of the new MySet type is to allow checking if elements of different types belong to sets of different cases. This is implemented by this function:

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

Note: I also plan to generalize elementOf allowing for function application, but again this is not needed here.

The function works:

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

That is great, but I wonder if I really need to create the dictionary of operations ComparisonOps, since operations like < are polymorphic on the types int, float and string anyway.

Eliminating ComparisonOps could considerably simplify the code. Is that possible?

Answer 1

As Fyodor Soikin notes, it sounds like maybe what you want is to define a set as all elements satisfying a predicate:

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

Then set operations are easy to define:

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

And all of your specific constructors can just be turned into simple functions:

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