Algebraic data types: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 4: | Line 4: | ||
As an example, implement insertion in a [[wp:Red_Black_Tree|red-black-tree]]. A red-black-tree is a binary tree where each internal node has a color attribute ''red'' or ''black''. Moreover, no red node can have a red child, and every path from the root to an empty node must contain the same number of black nodes. As a consequence, the tree is balanced, and must be re-balanced after an insertion. |
As an example, implement insertion in a [[wp:Red_Black_Tree|red-black-tree]]. A red-black-tree is a binary tree where each internal node has a color attribute ''red'' or ''black''. Moreover, no red node can have a red child, and every path from the root to an empty node must contain the same number of black nodes. As a consequence, the tree is balanced, and must be re-balanced after an insertion. |
||
=={{header|Bracmat}}== |
|||
<lang bracmat> |
|||
( balance |
|||
= a x b y c zd |
|||
. !arg |
|||
: ( B |
|||
. ( ( R |
|||
. ((R.?a,?x,?b),?y,?c) |
|||
| (?a,?x,(R.?b,?y,?c)) |
|||
) |
|||
, ?zd |
|||
) |
|||
| ( ?a |
|||
, ?x |
|||
, ( R |
|||
. ((R.?b,?y,?c),?zd) |
|||
| (?b,?y,(R.?c,?zd)) |
|||
) |
|||
) |
|||
) |
|||
& (R.(B.!a,!x,!b),!y,(B.!c,!zd)) |
|||
| !arg |
|||
) |
|||
& ( ins |
|||
= X tree a m z |
|||
. !arg:(?X.?tree) |
|||
& !tree:(?C.?a,?m,?z) |
|||
& ( !X:<!m |
|||
& balance$(!C.ins$(!X.!a),!m,!z) |
|||
| !X:>!m |
|||
& balance$(!C.!a,!m,ins$(!X.!z)) |
|||
| !tree |
|||
) |
|||
| (R.,!X,) |
|||
) |
|||
& ( insert |
|||
= X tree |
|||
. !arg:(?X.?tree) |
|||
& ins$(!X.!tree):(?.?X) |
|||
& (B.!X) |
|||
) |
|||
& ( insertMany |
|||
= L R tree |
|||
. !arg:(%?L_%?R.?tree) |
|||
& insertMany$(!L.!tree):?tree |
|||
& insertMany$(!R.!tree) |
|||
| insert$!arg |
|||
) |
|||
; |
|||
</lang> |
|||
Test: |
|||
<lang bracmat> |
|||
( it allows for terse code which is easy to read |
|||
, and can represent the algorithm directly |
|||
. |
|||
) |
|||
: ?values |
|||
& insertMany$(!values.):?tree |
|||
& out$!tree |
|||
& done; |
|||
</lang> |
|||
Output: |
|||
<lang> |
|||
B |
|||
. ( B |
|||
. (R.(B.,,),algorithm,(B.,allows,)) |
|||
, and |
|||
, (B.,can,) |
|||
) |
|||
, code |
|||
, ( R |
|||
. ( B |
|||
. (B.(R.,directly,),easy,) |
|||
, for |
|||
, (B.(R.,is,),it,) |
|||
) |
|||
, read |
|||
, ( B |
|||
. (B.,represent,) |
|||
, terse |
|||
, (R.(B.,the,),to,(B.,which,)) |
|||
) |
|||
) |
|||
</lang> |
|||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |