Thesis
A New View of Binary Trees
- Abstract:
-
We present a new formalism of labelled binary trees, using two partial binary constructors instead of the usual total ternary constructor. This formalism is complemented by some higher-order operators, encapsulating common patterns of computation on trees. We explore their use by deriving solutions to a couple of algorithmic problems on trees.
The work proceeds in the Bird-Meertens style. This is a calculus for programs, closely related to applicative programming languages. Expressions are written at the function level, avoiding the use of unnecessary names and being as concise as possible. Derivations are performed by program transformation — the application of correctness-preserving transformations to an initial specification, with the intention of improving its efficiency without changing its meaning.
Actions
Authors
- Publication date:
- 1988
- DOI:
- Type of award:
- DPhil
- Level of award:
- Doctoral
- Awarding institution:
- University of Oxford
- UUID:
-
uuid:0ed98904-71e5-46ab-bca0-5eeb57b8ca08
- Local pid:
-
cs:2339
- Deposit date:
-
2015-03-12
- ARK identifier:
Terms of use
- Copyright holder:
- Gibbons, J
- Copyright date:
- 1988
If you are the owner of this record, you can report an update to it here: Report update to this record