Algebraic data types: Difference between revisions
→{{header|jq}}
Line 1,098:
check''
</lang>
=={{header|jq}}==
'''Adapted from [[#Tcl|Tcl]]'''
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
jq does not have built-in support for pattern matching in the sense of the present task description, but the following `bindings` function takes advantage of the way in which singleton-key JSON objects can be used as variables for pattern-matching. In effect, jq expressions such as `{a}`
can be used as variables in the pattern definitions, and after matching, the corresponding values can be referenced by jq expressions such as `.a`.
'''bindings.jq'''
<lang jq># 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.
# giving the bindings.
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 ;</lang>
'''pattern-matching.jq'''
<lang jq>include "bindings" {search: "."};
# Each nonempty node is an array: [Color, Left, Value, Right]
# where Left and Right are nodes.
def B: "⚫";
def R: "🔴";
def E: []; # the empty node
def binding(x): bindings({} | x) // empty;
# Input: [$color, $left, $value, $right]
def balance:
(binding([B, [R, [R, {a}, {x}, {x}], {y}, {c}], {z}, {d}])
| [R, [B, .a, .x, .b], .y, [B, .c, .z, .d]])
// (binding([B, [R, {a}, {x}, [R, {b}, {y}, {c}]], {z}, {d}])
| [R, [B, .a, .x, .b], .y, [B, .c, .z, .d] ])
// (binding([B, {a},{x}, [R, [R, {b}, {y}, {c}], {z}, {d}]])
| [R, [B, .a, .x, .b], .y, [B, .c, .z, .d] ])
// (binding([B, {a},{x}, [R, {b}, {y}, [R, {c}, {z}, {d}]]])
| [R, [B, .a, .x, .b], .y, [B, .c, .z, .d] ])
// (binding([{col}, {a}, {x}, {b}])
| [.col, .a, .x, .b ]) ;
# 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</lang>
{{out}}
For brevity and perhaps visual appeal, the output from jq has been trimmed as per the following invocation:
<lang sh>jq -n -f pattern-matching.jq | grep -v '[][]' | tr -d ',"'</lang>
<pre>
⚫
⚫
⚫
⚫
1
⚫
2
3
⚫
⚫
4
5
⚫
6
7
⚫
⚫
⚫
8
9
⚫
10
11
⚫
⚫
12
13
⚫
14
🔴
15
</pre>
=={{header|Julia}}==
| |||