Algebraic data types: Difference between revisions
no edit summary
No edit summary |
|||
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.
=={{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}}==
| |||