Some languages offer direct support for algebraic data types and pattern matching on them. While this of course can always be simulated with manual tagging and conditionals, it allows for terse code which is easy to read, and can represent the algorithm directly.



Task

As an example, implement insertion in a red-black-tree.

A red-black-tree is a binary tree where each internal node has a color attribute red or black. Moreover, no red node can have a red child, and every path from the root to an empty node must contain the same number of black nodes. As a consequence, the tree is balanced, and must be re-balanced after an insertion.




Reference

Red-Black Trees in a Functional Setting

# 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 ;