Anonymous user
Algebraic data types: Difference between revisions
add E example
(add E example) |
|||
Line 5:
As an example, implement insertion in a [http://en.wikipedia.org/wiki/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|E}}==
{{trans|Haskell}}
In E, a pattern can be used almost anywhere a variable name can. Additionally, there are two operators used for pattern matching idioms: <code>=~</code> (returns success as a boolean, somewhat like Perl's <code>=~</code>), and <code>switch</code> (matches multiple patterns, like Haskell's <code>case</code>).
Both of those operators are defined in terms of the basic bind/match operation: <code>def <var>pattern</var> exit <var>failure_handler</var> := <var>specimen</var></code>
The scoping rules for E's <code>if</code> and <code>||</code> allow <code>balance</code> in this example to reuse the same output expression; this is unusual among pattern-matching systems.
def balance(tree) {
return if (
tree =~ term`tree(black, tree(red, tree(red, @a, @x, @b), @y, @c), @z, @d)` ||
tree =~ term`tree(black, tree(red, @a, @x, tree(red, @b, @y, @c)), @z, @d)` ||
tree =~ term`tree(black, @a, @x, tree(red, tree(red, @b, @y, @c), @z, @d))` ||
tree =~ term`tree(black, @a, @x, tree(red, @b, @y, tree(red, @c, @z, @d)))`
) {
term`tree(red, tree(black, $a, $x, $b), $y, tree(black, $c, $z, $d))`
} else { tree }
}
def insert(elem, tree) {
def ins(tree) {
return switch (tree) {
match term`empty` { term`tree(red, empty, $elem, empty)` }
match term`tree(@color, @a, @y, @b)` {
if (elem < y) {
balance(term`tree($color, ${ins(a)}, $y, $b)`)
} else if (elem > y) {
balance(term`tree($color, $a, $y, ${ins(b)})`)
} else {
tree
}
}
}
}
def term`tree(@_, @a, @y, @b)` := ins(tree)
return term`tree(black, $a, $y, $b)`
}
This code was tested by filling a tree with random values; you can try this at the E REPL:
? var tree := term`empty`
> for _ in 1..20 {
> tree := insert(entropy.nextInt(100), tree)
> }
> tree
=={{header|Haskell}}==
| |||