Skip to content

Overview

Jump to bottom Edit New page
Taylor Wood edited this page Oct 14, 2019 · 16 revisions

This library implements a pattern match compilation algorithm that uses the notion of "necessity" from lazy pattern matching.

For example the following pattern:

(let [x true
      y true
      z true]
  (match [x y z]
     [_ false true] 1
     [false true _ ] 2
     [_ _ false] 3
     [_ _ true] 4))
;=> 4

expands into something similar to the following:

(cond
 (= y false) (cond
              (= z false) (let [] 3)
              (= z true) (let [] 1)
              :else (throw (java.lang.Exception. "No match found.")))
 (= y true) (cond
             (= x false) (let [] 2)
             :else (cond
                    (= z false) 3
                    (= z true) 4
                    :else (throw
                           (java.lang.Exception.
                            "No match found."))))
 :else (cond
        (= z false) (let [] 3)
        (= z true) (let [] 4)
        :else (throw (java.lang.Exception. "No match found."))))

Note that y gets tested first. Lazy pattern matching consistently gives compact decision trees. This means faster pattern matching. You can find out more in the top paper cited below.

Matching literals

(let [x true
      y true
      z true]
  (match [x y z]
     [_ false true] 1
     [false true _ ] 2
     [_ _ false] 3
     [_ _ true] 4))
;=> 4

Wherever you would use a wildcard you can use a binding:

(let [x 1 y 2 z 4]
  (match [x y z]
     [1 2 b] [:a0 b]
     [a 2 4] [:a1 a]))
;=> [:a0 4]

Local scope and Symbols

A symbol pattern can represent one of three behaviours:

  • Match on a literal symbol.
(match [['my-sym]]
  [['my-sym]] :success)  ;; Branch is chosen because (= 'my-sym 'my-sym)
;=> :success
  • Match the value of an existing local binding.
(let [a (+ 1 2)]
  (match [[3]]
    [[a]] a))  ;; 3 matches against the value of `a`, local binding is preserved
;=> 3
  • Create a "named" wildcard pattern that creates a binding of the given name to the right of the pattern row.
(match [['my-sym]]
  [[a]] a) ;; a is a wildcard, here bound to 'my-sym on the right of the pattern row
;=> my-sym

Vector matching

Vector patterns support pattern matching any data type that supports the notion of random access. Clojure's persistent vectors are supported out of the box - note however the feature is extensible to primitive arrays and even for pattern matching bits in a primitive byte.

(let [v [1 2 3]]
  (match [v]
    [[1 1 1]] :a0
    [[1 2 1]] :a1
    [[1 2 _]] :a2))
;=> :a2

Vector patterns also support the familiar rest syntax from destructuring.

(let [v [3 2 3]]
  (match [v]
    [[1 1 3]] :a0
    [[2 & r]] :a1
    [[3 & r]] :a2))
;=> :a2

It's simple to extend match to support primitive arrays so you can write the following:

(defn balance [^objects node]
  (matchv ::objects [node]
    [(:or [:black [:red [:red a x b] y c] z d]
          [:black [:red a x [:red b y c]] z d]
          [:black a x [:red [:red b y c] z d]]
          [:black a x [:red b y [:red c z d]]])] (R (B a x b) y (B c z d))))

See clojure.core.match.array for some ideas.

Seq matching

Seq patterns are optimized for working with sequences.

(let [x [1 2 nil nil nil]]
   (match [x]
     [([1] :seq)]   :a0
     [([1 2] :seq)] :a1
     [([1 2 nil nil nil] :seq)] :a2))
;=> :a2

Seq patterns also support the familiar rest syntax from destructuring.

(let [x '(1 2 3 4)]
  (match [x]
    [([1] :seq)] :a0
    [([_ 2 & ([a & b] :seq)] :seq)] [:a1 a b]))
;=> [:a1 3 (4)]

Map matching

(let [x {:a 1 :b 1}]
   (match [x]
     [{:a _ :b 2}] :a0
     [{:a 1 :b _}] :a1
     [{:c 3 :d _ :e 4}] :a2))
;=> :a1

You can constrain map matching so that only maps with the exact key set will match:

(let [x {:a 1 :b 2}]
  (match [x]
    [({:a _ :b 2} :only [:a :b])] :a0
    [{:a 1 :c c}] :a1
    [{:c 3 :d d :e 4}] :a2))
;=> :a0

This will return :a0. Note that if you specify a key but you don't care about its value, you are asserting that the key must at least be present. For example:

(let [x {:a 1 :b 1}]
  (match [x]
    [{:c _}] :a0
    :else :no-match))
:=> :no-match

It's also useful to specify that some map has only a set of specified keys, this can be accomplished with the :only map pattern modifier:

(let [x {:a 1 :b 2}]
  (match [x]
    [({:a _ :b 2} :only [:a :b])] :a0
    [{:a 1 :c _}] :a1
    [{:c 3 :d _ :e 4}] :a2
    :else nil))
:=> :a0

This will return :a0 however the following:

(let [x {:a 1 :b 2 :c 3}]
  (match [x]
    [({:a _ :b 2} :only [:a :b])] :a0
    [{:a 1 :c _}] :a1
    [{:c 3 :d _ :e 4}] :a2
    :else nil))
;=> :a1

Will return :a1.

Special Syntax

The list syntax () is reserved for special uses. It does not match a literal list.

Or Patterns, Guards and As Patterns use this syntax.

To match a list, consider using the :seq syntax mentioned above, eg:

(let [val '(:a)] 
  (match [val]
    [([:a] :seq)] "A"
    [([:b] :seq)] "B"))

Or Patterns

Or patterns are supported anywhere you would use a pattern:

(let [x [1 2 3]]
  (match [x]
    [[1 (:or 3 4) 3]] :a0
    [[1 (:or 2 3) 3]] :a1))
;=> :a1
    
(let [x {:a 3}]
  (match [x]
    [{:a (:or 1 2)}] :a0
    [{:a (:or 3 4)}] :a1))
;=> :a1

Guards

Guards are simple boolean tests. You can specify them like so:

(defn div3? [x] (zero? (rem x 3)))
(let [y [2 3 4 5]]
  (match [y]
    [[_ (a :guard even?) _ _]] :a0
    [[_ (b :guard [odd? div3?]) _ _]] :a1))
;=> :a1

Or in maps, where the guard predicate is invoked with the map:

(let [y {:a 5 :b 9 :c 0}]
  (match [y]
    [{:a _ :b 2}] :a0
    [({:a 5 :b _} :guard [(comp odd? :b) (comp div3? :b)])] :a1
    [({:a 5 :b _} :guard #(= 0 (:c %)))] :a2))
=> :a1

As Patterns

Sometimes you'd like capture a part of the match with a binding:

(let [v [[1 2]]]
  (match [v]
    [[[3 1]]] :a0
    [[([1 a] :as b)]] [:a1 a b]))
;=> [:a1 2 [1 2]]

Java Interop

By extending Java types to IMatchLookup, Java types can participate in map patterns:

(extend-type java.util.Date
  IMatchLookup
  (val-at* [this k not-found]
    (case k
      :year    (.getYear this)
      :month   (.getMonth this)
      :date    (.getDate this)
      :hours   (.getHours this)
      :minutes (.getMinutes this)
      not-found)))

(let [d (java.util.Date. 2010 10 1 12 30)]
  (match [d]
    [{:year 2009 :month a}] [:a0 a]
    [{:year (:or 2010 2011) :month b}] [:a1 b]))
;=> [:a1 10]

The above is a bit tedious to write so clojure.core.match.java supplies a bean-match macro that can be used as follows:

(bean-match java.awt.Color)
(match [java.awt.Color/RED]
  [{:red red :green green :blue blue}] [red green blue]
  :else :error)
;; => [255 0 0]

Note on Pattern Rows

A pattern row is delimited with [], and is not a pattern itself.

For example, this syntax is illegal:

(let [v 1]
  (match [v]
    ([1] :as w) :a0))  ; Illegal! [1] is a pattern row, not a pattern.

Matching single variables

Matching single variables is simple:

(let [x 3]
  (match x
    1 :a0
    2 :a1
    :else :a2))
;=> :a2

Note that :else clauses are special and never need to be wrapped.

Road Map

A good chunk of Maranget's algorithm for pattern matching has been implemented. We would like to flesh out the pattern matching functionality. Once that work is done, we'll move on to predicate dispatch.

Resources

The four most relevant papers:

Further reading:

Add a custom footer
Add a custom sidebar
Clone this wiki locally