[Tutor] A Faq can be a tree (long)
VanL
van@lindbergs.org
Mon, 14 May 2001 01:09:45 -0600
Remco Gerlich wrote:
> On 0, VanL <van@lindbergs.org> wrote:
> > Here is how I came to this project:
> >
> > I was thinking about writing a faq generator and maintainer for my work. While
> > thinking about the problem, it occurred to me that a faq could be easily
> > represented by a tree of faqEntry objects.
>
> Wait wait wait - *why* did this occur to you? Is the FAQ itself a hierarchy?
>
[snip]
>
>
> I don't think a tree is all that natural for a FAQ. I'd go for a dictionary
> - each FAQ entry has its own keyword or title, and that's the dictionary
> key. Hyperlinks are trivial (they point to another keyword). This goes along
> with the first rule of data structures in Python - "Use a dictionary".
> Alternatively you might want a list, or some object wrapping either of the
> two.
>
> But what's so tree-like about FAQs? They're organized into chapters, but
> besides that they're mostly a list of questions...
Imagine a faq as being described by the following grammar:
<faq> := <faqentry>
<faqentry> := <data>|<data><subsection>
<subsection> := <subfaq>|<subfaq><subsection>
<subfaq> := <faqentry>
<data> := <question><answer>|<heading>
<heading> := <title><head>
<title> := string
<head> := string
<question> := string
<answer> := string
I don't guarantee that this grammer is unambiguous, but it should be clear enough to
show the idea.
This grammar allows the entire faq to be represented by a tree -- the parse tree for
this grammar.
To be more concrete, take the following faq.
[start imaginary faq]
Faq about faqtrees
This is a faq about faqtrees. It is also an illustration of why a tree representation
could be useful.
1. Q: What are trees?
A: Plants.
2. Q: What are FAQs?
A: Just the facts.
3. Q: What is question number 6?
A: There is no question number 6.
The parse tree for this FAQ would be:
FAQ
|
Faqentry
/\
/ \
/ \
Data Subsection
/| | \
/ \ | \
Title Head subfaq subsection
| | |
| \
string string faqentry subfaq
subsection
|
| |
Data
faqentry subfaq
/ |
/ \
Tree Question Ans Data
faqentry
/
\ \
FAQ question
answer Data
/\
6 question answer
The data structure implementing this faq would be:
Root faqentry (members: title, head, children)
The childrenlist would point to:
1. faqentry (members: tree question, answer children=None)
2. faqentry (members: FAQ question, answer, children=None)
3. faqentry (members: Question 6, answer, children=None)
Anyway, in this way, the faq could have an arbitrary number of subsections that would
all "know" their relationship to the parent structure by their place in the tree. The
advantage of this over the dictionary implementation that you propose is:
1. No namespace collision for child entries (ok, you would need a really large
faq to actually run into this problem)
2. Inserting a new question/answer would automatically renumber anything
necessary, which would be a big time win for large complicated faqs.
If you still think I'm on drugs for thinking that I should implement a faq as a tree,
tell me. That was just my thinking.
Van