Algebraic data types: Difference between revisions
Content added Content deleted
(New page: {{task}} Category:Data Structures Some languages offer direct support for [http://en.wikipedia.org/wiki/Algebraic_data_type algebraic data types] and pattern matching on them. While t...) |
(OCaml solution) |
||
Line 26: | Line 26: | ||
| otherwise = s |
| otherwise = s |
||
T _ a y b = ins s |
T _ a y b = ins s |
||
=={{header|OCaml}}== |
|||
type color = R | B |
|||
type 'a tree = E | T of color * 'a tree * 'a * 'a tree |
|||
(** val balance :: color -> 'a tree -> 'a -> 'a tree -> 'a tree *) |
|||
let balance = function |
|||
| (B, T (R, T (R,a,x,b), y, c), z, d) -> T (R, T (B,a,x,b), y, T (B,c,z,d)) |
|||
| (B, T (R, a, x, T (R,b,y,c)), z, d) -> T (R, T (B,a,x,b), y, T (B,c,z,d)) |
|||
| (B, a, x, T (R, T (R,b,y,c), z, d)) -> T (R, T (B,a,x,b), y, T (B,c,z,d)) |
|||
| (B, a, x, T (R, b, y, T (R,c,z,d))) -> T (R, T (B,a,x,b), y, T (B,c,z,d)) |
|||
| (col, a, x, b) -> T (col, a, x, b) |
|||
(** val insert :: 'a -> 'a tree -> 'a tree *) |
|||
let insert x s = |
|||
let rec ins = function |
|||
| E -> T (R,E,x,E) |
|||
| T (col,a,y,b) as s -> |
|||
if x < y then |
|||
balance (col, (ins a), y, b) |
|||
else if x > y then |
|||
balance (col, a, y, (ins b)) |
|||
else |
|||
s |
|||
in let T (_,a,y,b) = ins s |
|||
in T (B,a,y,b) |
Revision as of 10:46, 8 November 2007
Algebraic data types
You are encouraged to solve this task according to the task description, using any language you may know.
You are encouraged to solve this task according to the task description, using any language you may know.
Some languages offer direct support for algebraic data types and pattern matching on them. While this of course can always be simulated with manual tagging and conditionals, it allows for terse code which is easy to read, and can represent the algorithm directly.
As an example, implement insertion in a 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.
Haskell
data Color = R | B data Tree a = E | T Color (Tree a) a (Tree a) balance :: Color -> Tree a -> a -> Tree a -> Tree a balance B (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d) balance B (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d) balance B a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d) balance B a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d) balance col a x b = T col a x b insert :: Ord a => a -> Tree a -> Tree a insert x s = T B a y b where ins E = T R E x E ins s@(T col a y b) | x < y = balance col (ins a) y b | x > y = balance col a y (ins b) | otherwise = s T _ a y b = ins s
OCaml
type color = R | B type 'a tree = E | T of color * 'a tree * 'a * 'a tree (** val balance :: color -> 'a tree -> 'a -> 'a tree -> 'a tree *) let balance = function | (B, T (R, T (R,a,x,b), y, c), z, d) -> T (R, T (B,a,x,b), y, T (B,c,z,d)) | (B, T (R, a, x, T (R,b,y,c)), z, d) -> T (R, T (B,a,x,b), y, T (B,c,z,d)) | (B, a, x, T (R, T (R,b,y,c), z, d)) -> T (R, T (B,a,x,b), y, T (B,c,z,d)) | (B, a, x, T (R, b, y, T (R,c,z,d))) -> T (R, T (B,a,x,b), y, T (B,c,z,d)) | (col, a, x, b) -> T (col, a, x, b) (** val insert :: 'a -> 'a tree -> 'a tree *) let insert x s = let rec ins = function | E -> T (R,E,x,E) | T (col,a,y,b) as s -> if x < y then balance (col, (ins a), y, b) else if x > y then balance (col, a, y, (ins b)) else s in let T (_,a,y,b) = ins s in T (B,a,y,b)