A regex style matching library for generic matching on list items

Question

I've seen a library like this around before but then forgotten about what it was called.

You can specify a pattern that matches elements in a list, something along the lines of:

(def oddsandevens (pattern (n-of odd? :*) (n-of even? 2) :$))

(pattern-match oddsandevens [1 1 2 2]) => true
(pattern-match oddsandevens [1 1 1 2 2]) => true

(pattern-match oddsandevens [1 1 2 2 2]) => false
(pattern-match oddsandevens [1 1 2]) => false

If I'm totally imagining this, can someone shed light on how one might write one of these things?

Answer 1

More generally, you are asking for an expressive way to parse a sequence. There are of course many parsing libraries out there for Clojure, but many of them complect the lexing with the parsing (there may be good reasons for this in terms of optimizing performance), and so can only be used on strings. You might have to look outside the toolbox to find a parser that allows lexing as a separate concern.

Take, for example, The Parsatron (weighing only 262 loc)

(require '[the.parsatron ; sampling of available combinators 
            :refer [run token attempt many times choice always never >> eof]])

(defn matches? [parser input] 
  (run 
    (choice 
      (attempt (>> parser (eof) (always true))) 
      (always false))
    input))

Now define your pattern

(def odds-and-evens (>> (many (token odd?)) (times 2 (token even?))))

And test

(matches? odds-and-evens [1 1 2 2])   ;=> true
(matches? odds-and-evens [1 1 1 2 2]) ;=> true
(matches? odds-and-evens [1 1 2 2 2]) ;=> false
(matches? odds-and-evens [1 1 2])     ;=> false

From here you can add sugar to specify your pattern as desired.