Algebraic data types: Difference between revisions
Content added Content deleted
Line 1,098: | Line 1,098: | ||
check'' |
check'' |
||
</lang> |
</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}}== |
=={{header|Julia}}== |