Set data type

[toastal]

Is your feature request related to a problem? Please describe. For collection types, Nickel supports: records, dictionary, arrays, but one common structure missing is Set, an unordered collection like an array where all values must be unique. Uniqueness can prevent certain kinds of errors where the consumer should need to consider duplicate values, but also comes with a grab bag of handy combinators like union, intersect, difference, merge, etc.

Describe the solution you'd like Add a new data type: Set T + stdlib module std-set

Describe alternatives you've considered Making a bunch of contracts around Array T.

Additional context This is a common data structure in most languages. It’s been a long personal pain point with its absence in JSON, however alternatives like EDN do support it. Being able to assert a JSON Array as a Set would be very useful.

[yannham]

I wonder, do you want a builtin type Set that would be natively handled by Nickel, or some kind of standard library module that implements Set using more basic constructions? Or, maybe, you don't care and just want Set :slightly_smiling_face:

[toastal]

Sets are also basic blocks for building more advanced compound types too

[suimong]

Weighing in here as someone who also encountered use cases for Set, I believe a native implementation would be nicer, though the only reason I could think of is performance.😂

[thufschmitt]

Agreed that a Set could be useful.

I had fun with the encoding below, which has the advantage of playing nicely with the merge system (because a & b is the set-theoretic merge), but doesn't translate nicely to JSON at all:

let Set = {
  Set | doc "Contract for a set" = fun a => { _ : a },
  hashFun : Dyn -> String = fun x => x |> std.serialize 'Json |> std.hash 'Sha256,
  add
    | doc "Add an element to a set"
    : forall a. a -> { _ : a } -> { _ : a }
    = fun elt set =>
      let key : String = hashFun (elt | Dyn) in
      std.record.update key elt set,

  add_all
    : forall a. Array a -> { _ : a } -> { _ : a }
    = fun elts set =>
      std.array.fold_left
        (fun x y => add y x)
        set
        elts,

  from_array
    | doc m%"
      Create a set from all the elements in the given array.
    "%
    : forall a. Array a -> { _ : a }
    = fun elts => add_all elts {},
}
in
# Just for the example
(
  Set.from_array [1, 3, 5, 8, 9, 143]
  & (Set.add_all [1, 2, 3] {})
  & (Set.add_all [2, 2, 3] {})
) | Set.Set Number