Anonymous user
Algebraic data types: Difference between revisions
Added Tailspin solution
m (→{{header|REXX}}: added/changed whitespace and comments.) |
(Added Tailspin solution) |
||
Line 2,046:
}
}</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}}==
| |||