1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<!--Converted with LaTeX2HTML 98.1p1 release (March 2nd, 1998)
originally by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds
* revised and updated by: Marcus Hennecke, Ross Moore, Herb Swan
* with significant contributions from:
Jens Lippmann, Marek Rouchal, Martin Wilck and others -->
<HTML>
<HEAD>
<TITLE>Structural Induction</TITLE>
<META NAME="description" CONTENT="Structural Induction">
<META NAME="keywords" CONTENT="tpman">
<META NAME="resource-type" CONTENT="document">
<META NAME="distribution" CONTENT="global">
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<LINK REL="STYLESHEET" HREF="tpman.css">
<LINK REL="next" HREF="node30.html">
<LINK REL="previous" HREF="node28.html">
<LINK REL="up" HREF="node28.html">
<LINK REL="next" HREF="node30.html">
</HEAD>
<BODY >
<!--Navigation Panel-->
<A NAME="tex2html487"
HREF="node30.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="/usr/share/latex2html/icons/next.png"></A>
<A NAME="tex2html483"
HREF="node28.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="/usr/share/latex2html/icons/up.png"></A>
<A NAME="tex2html477"
HREF="node28.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="/usr/share/latex2html/icons/prev.png"></A>
<A NAME="tex2html485"
HREF="node4.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
SRC="/usr/share/latex2html/icons/contents.png"></A>
<A NAME="tex2html486"
HREF="node58.html">
<IMG WIDTH="43" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="index"
SRC="/usr/share/latex2html/icons/index.png"></A>
<BR>
<B> Next:</B> <A NAME="tex2html488"
HREF="node30.html">Unparsing</A>
<B> Up:</B> <A NAME="tex2html484"
HREF="node28.html">Cookbook</A>
<B> Previous:</B> <A NAME="tex2html478"
HREF="node28.html">Cookbook</A>
<BR>
<BR>
<!--End of Navigation Panel-->
<H2><A NAME="SECTION00091000000000000000">
Structural Induction</A>
</H2>
Perhaps the most straightforward style of computing a value over a tree is by
<EM>structural induction</EM>.
The result of a tree is computed as a function of the results of its subtrees.
The simplest example of such a function is equality of trees.
Two trees are equal if the top nodes have the same structure and all the corresponding
subtrees are equal.
This function is so common that it is always generated by the term processor.
Only one click less trivial is the function to compute the number of leaves of a tree.
An example of that functions follows.
The base case of <I>nroftips</I> simply returns 1,
and the structural induction case just adds the results of the components.
<A NAME="1081"> </A>
<PRE><HR><!--lgrindfile: funny.k 15:10 Jul 19 1996-->
<I>/* A very simple tree structure */</I>
funnytree: Str(<B>casestring</B>)
| Cons(funnytree funnytree)
;
<BR>
<B>int</B> nroftips(funnytree $f)
{
Str: { <B>return</B> 1; }
Cons(l, r): { <B>return</B> nroftips(l) + nroftips(r); }
}
<HR></PRE>
In general one writes a function for every phylum that occurs in the tree.
<P>
<BR><HR>
<ADDRESS>
<I></I>
<BR><I>2000-04-17</I>
</ADDRESS>
</BODY>
</HTML>
|
