From: jrwats
Subject: fringe definition
Date: 
Message-ID: <d6105697-9bd7-4e55-8562-6a609dfd65b7@i24g2000prf.googlegroups.com>
So I've seen many people implement functions that return the fringe
(all the leaves) of a tree.  However, all the implementations I've
seen iterate through *all* the nodes.  So I either do not have the
definition of fringe correct, or LISPers have a different defintion or
something else - I don't know what.  In my view here is a binary tree
with 4 as the root node, 2 as it's left child, 6 as it's right and so
on:

(setf bin-tree '(4 (2 1 3) (6 5 7)))

Thus in my view the only fringe nodes (leaves) are 1, 3, 5, and 7.

Below are 2 implementations:
#1 fringe implementation from http://home.pipeline.com/~hbaker1/Iterator.html:
(defun fringe (x &optional (c nil))                        ; fringe of
tree x.
  (if (atom x) (cons x c) (fringel x c)))

(defun fringel (xl c)                            ; fringe of list of
trees xl.
  (if (null xl) c (fringe (car xl) (fringel (cdr xl) c))))

(fringe bin-tree) = (4 2 1 3 6 5 7)

#2 from http://www.dreamsongs.com/10ideas.html
(defun leaves (tree)
  (cond ((atom tree) (list tree))
        (t (append (leaves (car tree))
                   (leaves (cdr tree))))))

(leaves bin-tree) = (4 2 1 3 nil 6 5 7 nil nil)
gotta love the nils


...Finally here is my view of what the fringe implementation should
be:
(defun left-child (node)
  (cond ((or (atom node) (null node)) nil)
        ((cadr node))))

(defun right-child (node)
  (cond ((or (atom node) (null node)) nil)
        ((caddr node))))

(defun is-leaf (node)
  (or (not (left-child node))
      (not (right-child node))))

(defun get-fringe (tree)
  (cond ((is-leaf tree) (list tree))
        (t (append (get-fringe (left-child tree))
                   (get-fringe (right-child tree)))))

(get-fringe bin-tree) = (1 3 5 7)

So what is going on?

From: Tim Bradshaw
Subject: Re: fringe definition
Date: 
Message-ID: <bfa2771a-4507-403b-a79b-99d26c4a9549@k30g2000hse.googlegroups.com>
On Aug 4, 7:55 pm, jrwats <······@gmail.com> wrote:

>
> So what is going on?

They are using different notions of what a tree is than you.  For
instance the Gabriel one is walking over the cons tree and
accumulating its leaves.  That's a completely different thing than
your tree.

So, basically you need to understand the data structures involved, not
just assume that because the function has a particular name it will do
what you think it should.
From: Rainer Joswig
Subject: Re: fringe definition
Date: 
Message-ID: <joswig-781C35.22143004082008@news-europe.giganews.com>
In article 
<····································@i24g2000prf.googlegroups.com>,
 jrwats <······@gmail.com> wrote:

> So I've seen many people implement functions that return the fringe
> (all the leaves) of a tree.  However, all the implementations I've
> seen iterate through *all* the nodes.  So I either do not have the
> definition of fringe correct, or LISPers have a different defintion or
> something else - I don't know what.  In my view here is a binary tree
> with 4 as the root node, 2 as it's left child, 6 as it's right and so
> on:
> 
> (setf bin-tree '(4 (2 1 3) (6 5 7)))
> 
> Thus in my view the only fringe nodes (leaves) are 1, 3, 5, and 7.
> 
> Below are 2 implementations:
> #1 fringe implementation from http://home.pipeline.com/~hbaker1/Iterator.html:
> (defun fringe (x &optional (c nil))                        ; fringe of
> tree x.
>   (if (atom x) (cons x c) (fringel x c)))
> 
> (defun fringel (xl c)                            ; fringe of list of
> trees xl.
>   (if (null xl) c (fringe (car xl) (fringel (cdr xl) c))))
> 
> (fringe bin-tree) = (4 2 1 3 6 5 7)
> 
> #2 from http://www.dreamsongs.com/10ideas.html
> (defun leaves (tree)
>   (cond ((atom tree) (list tree))
>         (t (append (leaves (car tree))
>                    (leaves (cdr tree))))))
> 
> (leaves bin-tree) = (4 2 1 3 nil 6 5 7 nil nil)
> gotta love the nils
> 
> 
> ...Finally here is my view of what the fringe implementation should
> be:
> (defun left-child (node)
>   (cond ((or (atom node) (null node)) nil)
>         ((cadr node))))
> 
> (defun right-child (node)
>   (cond ((or (atom node) (null node)) nil)
>         ((caddr node))))
> 
> (defun is-leaf (node)
>   (or (not (left-child node))
>       (not (right-child node))))
> 
> (defun get-fringe (tree)
>   (cond ((is-leaf tree) (list tree))
>         (t (append (get-fringe (left-child tree))
>                    (get-fringe (right-child tree)))))
> 
> (get-fringe bin-tree) = (1 3 5 7)
> 
> So what is going on?

Is that homework?

See this:

CL-USER 17 > (sdraw:sdraw '(4 (2 1 3) (6 5 7)))

[*|*]--->[*|*]--------------------------->[*|*]--->NIL
 |        |                                |
 v        v                                v
 4       [*|*]--->[*|*]--->[*|*]--->NIL   [*|*]--->[*|*]--->[*|*]--->NIL
          |        |        |              |        |        |
          v        v        v              v        v        v
          2        1        3              6        5        7



What you see is that (4 (2 1 3) (6 5 7))  is a binary
tree made of conses, numbers and nils.

(4 . ((2 . (1 . (3 . nil))) . ((6 . (5 . (7 . nil))) . nil)))

has the same cons structure as  (4 (2 1 3) (6 5 7))


CL-USER 19 > (equal '(4 . ((2 . (1 . (3 . nil))) . ((6 . (5 . (7 . nil))) . nil)))
                    '(4 (2 1 3) (6 5 7)))
T

left-child = CAR
right-child = CDR
is-leaf = ATOM


Your tree definition is different - that's all.

-- 
http://lispm.dyndns.org/
From: Pascal J. Bourguignon
Subject: Re: fringe definition
Date: 
Message-ID: <87wsiwsejd.fsf@hubble.informatimago.com>
jrwats <······@gmail.com> writes:

> So I've seen many people implement functions that return the fringe
> (all the leaves) of a tree.  However, all the implementations I've
> seen iterate through *all* the nodes.  So I either do not have the
> definition of fringe correct, or LISPers have a different defintion or
> something else - I don't know what.  In my view here is a binary tree
> with 4 as the root node, 2 as it's left child, 6 as it's right and so
> on:
>
> (setf bin-tree '(4 (2 1 3) (6 5 7)))

Ho! La!  Not so fast!

Have a look at:

http://groups.google.com/group/comp.lang.lisp/msg/0c66e597e08be90d


> Thus in my view the only fringe nodes (leaves) are 1, 3, 5, and 7.

You didn't give us enough information yet to know that.


> Below are 2 implementations:
> #1 fringe implementation from http://home.pipeline.com/~hbaker1/Iterator.html:
> (defun fringe (x &optional (c nil))                        ; fringe of
> tree x.
>   (if (atom x) (cons x c) (fringel x c)))
>
> (defun fringel (xl c)                            ; fringe of list of
> trees xl.
>   (if (null xl) c (fringe (car xl) (fringel (cdr xl) c))))
>
> (fringe bin-tree) = (4 2 1 3 6 5 7)


There is some implied tree representation at work here.
Exercise left to the reader: explicit the tree representation.


> #2 from http://www.dreamsongs.com/10ideas.html
> (defun leaves (tree)
>   (cond ((atom tree) (list tree))
>         (t (append (leaves (car tree))
>                    (leaves (cdr tree))))))
>
> (leaves bin-tree) = (4 2 1 3 nil 6 5 7 nil nil)
> gotta love the nils


There is some other implied tree representation at work here.
Exercise left to the reader: explicit this other tree representation.


> ...Finally here is my view of what the fringe implementation should
> be:
> (defun left-child (node)
>   (cond ((or (atom node) (null node)) nil)
>         ((cadr node))))
>
> (defun right-child (node)
>   (cond ((or (atom node) (null node)) nil)
>         ((caddr node))))
>
> (defun is-leaf (node)
>   (or (not (left-child node))
>       (not (right-child node))))

That's good, you're defining a tree represention.  It would be nicer
if you gave the corresponding make-tree-node and make-tree-leaf constructors.

(defun make-tree-node (label left-subtree right-subtree)
  (list label left-subtree right-subtree))

(defun make-tree-leaf (label) (list label nil nil))


> (defun get-fringe (tree)
>   (cond ((is-leaf tree) (list tree))
>         (t (append (get-fringe (left-child tree))
>                    (get-fringe (right-child tree)))))
>
> (get-fringe bin-tree) = (1 3 5 7)
>
> So what is going on?

(get-fringe (make-tree-node 4 (make-tree-node 2 (make-tree-leaf 1) (make-tree-leaf 3))
                              (make-tree-node 6 (make-tree-leaf 5) (make-tree-leaf 7))))
--> ((1 NIL NIL) (3 NIL NIL) (5 NIL NIL) (7 NIL NIL))

Notice that: (make-tree-leaf 1) --> (1 NIL NIL)
Perhaps you meant something else for a leaf?

;-)


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

This is a signature virus.  Add me to your signature and help me to live.
From: ······@gmail.com
Subject: Re: fringe definition
Date: 
Message-ID: <379afe9e-5966-4900-b605-c4b8b5860dd2@p10g2000prf.googlegroups.com>
On Aug 4, 11:55 am, jrwats <······@gmail.com> wrote:
> So I've seen many people implement functions that return the fringe
> (all the leaves) of a tree.  However, all the implementations I've
> seen iterate through *all* the nodes.  So I either do not have the
> definition of fringe correct, or LISPers have a different defintion or
> something else - I don't know what.  In my view here is a binary tree
> with 4 as the root node, 2 as it's left child, 6 as it's right and so
> on:
>
> (setf bin-tree '(4 (2 1 3) (6 5 7)))
>
> Thus in my view the only fringe nodes (leaves) are 1, 3, 5, and 7.

You are correct.

The reason you see lispers define otherwise is because lisp's cons
business really screwed up its lists.

For a detailed explanation:

Fundamental Problems of Lisp
http://xahlee.org/UnixResource_dir/writ/lisp_problems.html

Trees and Indexes
http://xahlee.org/tree/a-trees_indexes.html
(10 years old article)

For several more articles about trees, see:
http://xahlee.org/tree/tree.html
however, most of these are 10 years old and not maintained.

I see some lisp regulars here have tried to give you answers. In
general, they'll tell you how you misunderstood tree, or how you
should understand data structure, etc. Basically, any of their general
remarks about trees are garbage. Trust me. I'm a tree expert.

  Xah
∑ http://xahlee.org/

☄
From: Tim Bradshaw
Subject: Re: fringe definition
Date: 
Message-ID: <75f9371e-3568-4f94-924a-5b5bb068c6c1@k13g2000hse.googlegroups.com>
On Aug 5, 4:38 pm, ·······@gmail.com" <······@gmail.com> wrote:

> Fundamental Problems of Lisphttp://xahlee.org/UnixResource_dir/writ/lisp_problems.html

What Xah means is "Lisp doesn't actually have lists: it has conses and
a little bit of syntax which makes certain kinds of trees of conses
print and read prettily.

Somehow this upsets him deeply: I guess if it had been called CONSP
rather than LISP this would have all been OK.
From: ······@gmail.com
Subject: Re: fringe definition
Date: 
Message-ID: <cdda0770-92dd-4d6b-a2c3-f44b8454af08@j7g2000prm.googlegroups.com>
On Aug 5, 9:29 am, Tim Bradshaw <··········@tfeb.org> wrote:
> On Aug 5, 4:38 pm, ·······@gmail.com" <······@gmail.com> wrote:
>
> > Fundamental Problems of Lisp http://xahlee.org/UnixResource_dir/writ/lisp_problems.html
>
> WhatXahmeans is "Lisp doesn't actually have lists: it has conses and
> a little bit of syntax which makes certain kinds of trees of conses
> print and read prettily.
>
> Somehow this upsets him deeply: I guess if it had been called CONSP
> rather than LISP this would have all been OK.

It's not a naming problem.

The lisp's cons is a fundamental problem in the language today.

http://xahlee.org/UnixResource_dir/writ/lisp_problems.html

“Lisp's cons is perhaps the greatest fuck up in the history of
computer languages.” —Xah Lee

-----------------------------------

Now, a little speculation.

We might wonder, why lisp has the cons problem and was never
addressed?

I guess at the time, 1960s, the very fact that you could have a
concept like a list in a lang and manipulate it as a unit, is
extremely advaced at the time. The list, being built up by hardware
cons, is just something that has to be done.

having data as a single manipulatable object (list) didn't really
become popular until the 1990s. (notably by Perl, and others) And
today, it is THE most important feature of highlevel languages (perl,
python, php, javascript... of the ones i know of).

the lisp's cons, as a underlying primitive that builds lists, even
though a bit cumbersome, but works just fine when list structure are
simple. Even today, with all the perl, python, php, javascript etc
langs that deal with lists, vast majority of list usage is just simple
flat list, sometimes 2 level of nesting (list of list, list of hash,
hash of list). 3 levels of listing is seldomly used unless it's
dealing with 3d matrices.  Greater than 3 level is almost never seen.
Systematic manipulation and exploitation of nested list, such as
mapping to leafs, to particular level, transposition by permutation on
level, etc is hardly even to be seen. (except Mathematica, APL)

So, in general, when you just deal with simple lists, the deficiency
in lisp's doesn't really suface.

-----------------

Today, with lisp manipulation ubiquitous. The lisp's cons business
becomes more apparent and painful.

  Xah
∑ http://xahlee.org/

☄
From: Tim Bradshaw
Subject: Re: fringe definition
Date: 
Message-ID: <f431f371-6113-4062-89cb-675f3264a546@w7g2000hsa.googlegroups.com>
On Aug 6, 7:01 pm, ·······@gmail.com" <······@gmail.com> wrote:

> “Lisp's cons is perhaps the greatest fuck up in the history of
> computer languages.” —Xah Lee

Really the question we need the answer to here: if we bate you some
more, will you burst?  Because obviously, if you will, it will be
worth it, but otherwise it's just yet another tedious waste of time.
From: ······@gmail.com
Subject: Re: fringe definition
Date: 
Message-ID: <c6cb8683-110a-4e4e-9752-94477ea6bb64@a3g2000prm.googlegroups.com>
On Aug 7, 8:13 am, Tim Bradshaw <··········@tfeb.org> wrote:
> On Aug 6, 7:01 pm, ·······@gmail.com" <······@gmail.com> wrote:
>
> > “Lisp's cons is perhaps the greatest fuck up in the history of
> > computer languages.” —Xah Lee
>
> Really the question we need the answer to here: if we bate you some
> more, will you burst?  Because obviously, if you will, it will be
> worth it, but otherwise it's just yet another tedious waste of time.

burst? as in starting to swear? or making a ridiculously exaggerated
claim?

Recently i kinda started a conversational styled posting manner. There
are good and bad points... but anyway i don't feel comfy in reply to
one liners or myself being on-liners...

Write more Tim, with more thoughts please. So we can avoid on-liner
slipslop exchanges.

  Xah
∑ http://xahlee.org/

☄
From: Don Geddis
Subject: Re: fringe definition
Date: 
Message-ID: <87iqufpfxw.fsf@geddis.org>
·······@gmail.com" <······@gmail.com> wrote on Tue, 5 Aug 2008 :
> For several more articles about trees, see:
[...]
> Trust me. I'm a tree expert.

I've got some Monterey Pines in my backyard, but I hear that they require
a lot of water.  Do you think my landscaping would be more drought-resistant
if I planted Stone Pines instead?

        -- Don

(Everybody else on c.l.l: yes, yes, I know.  Why respond at all?  I think I
have a sickness.  I just can't resist sometimes.  Much apologies to the
community.  I'm working on my problem.  Just ignore, just ignore, just
ignore...)
_______________________________________________________________________________
Don Geddis                  http://don.geddis.org/               ···@geddis.org
"The prince wants your daughter for his wife."
"Well, tell him his wife can't have her."  -- Blackadder III
From: Tamas K Papp
Subject: Re: fringe definition
Date: 
Message-ID: <6frgelFd089oU1@mid.individual.net>
On Tue, 05 Aug 2008 09:47:07 -0700, Don Geddis wrote:

> (Everybody else on c.l.l: yes, yes, I know.  Why respond at all?  I
> think I have a sickness.  I just can't resist sometimes.  Much apologies
> to the community.  I'm working on my problem.  Just ignore, just ignore,
> just ignore...)

I don't mind if someone occasionally quotes 1-3 lines from the guy for  
amusement :-)  I don't see his rants otherwise, which is a relief.

Tamas
From: George Neuner
Subject: Re: fringe definition
Date: 
Message-ID: <telk94l2t4kpv723mgmanq0btlpbmem6kv@4ax.com>
On Mon, 4 Aug 2008 11:55:53 -0700 (PDT), jrwats <······@gmail.com>
wrote:

>So I've seen many people implement functions that return the fringe
>(all the leaves) of a tree.  However, all the implementations I've
>seen iterate through *all* the nodes.  So I either do not have the
>definition of fringe correct, or LISPers have a different defintion or
>something else - I don't know what.  In my view here is a binary tree
>with 4 as the root node, 2 as it's left child, 6 as it's right and so
>on:
>
>(setf bin-tree '(4 (2 1 3) (6 5 7)))
>
>Thus in my view the only fringe nodes (leaves) are 1, 3, 5, and 7.
>:
>So what is going on?

What you have is not a binary tree, but a nested list built from
Lisp's cons cells.  Conses have only 2 fields and so they cannot hold
key data and 2 child pointers necessary to create a proper binary
tree.  You can create  more appropriate tree nodes using structures or
CLOS objects or even vectors.

If you want to stay with conses, you can approximate a binary tree by
storing key data in the car and a (single) downward link to children
in the CDR using a nil to signify no children ... something like as
follows:

(4 . ((2 . ((1 . ()) . (3 . ()))) . (6 . ((5 . ()) . (7 . ())))))

                       4 . *
                           |
                         * . *
                        /     \
                      2. *   6 . * 
                        /         \
                     * . *       * . *
                    /    |       |    \
                   /     |       |     \
                1 . -  3 . -   5 . -  7 . -

It's fairly simple to build and use such a tree programmatically, but
it is somewhat convoluted to enter data manually.

George
From: John Thingstad
Subject: Re: fringe definition
Date: 
Message-ID: <op.ufhxiqyxut4oq5@pandora.alfanett.no>
P� Thu, 07 Aug 2008 04:16:32 +0200, skrev George Neuner  
<········@comcast.net>:

>
> It's fairly simple to build and use such a tree programmatically, but
> it is somewhat convoluted to enter data manually.
>
> George


Not really you just use (defstruct (bintree (:type list))...

--------------
John Thingstad