Algebraic data types: Difference between revisions
Content added Content deleted
m (omit from Ada) |
(→{{header|Perl 6}}: new entry) |
||
Line 177: | Line 177: | ||
t(b A Y B) |
t(b A Y B) |
||
end</lang> |
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}}== |
=={{header|Prolog}}== |