Source code in the jq programming language

# bindings($x) attempts to match . and $x structurally on the
# assumption that . is free of JSON objects, and that any objects in
# $x will have distinct, singleton keys that are to be interpreted as
# variables.  These variables will match the corresponding entities in
# . if . and $x can be structurally matched.
#
# If . and $x cannot be matched, then null is returned;
# otherwise, if $x contains no objects, {} is returned;
# finally, if . and $x can be structurally matched, a composite object containing the bindings
# will be returned.
# Output: null (failure to match) or a single JSON object giving the bindings if any.
def bindings($x):
   if $x == . then {}  # by assumption, no bindings are necessary
   elif ($x|type) == "object"
   then ($x|keys) as $keys
   | if ($keys|length) == 1 then {($keys[0]): .} else "objects should be singletons"|error end
   elif type != ($x|type) then null
   elif type == "array"
   then if length != ($x|length) then null
        else . as $in
        | reduce range(0;length) as $i ({};
            if . == null then null
            else ($in[$i] | bindings($x[$i]) ) as $m
            | if $m == null then null else . + $m end
            end)
	end
   else null
   end ;

include "bindings" {search: "."};

def E: [];  # the empty node
# Each nonempty node is an array: [Color, Left, Value, Right]
# where Left and Right are nodes.

def B: "⚫";
def R: "🔴";

def b(x): bindings({} | x) // empty;

# Input: [$color, $left, $value, $right]
def balance:
  def node: [R, [B, .a, .x, .b], .y, [B, .c, .z, .d]];

  (   b([B, [R, [R,  {a}, {x}, {x}], {y}, {c}],  {z}, {d}])
   // b([B, [R, {a}, {x}, [R,  {b},  {y}, {c}]], {z}, {d}])
   // b([B, {a},{x}, [R,  [R,  {b},  {y}, {c}],  {z}, {d}]])
   // b([B, {a},{x}, [R,  {b}, {y},  [R,  {c},   {z}, {d}]]])
   | node) // . ;

# Input: a node 
def ins($x):
  if . == E then [R, E, $x, E]
  else . as [$col, $left, $y, $right]
  | if   $x < $y then [ $col, ($left|ins($x)), $y, $right]            | balance
    elif $x > $y then [ $col, $left,           $y, ($right|ins($x)) ] | balance
    else $left
    end
  end;

# insert(Value) into .
def insert($x):
  ins($x) as [$col, $left, $y, $right]
  | [ B, $left, $y, $right] ;

def pp: walk( if type == "array" then map(select(length>0)) else . end);

def task($n):
  reduce range(0; $n) as $i (E; insert($i));

task(16) | pp

jq -n -f pattern-matching.jq | grep -v '[][]' | tr -d ',"'