This article describes the application of functional programming techniques to a problem previously studied by imperative programmers, that of drawing general trees automatically. We first consider the nature of the problem and the ideas behind its solutio
J. Functional Programming 6 (3): 527{534, May 1996 c 1996 Cambridge University Press 527
FUNCTIONAL PEARLS
Drawing Trees
University of Cambridge Computer Laboratory New Museums Site, Pembroke Street Cambridge CB2 3QG, United Kingdom
ANDREW J. KENNEDY
Abstract This article describes the application of functional programming techniques to a problem previously studied by imperative programmers, that of drawing general trees automatically. We rst consider the nature of the problem and the ideas behind its solution (due to Radack), independent of programming language implementation. We then describe a Standard ML program which re ects the structure of the abstract solution much better than an imperative language implementation. We conclude with an informal discussion on the correctness of the implementation and some changes which improve the algorithm's worst-case time complexity.
1 The problem and its solution The problem is this: given a labelled tree, assign to each node a position on the page to give an aesthetically pleasing rendering of the tree. We assume that nodes at the same depth are positioned on the same horizontal line on the page, so the problem reduces to nding a position horizontally for each node. But what do we mean by\aesthetically pleasing"? The various papers on the subject (Radack, 1988; Wetherell and Shannon, 1979; Vaucher, 1980; Reingold and Tilford, 1981; Walker, 1990) list aesthetic rules which constrain the positions in a number of ways. We adopt the same rules as Radack and Walker: 1. Two nodes at the same level should be placed at least a given distance apart. 2. A parent should be centred over its o spring. 3. Tree drawings should be symmetrical with respect to re ection|a tree and its mirror image should produce drawings that are re ections of each other. In particular, this means that symmetric trees will be rendered symmetrically. So, for example, Figure 1 shows two renderings, the rst bad, the second good. 4. Identical subtrees should be rendered identically|their position in the larger tree should not a ect their appearance. In Figure 2 the tree on the left fails the test, and the one on the right passes. Finally, trees should be as narrow as possible without violating these rules.
FUNCT I ONAL PEARLS Draw... 暂无评价 8页 免费 FUNCT I ONAL PEARLS ...Testing for set membership in a diet is similar to binary search trees: ...
FUNCT I ONAL PEARLS Combinators for Breadth-First Search_专业资料。Every functional programmer knows the technique of \replacing failure by a list of ...
Functional Programming 1 FUNCT I ONAL PEARLS Inve Our aim in this pearl is to exploit simple equational reasoning to derive the inverse of the Burrows-...
Under consideration for publi...
FUNCT I ONAL PEARLS Diet... 暂无评价 6页 免费 I. PRACTICAL NEED FOR FU... 暂无评价 6页 免费 2.1 Sets 暂无评价 20页 1财富值 Ergodic Theory ...
FUNCT I ONAL PEARLS Comb... 暂无评价 11页 免费 first draft 2页 5财富值 First Draft 17页 免费 First draft 1页 免费 Lecture 17 Shortest Path... ...
FUNCT I ONAL PEARLS Expl... 暂无评价 12页 免费 Min-max heaps – ... Binomial Heaps Leftist trees Binomial heaps Actual Amortized O(log n) O(...
免费 FUNCT I ONAL PEARLS... 暂无评价 11页 免费 leanEA A Poor Man's Ev... 暂无评价 34页 免费 Abstract A Poor Man's ... 暂无评价 10页 免费...
暂无评价 7页 免费 FUNCT I ONAL PEARLS A Po... 暂无评价 11页 免费喜欢此文档的还喜欢 小学英语阅读100篇WORD文本... 48页 2财富值 办公文具2 36页 ...
FUNCT I ONAL PEARLS A Po... 暂无评价 11页 免费 Parser Combinators for E... 6页 免费 Abstract Visual Haskell ... 12页 免费 Programming Language ...
热门文档