Fork me on GitHub
#meander
<
2020-03-10
>
jeremys10:03:02

Hey! I am struggling to express a pattern. For instance we could have 1 even number followed by 0 or more odd numbers, this pattern repeating in a sequence like in [2 3 5 4 3 2]. The goal would be to get in this example something like [[2 [3 5]] [4 [3]] [2[]]] Any ideas ?

noprompt21:03:44

There is a partial solution to this problem but, actually, what we really need to do this properly is a greedy version of (basically Kleene star which is not that). I would use vanilla Clojure for this in the interim.

jeremys22:03:47

Ok thanks, I gathered the pattern It has a regex feel to it, it might be expressed by (ab*)*. I had a partial solution that identify the first pattern, something like

(-> [2 3 5 4 5 3 6]
    (m/search
      (m/seqable (m/pred even? ?e) .
                 (m/pred odd? !os) ...
                 & (m/and ?rest
                          (m/or
                            (m/seqable)
                            (m/seqable (m/pred even?) .
                                       (m/pred (constantly true)) ...))))
      {:e ?e
       :os !os
       :rest ?rest}))
wondering if I could have use some catamorphism magic on ?rest but I am not used to meander yet and some operator are a little mind bending at first. Plus my solution feels a bit cumbersome compared to the regex. Now I know I can’t really express it. Thanks a lot!

noprompt23:03:45

So the partial solution uses rewrite and cata but due to not having a greedy star or grouping it, and the way rewrite works presently I can’t, in honesty, recommend it.

(m/rewrite [2 3 5 4 3 2]
  [] []
  [(m/pred even? ?even) . (m/pred odd? !odds) ..!ns & ?rest]
  [[?even [!odds ...]] & (m/cata ?rest)])
;; => 
[[2 [3 5]] [4 [3]] [2 []]]
(It could use seqable here.) The zeta branch will have both grouping and greedy star. I think I can bring greedy star to epsilon but I’m not sure about grouping.

noprompt23:03:52

FWIW, I’m spending time working on zeta and less time on epsilon because its easier to build a better, less buggy implementation that reflects the breadth and depth of knowledge that I acquired while working on epsilon. In the spirit of transparency, I’m learning 🙂

timothypratley23:03:40

True story I made this before seeing your cata:

(m/rewrite [2 3 5 4 3 2]
  (m/with [%p (m/or [(m/pred even? !x) . (m/pred odd? !y) ..!n & %p]
                    [])]
    %p)
  [[!x [!y ..!n]] ...])

timothypratley23:03:54

oh damn, my verison drops the last thing though => [[2 [3 5]] [4 [3]]]

timothypratley23:03:43

@U06MDAPTP when you say “I can’t recommend it” about your m/cata solution…. why not? seems good to me???

timothypratley23:03:49

Is it that “greedy Kleene” would be more efficient? concise? (Maybe I should just wait and see 🙂)

noprompt23:03:17

@U06S1EJPL is not greedy. You can think of as a gradient from the least to most amount of greed with respect to context. So its really designed for ambiguity when two or more patterns are next to each other.

noprompt23:03:11

Greed is really about how much to consume and not so much about efficiency or concision.

noprompt23:03:16

For example

;; Using infix * to demo
[!xs * !ys ...]
;; or
[!xs * !ys *]
should always starve !ys by consuming everything because the semantics of * are greedy.

noprompt23:03:24

The same would apply to + by comparison to ..1 . These are not expressing the same idea, at least to my mind they aren’t.

noprompt23:03:05

*/`+` are for when you don’t want ambiguity while /`..N` would be.

noprompt23:03:48

I must apologize to everyone on the face of the earth for not recognizing this subtle difference sooner. 🙂

timothypratley23:03:33

Ah well I don’t disagree with you… but I’m not seeing how it affects expression of this particular problem. In this case it seems like greediness isn’t a factor as there is only one solution.

timothypratley23:03:29

Don’t get me wrong; I love regexs and like the sound of what you are saying, I just don’t get it 😄

noprompt23:03:43

There isn’t one solution to this

[(m/pred odd? !odds) ... & ?rest]

noprompt23:03:13

Hence the need for an explicit distinction of greediness.

timothypratley23:03:25

Oh I think I see what you mean now

noprompt23:03:33

What we really want here is CONSUME ALL THE ODDS DAMMIT!!! 😂

noprompt23:03:49

But because its ambiguous… hahah yeah. 😛

timothypratley23:03:13

is there a situation where you really want non-greedy? I guess for search maybe?

noprompt23:03:38

Yep. 🙂 And find too.

noprompt23:03:25

Hence my apology for not noticing the subtlety

timothypratley23:03:26

I guess somewhat ironically in match means non-greedy but in search means greedy if you have enough constraints o_O I know it doesn’t really mean greedy but you can make it behave like that obviously as per example.

noprompt23:03:40

FYI someone asked about having Mathematica’s Longest and we will have that in the form of greedy Kleene start both on epsilon and zeta.

1
noprompt23:03:29

In fact, zeta will basically have as much or all of regex as humanly possible.

noprompt23:03:20

I also want to thank everyone, again, for the millionth time for supporting the project and suffering lows. 🙂

noprompt23:03:38

And sharing the highs. 😉

ezmiller7723:03:04

Hey I’m wondering if it’s possible to extract the structures that one passes to the match function. Eg.. I tried something like this:

(def match `{:a ?a :b ?b})
(def target `{:a ?b :b ?a})
(m/match {:a 1 :2} ~match ~target}

ezmiller7723:03:49

This produced an error:

ezmiller7723:03:51

> non exhaustive pattern match

timothypratley23:03:15

(m/defsyntax m [] '{:a ?a :b ?b})
=> #'happy.beaver/m
(m/defsyntax t [] '{:a ?b :b ?a})
=> #'happy.beaver/t
(m/match {:a 1 :b 2}
  (m)
  (t))
=> {:a ?b, :b ?a}

ezmiller7700:03:21

Hmmm I was wondering about this. Thanks @U06S1EJPL

noprompt23:03:44

Hi @ezmiller77 👋 Someone opened a ticket with a similar structure a while back and the tl;dr to this is “no” and the reason why is that ~expr is an equality check against the match target with respect to the result of expr . Its not for splicing patterns.

noprompt23:03:32

(m/match [20 30]
  [~(* 10 2) ~(* 10 3)]
  :yes)
;; => :yes

noprompt23:03:14

There is work on going in the subsequent branch of the project, zeta, which will allow for this kind of programatic thing.

ezmiller7723:03:47

I see. So basically my use-case here has to do with keeping code readable. So maybe I can just pack the expression inside another fn.

ezmiller7723:03:36

I’m basically trying to use meander to do a large-scale remap of keys on a map, where I’m also adding a bunch of other keys with nil values.

ezmiller7723:03:57

So both the lhs and rhs expressions are gonna be quite large.