Difference between revisions of "Stanamic typing"
From HaskellWiki
Tomjaguarpaw (talk | contribs) (Deleting page that hasn't been edited for over 10 years) |
m (Reverted edits by Tomjaguarpaw (talk) to last revision by DonStewart) |
||
| Line 1: | Line 1: | ||
| + | "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" | ||
| + | |||
| + | [http://okmij.org/ftp/Haskell/types.html#stanamic-AVL Polymorphic stanamically balanced AVL trees] | ||
| + | |||
| + | [[Category:Idioms]] | ||
Latest revision as of 15:19, 6 February 2021
"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"