Fork me on GitHub
#meander
<
2021-08-25
>
noprompt16:08:10

Yes they should. I’m guessing they don’t?

noprompt16:08:00

Investigating.

noprompt16:08:18

OK. So those are working properly.

noprompt16:08:40

(m/rewrite '[:a b c 1 2]
  [:a . (m/pred symbol? !xs) ... !rest ...]
  [!xs ... !rest ...])
;; => [b c 1 2]


(m/rewrite '[:a b c 1 2]
  [:a . (m/pred symbol? !xs) ... & ?rest]
  [!xs ... & ?rest])
;; => [b c 1 2]
rewrite is based on find. The search space for the partitions of the list after :a is.
[:a . (m/pred symbol? !xs) ... !rest ...]
;;    ^^^^^^^^ XS ^^^^^^^^    ^  YS ^
;;                             
;; XS => [],        YS => [b c 1 2]
;; XS => [b],       YS => [c 1 2]
;; XS => [b c],     YS => [1 2]
;; XS => [b c 1],   YS => [2]
;; XS => [b c 1 2], YS => []

noprompt16:08:16

What Meander lacks is a greedy star for matching.

noprompt16:08:23

I know how to implement it as I have done this for zeta. For epsilon I just need a notation.

noprompt16:08:22

IOW Does anyone have an idea for what sort of notation we could use for a greedy version of ?

noprompt16:08:41

epsilon also makes the mistake of being greedy on the RHS, something we can’t fix without, well, making a new version.

ribelo18:08:03

¯\_(ツ)_/¯

ribelo19:08:16

I'm trying to rewrite the doxa datalog parsing functions using meander, and I've pretty much stuck out on a simple thing

ribelo19:08:05

I would like to transform [:find ?e ?age :in ?name :where [?e :name ?name] [?e :age ?age]] to {:find [?e ?age] :in [?name] :where [[?e :name ?name] ...]} seems simple, but the order is not fixed, all keys are optional and all vals can be anything but a keyword

ribelo19:08:18

In theory, such a thing should work, but because & ?more is greedy, it doesn't.

(defn parse-query2 [q & args]
  (m/rewrite q
    [:find . (m/pred (complement keyword?) !find) ... & (m/cata ?more)]
    {:find [!find ...] & ?more}
    [:in . (m/pred (complement keyword?) !in) ... & (m/cata ?more)]
    {:in [!in ...] & ?more}
    [:where . (m/pred vector? !xs) ...]
    {:where [!xs ...]}

    ?x nil
    nil {:args ~args}))

noprompt22:08:30

Here’s what I came up with:

(let [q '[:find ?e ?age :in ?name :where [?e :name ?name] [?e :age ?age]]]
  (m/rewrite [q {}]
    [[(m/keyword _ _ :as ?keyword) & ?args & [(m/keyword _) & _ :as ?rest-q]] ?out]
    (m/cata [?rest-q {?keyword ?args & ?out}])

    [[(m/keyword _ _ :as ?keyword) & ?args] ?out]
    {?keyword ?args & ?out}

    [_ ?out]
    ?out))
;; =>
{:find [?e ?age],
 :in [?name],
 :where [[?e :name ?name] [?e :age ?age]]}

noprompt22:08:13

I’m definitely not proud of the hackery here. The first rule is annoying because don’t have a greedy operator can’t

(m/and (m/not (m/keyword _)) !args)

noprompt22:08:28

So I want to correct that.

noprompt22:08:41

Also, ideally, something like this should work.

(let [q '[:find ?e ?age :in ?name :where [?e :name ?name] [?e :age ?age]]]
  (m/rewrite q
    [(m/keyword _ _ :as ?keyword) & ?args & (m/cata ?out)]
    {?keyword ?args & ?out}))

noprompt22:08:28

Oh. It does. I just forgot the empty case.

noprompt22:08:30

(let [q '[:find ?e ?age :in ?name :where [?e :name ?name] [?e :age ?age]]]
  (m/rewrite q
    [(m/keyword _ _ :as ?keyword) & ?args & (m/cata ?out)]
    {?keyword ?args & ?out}

    [] {}))
;;=>
{:where [[?e :name ?name] [?e :age ?age]],
 :in [?name],
 :find [?e ?age]}

noprompt22:08:05

I might also consider returning a sequence of pairs.

(let [q '[:find :find ?e ?age :in ?name :where [?e :name ?name] [?e :age ?age]]]
  (m/rewrite q
    [(m/keyword _ _ :as ?keyword) & ?args & (m/cata ?out)]
    [[?keyword ?args] & ?out]

    [] []))
;;=>
[[:find []]
 [:find [?e ?age]]
 [:in [?name]]
 [:where [[?e :name ?name] [?e :age ?age]]]]

noprompt22:08:33

But growing the cata could also accommodate this.

(let [q '[:find :find ?e ?age :in ?name :where [?e :name ?name] [?e :age ?age]]]
  (m/rewrite q
    [(m/keyword _ _ :as ?keyword) . !args ...
     & (m/cata (m/or {?keyword [!args ...] & ?out} ?out))]
    {?keyword [!args ...] & ?out}

    [] {}))
;; =>
{:where [[?e :name ?name] [?e :age ?age]],
 :in [?name],
 :find [?e ?age]}

noprompt22:08:49

Vector queries are kind of a mixed bag. 😕

noprompt22:08:00

But I hope some of this helps?