Trees |
|
Binary TreesNote 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) ) ) flattenA 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:
The slow method has quadratic time complexity because of the calls to append -- so use the fast linear-time flatten instead. TestSimple 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
|
|
↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso-8859-1, fetched Thursday, 28-Mar-2024 09:18:58 UTC. Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off. |