Regular expression style matching library for general matching on list items.

Question

I saw such a library before, but then I forgot about what it was called.

You can specify a template that matches the elements in the list, something like strings:

(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 fully imagine this, can someone shed some light on how one of these things can be written?

Answer 1

More generally, you are asking for an expressive way to make out the sequence. Of course, there are many parsing libraries for Clojure, but many of them make up parsing lexing (there may be good reasons for this in terms of performance optimization), and therefore can only be used for strings. You may need to search outside the toolbox to find a parser that allows you to lex as a separate issue.

Take, for example, The Parsatron (weighs only 262 locks)

 (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 template

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

And check

 (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 

Here you can add sugar to indicate your pattern as you wish.

Answer 2

Too long for a comment:

If you are thinking about your height, you can find Brzozowski's article Regular Expression Derivatives . It describes an efficient method for converting a regular expression into a state machine that recognizes it. An alternative source is John Conway's book Regular Algebra and Finite Machines .

I have the feeling that the Christopher Grand GitHub project , found by @leontalbot, has already done this work, but since I do not have a proper development environment, I cannot investigate. Although its terminal classes are strings, it defines a protocol for regular expressions that matches its joins and sequences (and stars?).

Looking back to other languages.

• Scala does what Clojure does: wraps Java regular expressions.
• Bout people have something for C ++. It is not clear that it requires that the terminals be characters.

Sorry, I could not be more helpful.

---

Added notes:

• This thread in the Google group is worth a read.
• Russ Cox has compiled some links to Implementing Regular Expressions , probably more useful than the ones above.
• The NFA method described in his own article The Regular Expression Matching can be simple and fast , which is mentioned in the Google thread group, looks natural to Clojure.