Anonymous user
Algebraic data types: Difference between revisions
→{{header|Perl 6}}: new entry
m (omit from Ada) |
(→{{header|Perl 6}}: new entry) |
||
Line 177:
t(b A Y B)
end</lang>
=={{header|Perl 6}}==
{{works with|Rakudo|2011.07}}
Perl 6 doesn't have algebraic data types (yet), but it does have pretty good pattern matching in multi signatures.
<lang perl6>proto balance ($, @, $, @) {*}
multi balance('B',['R',['R',$a,$x,$b],$y,$c],$z,$d) { ['R',['B',$a,$x,$b],$y,['B',$c,$z,$d]] }
multi balance('B',['R',$a,$x,['R',$b,$y,$c]],$z,$d) { ['R',['B',$a,$x,$b],$y,['B',$c,$z,$d]] }
multi balance('B',$a,$x,['R',['R',$b,$y,$c],$z,$d]) { ['R',['B',$a,$x,$b],$y,['B',$c,$z,$d]] }
multi balance('B',$a,$x,['R',$b,$y,['R',$c,$z,$d]]) { ['R',['B',$a,$x,$b],$y,['B',$c,$z,$d]] }
multi balance($col, $a, $x, $b) is default { [$col, $a, $x, $b] }
proto insert ($, @) {*}
multi ins( $x, [] ) { ['R', [], $x, []] }
multi ins( $x, $s [$col, $a, $y, $b] ) {
when $x before $y { balance $col, ins($x, $a), $y, $b }
when $x after $y { balance $col, $a, $y, ins($x, $b) }
default { $s }
}
multi insert( $x, $s ) {
my ([$, $a, $y, $b]) := ins($x, $s);
['B', $a, $y, $b];
}</lang>
This is implemented with string tags instead of enums because [[rakudo]] does not yet properly treat enums as constants, and thus treats the multi dispatch as ambiguous. Also, in order to correctly parameterize the generic tree type, we'd currently have use a parametric role in a class, which would have been a bit more cluttery, so we don't check the type of tree insertions here.
It does, however, use the generic comparison operators <tt>before</tt> and <tt>after</tt>, so it should work on any ordered type.
Testing it by inserting 10 integers in random order:
<lang perl6>sub MAIN {
my $t = [];
$t = insert($_, $t) for (1..10).pick(*);
say $t.perl;
}</lang>
Output:
<pre>["B", ["B", ["R", ["B", [], 1, []], 2, ["B", [], 3, []]], 4, ["B", [], 5, []]], 6, ["B", ["B", [], 7, []], 8, ["B", [], 9, ["R", [], 10, []]]]]</pre>
=={{header|Prolog}}==
| |||