Version 1.0.1¹

Source code files:

1. Java: BinaryTree.java, Tnode.java, Visitor.java, BinaryTreeMaker.java, TreeTest.java, (omit: Graphable.java, tmp.dot, GraphViewer.java).

2. Haskell binary trees and general trees: BinaryTree.hs, GeneralTree.hs, GeneralTreeFCNS.hs (?), XmlTree.hs, XmlTree2.hs

3. Haskell binary search trees: BinarySearchTree.hs, TreeSet.hs, TreeSetTest.hs

A. Java Functional Binary Trees

This is a Java implementation of binary trees, in functional style, with graphics provided by the GraphViz library.

(Not in the textbook, handout-10a.ps)

• BinaryTree, mostly functional version.
• Tnode, immutable binary tree nodes.
• Visitor. A Visitor is used to traverse the tree.
• BinaryTreeMaker, a utility for tree construction.
• TreeTest, the test program.
• Graphable, interface for things that can be graphed.
• tmp.dot, a dot input file.
• GraphViewer, mechanism for running dot and display.
• Graphviz — Graph Visualization Software includes dot.

B. Haskell Trees

(src/functional/haskell)

1. BinaryTree.hs
   • import and hiding
   • data declaration: type constructor, data constructors; deriving clause
   • size and height functions
   • lazy evaluation
   • traversal as lazily building a list, somewhat like an iterator
   • fmap
   • actions: mapM_

   • Test tree:

     

2. GeneralTree.hs
   • Using a (linked) list of children for each node
   • data declaration
   • simple data accessors: treeRoot, treeSubtrees; _ “who cares” variable
   • size: mapping a function over a list
   • height: max (in BinaryTree height) took two Ords; maximum takes a list of Ords
   • traversal functions: we can generalize preorder and postorder from binary trees, but how to generalize inorder is unclear (what would it mean?).
     • concat, map, and concatMap functions on lists

   • Test tree:

     

3. (skip) GeneralTreeFCNS.hs is an implementation of general trees using the first child next sibling representation. It seems more trouble than it’s worth!
   • New Haskell language features:
     • Named fields
     • The Maybe type
     • Module declaration with explicit exports
     • case expression
   • There’s an error here in fromTree or toTree.
4. XmlTree.hs is an example of XML tree processing.
   • New Haskell language features
     • Type synonym declaration
     • Monad sequence operator (>>)
5. (optional) XmlTree2.hs using a full-strength XML package (“xml” from Hackage, the module is Text.XML.Light), shows that real XML processing is a bit more complex due to namespaces and qualified names, node types other than element and text, etc.
   • A single pattern match won’t reliably suffice, because there are text nodes containing as little as just a \n in the elements’ contents, in addition to the expected sub-elements.
   • elt@pattern makes elt a variable; its value is whatever matches pattern
   • elt {field=value, ...} creates a modified copy of elt (so that we don’t have to explicitly give the value of each field).

C. Haskell Binary Search Trees

Haskell code:

• BinarySearchTree.hs
  • Introduces the compare method of Ord; similar to Java’s Comparable; also allows <, <=, >, >=, max, min
    • By the way, Eq allows == and /= (not equal to)
  • Introduces (?) “don’t care” variable _ for matching anything (in general, any variable name beginning with _ plays this role)
• TreeSet.hs
  • Encapsulation and information hiding: exports only the type constructor, not data constructor, of TreeSet, thereby hiding its internal structure.
  • instance declaration instead of automatically derived Show instance further supports information hiding
  • Possible exercises: add true set operations, including intersection, union, difference, subset (i.e., is A a subset of B?), equality (instance for Eq with a definition of ==; sets A and B are equal if each is a subset of the other).
• TreeSetTest.hs
  • An interactive main function for demonstrating the TreeSet
  • Demonstrates how “state” can be carried as the parameter(s) of a recursive function