Add support for sorted collections

[helins]

Currently, it seems there is no support for sorted collections. Understandably, it was not a top priority since there are not that common.

They are not common but when needed, they become invaluable. Furthermore, since they are part of Clojure/script, it makes sense opening a discussion. I did not find anything, any issue on the matter. If you did consider supporting them and retracted for some reason, it would be useful providing a very brief summary here to at least have one issue documenting the process.

A few points:

0. It is usually disastrous when algorithms meant to operate on sorted collections blindly operate on unsorted ones (eg. a mistake, a bug, something escaped validation...)

1. Malli strives to be as serializable as possible. This can be problematic when using sorted-map-by and sorted-set-by which accept a custom sorting function. Using SCI in any way is not an option for performance reasons. However being serializable is not mandatory hence this is a minor problem. Furthermore, from experience, default sorted-map and sorted-set are often sufficient in most cases and those sorted default collections can be readily serializable.

2. Using custom sorted collections (eg. sorted-map-by) is akin to opening Malli to supporting any custom collection. A gateway to chaos?

3. Spec kind of eschews serialization but it almost solves this very simply by having an :into option in s/every and friends. Something like:

[:map-of
 {:into (sorted-map)}
 :int
 :string]

4. Example in Point 3 works for generation but not validation. Surprisingly, validation is tricky. You can check if a collection is sorted using sorted? but you never now if it is sorted as intended, returning back to Point 1. I don't think the sorting function can be reliably retrieved in both Clojure and CLJS. Users will have to resort to an alternative scheme such as adding a type in metadata if validation of custom sorted collections is needed.

[ikitommi]

How about creating custom sorted collection IntoSchemas in user space?

an incomplete example of :sorted-set:

(require '[malli.core :as m])
(require '[malli.transform :as mt])

(defn -sorted-set []
  (m/-collection-schema 
    {:type :sorted-set
     :pred #(and (set? %) (sorted? %))
     :empty (sorted-set)
     :in (fn [_ x] (sorted-set x))}))

(def registry
  (merge (m/default-schemas) {:sorted-set (-sorted-set)}))

(defn sorting-transformer []
  (mt/transformer {:decoders {:sorted-set (fn [x] (apply sorted-set x))}}))

(def SortedIntSet
  (m/schema [:sorted-set :int] {:registry registry}))

(m/validate SortedIntSet #{1 3 2 4})
; => false

(m/validate SortedIntSet (sorted-set 1 3 2 4))
; => true

(as-> #{1 3 2 4} $
      (m/decode SortedIntSet $ (sorting-transformer))
      (m/validate SortedIntSet $))
; => true

we could add more options into the functions creating the relevant IntoSchemas. e.g. one could set all generation, human errors, json-schema etc. as type-properties.

what do you think?

[ikitommi]

could also be a separate namespace malli.sorted, but we could start by doing the things as a good example/doc how to create custom IntoSchemas, under /docs.

[nilern]

I don't think the sorting function can be reliably retrieved in both Clojure and CLJS.

Clojure: (.comparator ^clojure.lang.Sorted m), CLJS: (-comparator m)

[helins]

If -collection-schema was checking for fn? akin to -simple-schema, it would also allow for defining something like:

[:sorted-set
 {:by sorting-fn}
 :int]

(I might misunderstand the internals, I didn't take much time really diving in greater details)

I am still unsure about how a complete solution would look like, taking into account that sorted? is an insufficient predicate. On the other hand, using the sorting function as a reference is misleading as well since 2 different sorting functions might behave the same. Might need to use homotopo type theory... Nah, we'll find out something else :p

For the time being it is a good idea to write it as documentation. It won't hurt, it is about a "real world example", and it might lead to some brainstorming later.