Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <blockquote> <p>Conses can also be considered as binary trees, with the car representing the right subtree and the cdr representing the left.</p> </blockquote> <p>You're right to pick up that this seems unconventional. It should probably say that the <code>car</code> would represent the <em>left</em> subtree and that the <code>cdr</code> would represent the <em>right</em> subtree. That said, trees (as well as lists) built from cons cells are <em>intensional</em> data structures. We make a decision about how to to represent structures using cons cells, and then think in terms of that representation, not in terms of the cons cells. So, when we're writing list processing code, we'd prefer </p> <pre><code>(defun mapcar1 (fn list) (cons (funcall fn (first list)) (mapcar fn (rest list)))) </code></pre> <p>to </p> <pre><code>(defun mapcar1 (fn list) (cons (funcall fn (car list)) (mapcar fn (cdr list)))) </code></pre> <p>because we think of a list as having a first element, and there being a <em>rest</em> of the list., even though both would work. It's just a coincidence that because of implementation, <code>car</code> and <code>cdr</code> would work too. (Of course, this is a leaky abstraction when we notice that we have functions named, e.g., <code>mapcar</code> and <code>nthcdr</code> instead of <code>map</code> (well, there <em>is</em> a <code>map</code> function, but it's a little different) and <code>nthrest</code> or <code>nthtail</code>.</p> <p>Similarly, we'd have to make a choice about representing binary trees with cons cells. It doesn't <em>really</em> make a difference whether you do:</p> <pre><code>(defun make-tree (left right) (cons left right)) (defun left (tree) (car tree)) (defun right (tree) (cdr tree)) </code></pre> <p>or</p> <pre><code>(defun make-tree (left right) (cons right left)) (defun left (tree) (cdr tree)) (defun right (tree) (car tree)) </code></pre> <p>because you <em>ought</em> to be using <code>make-tree</code>, <code>left</code>, and <code>right</code> rather than <code>cons</code>, <code>car</code>, and <code>cdr</code> when you're working with trees.</p> <blockquote> <p>Binary trees without interior nodes are not useful for much.</p> </blockquote> <p>He's referring to binary trees whose internal nodes don't have values of their own. For instance, in a binary search tree, a node doesn't only have a left and right subtree, it has an associated value (or element). A binary search tree node is really a <em>triple</em> (element, left, right), not a pair (left, right). Some problems can be solved with binary trees whose nodes don't have an associated value, but for many problems, you'll want nodes that hold two pointers (to left and right subtrees) in addition to a value.</p>
    singulars
    1. This table or related slice is empty.
    1. POCAR represent *right* subtree of a cons?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJoshua Taylor
    1. USJoshua Taylor
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThanks for your answers to both questions. The term "intensional" data structure is new to me, but I think I got a bit sense out of it by reading the following text, also reading "Chapter 13" of Peter Seibel's book "Practical Common Lisp": data structure made from cons can be viewed through different lens according to your intension (on how to interpret it), pretty much like how a database schema can have multiple views...
      singulars
      1. PO
      1. USbruin
    2. COThe second question is due to my unfamiliarity with trees made up from nodes of pairs instead of triples. I was reading some introductary material saying that list data structure
      singulars
      1. PO
      1. USbruin
    3. CO...can be nested thus it's essentially a tree, which is versatile enough to do many things...then I was a bit stuck on figuring out how pair-noded trees can be recognized as conventional triple-noded trees...Now, in the abstract sense (i.e., w/o considering the cons impelementation), how a lisp list can be interpreted as trees? I guess the answer is also depends on intensions...one possible way, i think, is to treat car as the parent of cdr, thus a list can be viewed as a conventional triple-noded tree. e.g. (+ 1 2) is a tree with root being + which has two kids 1 and 2 as leaves...
      singulars
      1. PO
      1. USbruin
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload