Proposal: map-of operator, grouping / joining construct

[yuhan0]

This was prompted by a question on the Slack channel on how to match and substitute maps which represent homogeneous, variable-length mappings instead of a heterogeneous collection of keys.

The example I had in mind was how to transform the nested data structure

(def data
  {1 {:en "one", :de "eins", :fr "un"}
   2 {:en "two", :de "zwei", :fr "deux" :es "dos"}
   3 {:en "three", :de "drei", :fr "trois"}
   5 {:fr "cinq"}})

into the following result

{:en {1 "one", 2 "two", 3 "three"}
 :de {1 "eins", 2 "zwei", 3 "drei"}
 :fr {1 "un", 2 "deux", 3 "trois", 5 "cinq"}
 :es {2 "dos"}}

It turns out this example conflates a "database join", or grouping operation which may be a separate and more challenging problem.

The map-of implementation @noprompt suggested:

(m/defsyntax map-of [k-pattern v-pattern]
  (if (m/match-syntax? &env)
    `(m/with [%map# {~k-pattern ~v-pattern & (m/or '{} %map#)}]
       %map#)
    &form))

The operator in use, and partial solution to the original problem:

(m/find data
  (map-of !keys !vals)
  [!keys !vals])
;; =>
[[3 1 2 5]
 [{:en "three", :de "drei", :fr "trois"}
  {:en "one", :de "eins", :fr "un"}
  {:en "two", :de "zwei", :fr "deux", :es "dos"}
  {:fr "cinq"}]]

(defn number-to-word-by-lang [lang]
  (m/rewrite {1 {:en "one", :de "eins", :fr "un"}
              2 {:en "two", :de "zwei", :fr "deux" :es "dos"}
              3 {:en "three", :de "drei", :fr "trois"}
              5 {:fr "cinq"}}
    (map-of !nums {~lang (m/or (m/some !words) _)})
    {~lang {& [[!nums !words] ...]}}))

(number-to-word-by-lang :en)
;; =>
{:en {3 "three", 1 "one", 2 "two"}}

[timothypratley]

I like the operator 👍

As to solving the original problem I suggest

(apply merge-with merge
       (m/search {1 {:en "one", :de "eins", :fr "un"}
                  2 {:en "two", :de "zwei", :fr "deux" :es "dos"}
                  3 {:en "three", :de "drei", :fr "trois"}
                  5 {:fr "cinq"}}
                 (m/scan [?num (m/scan [?lang ?word])])
                 {?lang {?num ?word}}))
=>
{:en {1 "one", 2 "two", 3 "three"},
 :de {1 "eins", 2 "zwei", 3 "drei"},
 :fr {1 "un", 2 "deux", 3 "trois", 5 "cinq"},
 :es {2 "dos"}}

[timothypratley]

I've changed my mind based on recent experiments; I think the current definition of map-of is too limiting to be useful. (See #97 (comment))

Specifically:

• map-of does not capture the associations, whereas matching key-value sequences does ([!k !v] ..!n) !n will contain the partitions which can be used to construct rows and solve the map reshaping problem. This can be solved by changing the signature of the syntax to key-value style.
• map-of is not symmetrical with substitution. This is solvable, we just need to provide a substitution behavior.
• {& ([!k !v] ...)} already exists on the substitution side, but just doesn't seem to work on the matching side; if that's addressable then the need for map-of goes away.

[timothypratley]

(m/match {}
          (map-of !x !y)
          [!x !y])

Is an error: When matching, map patterns may not contain variables in their keys that would make it so there is more than one match possible.

[noprompt]

@timothypratley Thats expected behavior.

[timothypratley]

Sure! Expected behavior given the definition, but don't you think it limits what it can be used for?

map-of seems to have a lot of drawbacks and I'm failing to see the upside... what does it do for me?

It looks like the intention is a convenience to gathering key-value pairs, but I claim that is better served by (m/and {} (m/seqable ,,,)) which can be used in match and can bind the size ..!n

Is there a property of map-of that makes it more desirable?

[timothypratley]

As a key-value collector/disperser this works great:

 (m/rewrite {:a :b :c :d :e :f}
            {& (m/seqable [!k !v] ..!n)}
            {& ([!k !v] ..!n)})

It is almost symetrical and almost as concise as map-of, but additionally it's got all of meanders features available and is nestable:

(m/match {1 {:en "one", :de "eins", :fr "un"}
           2 {:en "two", :de "zwei", :fr "deux" :es "dos"}
           3 {:en "three", :de "drei", :fr "trois"}
           5 {:fr "cinq"}}
          {& (m/seqable [!num {& (m/seqable [!lang !word] ..!partition)}] ...)}
          {:num !num
           :lang !lang
           :word !word
           :partitions !partition})
#_#_=>
{:num [1 2 3 5],
 :lang [:en :de :fr :en :de :fr :es :en :de :fr :fr],
 :word ["one" "eins" "un" "two" "zwei" "deux" "dos" "three" "drei" "trois" "cinq"],
 :partitions [3 4 3 1]}

I think map-of differentiates by being able to find sub-maps where as the above forms match the entire map... is that the killer feature?

[noprompt]

There's a pull request open for map-of and submap-of.

For grouping, we have a solution on zeta which is called fold which is an operator that takes a mutable variable, an initial value, and a reducing function:

;; Tally
(m/fold m* 0 +)
;; Max
(m/fold m* 0 clojure.core/max)

Here is an example of how it works:

(m/find [1 8 9 -1 10 30 3]
  (m/with [%min (m/fold *min 0 clojure.core/min)]
    [%min ...])
   *min)
;; => -1

Of course, this can be used to do grouping as well since grouping is a reduction.

It may be possible to bring fold to epsilon while zeta is in progress, however, my available time to investigate it is limited and I want to focus on zeta since it has a more reliable base than epsilon does.