Anonymous user
Algebraic data types: Difference between revisions
Added a Java (JDK 21 + Preview features) translation for the existing Kotlin solution. Removed the omission tag for Java.
Thundergnat (talk | contribs) m (Automated syntax highlighting fixup (second round - minor fixes)) |
imported>Maruseron (Added a Java (JDK 21 + Preview features) translation for the existing Kotlin solution. Removed the omission tag for Java.) |
||
| (3 intermediate revisions by 3 users not shown) | |||
Line 978:
Finally a caution: red black trees exhibit poor cache coherency. In many (perhaps most or all) cases an amortized hierarchical linear sort mechanism will perform better than a red black tree implementation. (And that characteristic is especially true of this particular implementation.)
=={{header|Java}}==
{{trans|Kotlin}}
{{works with|OpenJDK|21 (Preview)}}
Java 21 has added support for ADTs (in the form of sealed types), which are narrowable through a switch expression. Despite having no fully-fledged pattern matching, a combination of record deconstruction patterns and guarded patterns allows for something very similar through switch expressions:
<syntaxhighlight lang="java">public class Task {
enum Color { R, B }
sealed interface Tree<A extends Comparable<A>> permits E, T {
default Tree<A> insert(A a) {
return switch(ins(a)) {
case T(_, var l, var v, var r) -> new T<>(Color.B, l, v, r);
case E() -> new E<>();
};
}
Tree<A> ins(A a);
}
record E<A extends Comparable<A>>() implements Tree<A> {
@Override
public Tree<A> ins(A a) {
return new T<>(Color.R, new E<>(), a, new E<>());
}
@Override
public String toString() { return "E"; }
}
record T<A extends Comparable<A>>(Color color, Tree<A> left,
A value, Tree<A> right) implements Tree<A> {
@Override
public Tree<A> ins(A a) {
return switch(Integer.valueOf(a.compareTo(value))) {
case Integer i when i < 0 -> new T<>(color, left.ins(a), value, right).balance();
case Integer i when i > 0 -> new T<>(color, left, value, right.ins(a)).balance();
default -> this;
};
}
private Tree<A> balance() {
if (color == Color.R) return this;
return switch (this) {
// unnamed patterns (case T<A>(_, ...)) are a JDK21 Preview feature
case T<A>(_, T<A>(_, T<A>(_, var a, var x, var b), var y, var c), var z, var d)
when left instanceof T<A> le && le.left instanceof T<A> le_le &&
le.color == Color.R && le_le.color == Color.R ->
new T<>(Color.R, new T<>(Color.B, a, x, b), y, new T<>(Color.B, c, z, d));
case T<A>(_, T<A>(_, var a, var x, T<A>(_, var b, var y, var c)), var z, var d)
when left instanceof T<A> le && le.right instanceof T<A> le_ri &&
le.color == Color.R && le_ri.color == Color.R ->
new T<>(Color.R, new T<>(Color.B, a, x, b), y, new T<>(Color.B, c, z, d));
case T<A>(_, var a, var x, T<A>(_, T<A>(_, var b, var y, var c), var z, var d))
when right instanceof T<A> ri && ri.left instanceof T<A> ri_le &&
ri.color == Color.R && ri_le.color == Color.R ->
new T<>(Color.R, new T<>(Color.B, a, x, b), y, new T<>(Color.B, c, z, d));
case T<A>(_, var a, var x, T<A>(_, var b, var y, T<A>(_, var c, var z, var d)))
when right instanceof T<A> ri && ri.right instanceof T<A> ri_ri &&
ri.color == Color.R && ri_ri.color == Color.R ->
new T<>(Color.R, new T<>(Color.B, a, x, b), y, new T<>(Color.B, c, z, d));
default -> this;
};
}
@Override
public String toString() {
return STR."T[\{color}, \{left}, \{value}, \{right}]"; // String templates are a JDK 21 Preview feature
}
}
public static void main(String[] args) {
Tree<Integer> tree = new E<>();
for (var i : IntStream.rangeClosed(1, 16).toArray()) {
tree = tree.insert(i);
}
System.out.println(tree);
}
}
</syntaxhighlight>
{{out}}
<pre>
T[B, T[B, T[B, T[B, E, 1, E], 2, T[B, E, 3, E]], 4, T[B, T[B, E, 5, E], 6, T[B, E, 7, E]]], 8, T[B, T[B, T[B, E, 9, E], 10, T[B, E, 11, E]], 12, T[B, T[B, E, 13, E], 14, T[B, E, 15, T[R, E, 16, E]]]]]
</pre>
=={{header|jq}}==
Line 2,382 ⟶ 2,466:
end balance
templates ins&{into:}
when <?($into <´node´ ={}>)> do { colour: 'red', left: {}, value: $, right: {}} !
when <..$into.value::raw> do { $into..., left: $ -> ins&{into: $into.left}} -> balance !
otherwise { $into..., right: $ -> ins&{into: $into.right}} -> balance !
Line 2,514 ⟶ 2,598:
}
}</syntaxhighlight>
=={{header|TXR}}==
TXR Lisp has structural pattern matching on objects of all kinds, including structures. We define a red-black tree structure like this, with a BOA constructor (by-order of arguments) for convenience:
<syntaxhighlight lang="txrlisp">
(defstruct (rbnode color left right data) ()
color
left
right
data)
</syntaxhighlight>
The empty tree case is handled by the <code>nil</code> symbol, so in terms of algebraic types, the tree is a sum of <code>nil</code> and the <code>rbnode</code> struct type, and that struct type is a product type of several properties. For the <code>color</code> slot, we use the keyword symbols <code>:red</code> and <code>:black</code> which needs not be declared anywhere. <code>data</code> can be any value.
TXR Lisp's syntax for matching structures looks like this:
<syntaxhighlight lang="txrlisp">
@(struct time year @y month @m)
</syntaxhighlight>
This example matches a time structure instance, capturing the year as <code>y</code>
and month as <code>m</code>.
Structures aren't ordered tuples; they are clumps of of named slots,
that cannot be accessed by position. This would break under
inheritance, in particular multiple inheritance.
Furthermore, variables have the <code>@</code> sigil in most pattern matching
constructs, because symbols without the sigil denote themselves as literal
patterns. The pattern <code>x</code> matches the symbol <code>x</code>
literally, and no other object. The pattern <code>@x</code> matches any
object and captures it as <code>x</code>.
These above features make it verbose and somewhat noisy to express
pattern matching of our <code>rbtree</code> node. However, TXR Lisp's
pattern matching sublanguage supports application-defined macro patterns,
defined by the <code>defmatch</code> macro. With these we can achieve
a shorthand notation which matches nodes as if they were ordered tuples,
and which drops the sigils from variables.
<syntaxhighlight lang="txrlisp">
(defmatch rb (color left right data)
(flet ((var? (sym) (if (bindable sym) ^@,sym sym)))
^@(struct rbnode
color ,(var? color)
left ,(var? left)
right ,(var? right)
data ,(var? data))))
(defmatch red (left right data)
^@(rb :red ,left ,right ,data))
(defmatch black (left right data)
^@(rb :black ,left ,right ,data))
</syntaxhighlight>
And with all the above, we can write the code like this:
<syntaxhighlight lang="txrlisp">
(defun-match rb-balance
((@(or @(black @(red @(red a b x) c y) d z)
@(black @(red a @(red b c x) x) d z)
@(black a @(red @(red b c y) d z) x)
@(black a @(red b @(red c d z) y) x)))
(new (rbnode :red
(new (rbnode :black a b x))
(new (rbnode :black c d z))
y)))
((@else) else))
(defun rb-insert-rec (tree x)
(match-ecase tree
(nil
(new (rbnode :red nil nil x)))
(@(rb color a b y)
(cond
((< x y)
(rb-balance (new (rbnode color (rb-insert-rec a) b y))))
((> x y)
(rb-balance (new (rbnode color a (rb-insert-rec b) y))))
(t tree)))))
(defun rb-insert (tree x)
(match-case (rb-insert-rec tree x)
(@(red a b y) (new (rbnode :black a b y)))
(@else else)))
</syntaxhighlight>
Insertion is split into two functions: a recursive one which works on its own, except that whenever the tree ends up with a red root, we would like to rewrite that node to a black one. We make the insertion function call the recursive one and then do this fix-up using pattern matching again.
=={{header|Wren}}==
{{trans|Go}}
Wren doesn't have either algebraic data types or pattern matching though, despite that, the ''T.balance()'' method looks better than I thought it would :)
<syntaxhighlight lang="
var B = "B"
Line 2,611 ⟶ 2,785:
{{omit from|BBC BASIC}}
{{omit from|C}}
{{omit from|Pascal}}
{{omit from|Processing}}
| |||