Technical reports

Drawing trees —
a case study in functional programming

Andrew Kennedy

June 1993, 9 pages

DOI: 10.48456/tr-303

Abstract

This report 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 solution, independent of programming language implementation. The functional language implementation is described in a bottom up style starting with very general functions over trees and then narrowing in on the particular tree layout algorithm. Its correctness is considered informally. Finally we discuss the implementation’s computational complexity and possible improvements.

Full text

PDF (0.6 MB)

BibTeX record

@TechReport{UCAM-CL-TR-303,
  author =	 {Kennedy, Andrew},
  title = 	 {{Drawing trees --- a case study in functional programming}},
  year = 	 1993,
  month = 	 jun,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-303.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-303},
  number = 	 {UCAM-CL-TR-303}
}