Personal tools

Stanamic typing

From HaskellWiki

Revision as of 12:00, 10 April 2006 by DonStewart (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

"We describe a datatype of polymorphic balanced binary trees: AVL trees. The trees are polymorphic: the values in different nodes may have different type. The trees are balanced: for each non-leaf node, the heights of its two children can differ at most by one. Here, by definition the height of a node is 1 + max of the heights of its children. A leaf node has the height of 0.

The main feature of the present approach is a blended static and dynamic enforcement of the balancing constraint. The function make_node verifies the balancing constraint at compile time -- if it can. If the static check is not possible, the function delays the check till the run-time"

Polymorphic stanamically balanced AVL trees