Algebraic data types: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: added/changed whitespace and comments.) |
(Added Tailspin solution) |
||
Line 2,046: | Line 2,046: | ||
} |
} |
||
}</lang> |
}</lang> |
||
=={{header|Tailspin}}== |
|||
{{trans|Haskell}} |
|||
Tailspin doesn't have algebraic types or type names, so here using a tag. Neither does it have the type of pattern matching |
|||
that is posited in the problem statement. Arguably Tailspin is more readable while still as concise. |
|||
<lang tailspin> |
|||
processor RedBlackTree |
|||
@: {}; |
|||
sink insert |
|||
templates balance |
|||
when <{colour: <='black'>, left: <{ colour: <='red'> left: <{colour: <='red'>}>}>}> |
|||
do { colour: 'red', |
|||
left: { $.left.left..., colour: 'black'}, |
|||
value: $.left.value, |
|||
right: { $..., left: $.left.right }} ! |
|||
when <{colour: <='black'>, |
|||
left: <{ colour: <='red'> right: <{colour: <='red'>}>}>}> |
|||
do { colour: 'red', |
|||
left: { $.left..., colour: 'black', right: $.left.right.left}, |
|||
value: $.left.right.value, |
|||
right: { $..., left: $.left.right.right }} ! |
|||
when <{colour: <='black'>, right: <{ colour: <='red'> left: <{colour: <='red'>}>}>}> |
|||
do { colour: 'red', |
|||
left: { $..., right: $.right.left.left}, |
|||
value: $.right.left.value, |
|||
right: { $.right..., colour: 'black', left: $.right.left.right }} ! |
|||
when <{colour: <='black'>, right: <{ colour: <='red'> right: <{colour: <='red'>}>}>}> |
|||
do { colour: 'red', |
|||
left: { $..., right: $.right.left}, |
|||
value: $.right.value, |
|||
right: { $.right.right..., colour: 'black' }} ! |
|||
otherwise $ ! |
|||
end balance |
|||
templates ins&{into:} |
|||
when <?($into <={}>)> do { colour: 'red', left: {}, value: $, right: {}} ! |
|||
when <..$into.value> do { $into..., left: $ -> ins&{into: $into.left}} -> balance ! |
|||
otherwise { $into..., right: $ -> ins&{into: $into.right}} -> balance ! |
|||
end ins |
|||
@RedBlackTree: { $ -> ins&{into: $@RedBlackTree} ..., colour: 'black'}; |
|||
end insert |
|||
source toString |
|||
'$@RedBlackTree;' ! |
|||
end toString |
|||
end RedBlackTree |
|||
def tree: $RedBlackTree; |
|||
1..5 -> \('$tree::toString;$#10;' -> !OUT::write $ -> !tree::insert \) -> !VOID |
|||
$tree::toString -> !OUT::write |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
{} |
|||
{colour=black, left={}, right={}, value=1} |
|||
{colour=black, left={}, right={colour=red, left={}, right={}, value=2}, value=1} |
|||
{colour=black, left={colour=black, left={}, right={}, value=1}, right={colour=black, left={}, right={}, value=3}, value=2} |
|||
{colour=black, left={colour=black, left={}, right={}, value=1}, right={colour=black, left={}, right={colour=red, left={}, right={}, value=4}, value=3}, value=2} |
|||
{colour=black, left={colour=black, left={}, right={}, value=1}, right={colour=red, left={colour=black, left={}, right={}, value=3}, right={colour=black, left={}, right={}, value=5}, value=4}, value=2} |
|||
</pre> |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |