redblack.clj

gistfile1.clj

;; 400ms
(let [t [:black [:red [:red 1 2 3] 3 4] 5 6]]
   (dotimes [_ 10]
     (time
      (dotimes [_ 1e6]
        (match [t]
          [(([:black ([:red ([:red _ _ _] ::m/vector) _ _] ::m/vector) _ _] ::m/vector) |
            ([:black ([:red _ _ ([:red _ _ _] ::m/vector)] ::m/vector) _ _] ::m/vector) |
            ([:black _ _ ([:red ([:red _ _ _] ::m/vector) _ _] ::m/vector)] ::m/vector))] :valid
            :else :invalid)))))

;; ideally sugar so we can write

(let [t [:black [:red [:red 1 2 3] 3 4] 5 6]]
   (dotimes [_ 10]
     (time
      (dotimes [_ 1e6]
        (match [t]
          [(or [:black [:red [:red _ _ _] _ _] _ _]
               [:black [:red _ _ [:red _ _ _]] _ _]
               [:black _ _ [:red [:red _ _ _] _ _]])] :valid
          :else :invalid)))))

I quite like the column syntax here.