Trees

LA home
Computing
 Algorithms
 Bioinformatics
 FP,  λ
 Logic,  π
 MML
 Prog.Langs

FP
 Haskell
  Haskell98
  Trees
   Circular T

Algs:Trees

Binary Trees

Note that there are many ways to define trees in a functional programming languge, this is just one of them. As for lists, the structure of many functions (weight, height etc.) on trees matches that of the data type definition.

A data type can be made printable by adding it to type class Show. This is done by defining function show or showsPrec on the type. The element of the type, here of the tree, must be printable.

module Tree (module Tree) where

data Tree e = Fork e (Tree e) (Tree e) | EmptyTree

contents (Fork e l r) = e
left     (Fork e l r) = l
right    (Fork e l r) = r

weight  EmptyTree   = 0
weight (Fork e l r) = 1+(weight l)+(weight r)

height  EmptyTree   = 0
height (Fork e l r) =
 let lh = height l
     rh = height r
 in 1 + if lh > rh then lh else rh

                         -- make  Tree a  showable
instance Show a => Show (Tree a) where
  -- note the indenting of showsPrec ~ the instance!
  -- showsPrec :: Int ->   a ->  ShowS
  --              priority thing ...
  showsPrec d EmptyTree    rest = "{}" ++ rest
  showsPrec d (Fork e l r) rest =
     "{"++ showsPrec d e
        (showsPrec d l
           (showsPrec d r ("}"++rest)
        )  )

flatten

A tree can be flattened to produce a list of elements in infix order. The real work is done by function fl which contains another use of an accumulating parameter. It runs in linear time.

module Flatten (module Flatten) where
import Tree

flatten EmptyTree = []
flatten t =                  -- O(weight t)-time
 let fl  EmptyTree   ans = ans
     fl (Fork e l r) ans = fl l (e : (fl r ans))
 in fl t []

We can prove that flatten, above, is equivalent to the obvious but slow version:

Definition of the obvious but slow tree flattening method:
slowF EmptyTree = []
slowF (Fork e l r) = append (slowF l) (e : (slowF r))
 
Claim: slowF t = flatten t, for every tree, t.
base case, t = EmptyTree
LHS = slowF EmptyTree = [] = fl EmptyTree [] = flatten EmptyTree = RHS
general case, t = Fork e l r
LHS
= slowF (Fork e l r)
= append (slowF l) (e:(slowF r)) -- defn of slowF
= append (flatten l) (e:(flatten r)) -- by induction on |l| & |r|
= append (fl l []) (e:(flatten r)) -- defn of flatten
= fl l (e:(flatten r)) -- see note below
= fl l (e : (fl r [])) -- defn of flatten
= flatten (Fork e l r) -- defn of flatten
= RHS
 
Note: append (fl t xs) ys = fl t (append xs ys), for every tree t and every pair of lists xs and ys.
proof:
base case, t = EmptyTree
LHS
= append (fl EmptyTree xs) ys
= append xs ys -- defn of fl
= fl EmptyTree (append xs ys) -- ditto
= RHS
general case, t = Fork(e l r)
LHS
= append (fl (Fork e l r) xs) ys
= append (fl l (e:(fl r xs))) ys -- defn of fl
= fl l (append (e:(fl r xs)) ys) -- induction on |l|
= fl l (e:( append (fl r xs) ys )) -- defn of append
= fl l (e:( fl r (append xs ys) )) -- induction on |r|
= fl (Fork e l r) (append xs ys) -- defn of fl
= RHS

The slow method has quadratic time complexity because of the calls to append -- so use the fast linear-time flatten instead.

Test

Simple test main:

module Main where
import Tree
import Flatten

t1 = Fork 2 (Fork 1 EmptyTree EmptyTree)
	    (Fork 3 EmptyTree EmptyTree)

main = print (show t1) >>
       print (show (weight t1)) >>
       print (show (height t1)) >>
       print (show (flatten t1))


L.A. 8/2002
window on the wide world:

Computer Science Education Week

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite,
ver 3.4+

The GIMP
~ free photoshop
Firefox
web browser
FlashBlock
like it says!

Haskell:
(:) cons
[x1,...] list
[ ]list
(++) append
\ λ :-)
:: has type
Compared

© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Saturday, 01-Nov-2014 22:08:35 EST.