hi,everyone, I am a newbies in lisp, and have a basic question.
I have two procedures, which I use to convert a binary tree to a
list. The tree is formatted like this
'( entry (left-branch) (right-branch))
This two functions like this:
(defun tree->list-1 (tree)
(if (not tree) '()
(append (tree->list-1 (left-branch tree))
(cons (entry tree)
(tree->list-1 (right-branch tree))))))
-----------------------------------------------
(defun tree->list-2 (tree)
(defun copy-to-list (tree result-list)
(if (not tree) result-list
(copy-to-list (left-branch tree)
(cons (entry tree)
(copy-to-list (right-branch
tree)
result-list)))))
(copy-to-list tree '()))
they both work well, but I have a question here, do the two
procedures have the same order of growth in the number of steps
required to convert a balanced tree with n elements to a list ? I
guess they do not, but can not explain why. Anyone do me a favor?
Thanks.
··········@gmail.com" <·········@gmail.com> writes:
> hi,everyone, I am a newbies in lisp, and have a basic question.
> I have two procedures, which I use to convert a binary tree to a
> list. The tree is formatted like this
> '( entry (left-branch) (right-branch))
> This two functions like this:
> (defun tree->list-1 (tree)
> (if (not tree) '()
> (append (tree->list-1 (left-branch tree))
> (cons (entry tree)
> (tree->list-1 (right-branch tree))))))
> -----------------------------------------------
> (defun tree->list-2 (tree)
> (defun copy-to-list (tree result-list)
> (if (not tree) result-list
> (copy-to-list (left-branch tree)
> (cons (entry tree)
> (copy-to-list (right-branch
> tree)
> result-list)))))
> (copy-to-list tree '()))
> they both work well, but I have a question here, do the two
> procedures have the same order of growth in the number of steps
> required to convert a balanced tree with n elements to a list ? I
> guess they do not, but can not explain why. Anyone do me a favor?
> Thanks.
APPEND calls CONS O(n) times.
If you call APPEND O(n) times, then CONS will be called O(n�) times.
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
May the iterative procedure and the recursive procedure are at the
same efficiency. They only differ at the using of CONS or APPEND, and
APPEND calls CONS, so the first would be less effective.
On Jun 22, 5:11 am, ··········@gmail.com" <·········@gmail.com> wrote:
> hi,everyone, I am a newbies in lisp, and have a basic question.
> I have two procedures, which I use to convert a binary tree to a
> list. The tree is formatted like this
> '( entry (left-branch) (right-branch))
> This two functions like this:
> (defun tree->list-1 (tree)
> (if (not tree) '()
> (append (tree->list-1 (left-branch tree))
> (cons (entry tree)
> (tree->list-1 (right-branch tree))))))
> -----------------------------------------------
> (defun tree->list-2 (tree)
> (defun copy-to-list (tree result-list)
> (if (not tree) result-list
> (copy-to-list (left-branch tree)
> (cons (entry tree)
> (copy-to-list (right-branch
> tree)
> result-list)))))
> (copy-to-list tree '()))
> they both work well, but I have a question here, do the two
> procedures have the same order of growth in the number of steps
> required to convert a balanced tree with n elements to a list ? I
> guess they do not, but can not explain why. Anyone do me a favor?
> Thanks.
If you want to stray from a functional path than push & nreverse are
common idiom, though iterative
solution is even bettrr for efficiency.
And you don't have to quote nil
(if (not tree) '()
nil <=> () evaluates to itself.
Slobodan Blazeski
fireblade <·················@gmail.com> writes:
> And you don't have to quote nil
> (if (not tree) '()
> nil <=> () evaluates to itself.
You don't have to, but it's much better to quote it sometimes!
() empty list in source code
'() empty list as data
nil boolean false
'nil symbol named "NIL"
For example, one would write:
(defun f ()
(if (xor *x* NIL)
'() ; return an empty list
(symbol-package 'NIL)))
instead of:
(defun f NIL
(if (xor *x* ())
'NIL ; return an empty list
(symbol-package '())))
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
On Jun 22, 10:21 am, Pascal Bourguignon <····@informatimago.com>
wrote:
> fireblade <·················@gmail.com> writes:
> > And you don't have to quote nil
> > (if (not tree) '()
> > nil <=> () evaluates to itself.
>
> You don't have to, but it's much better to quote it sometimes!
>
> () empty list in source code
> '() empty list as data
> nil boolean false
> 'nil symbol named "NIL"
>
> For example, one would write:
>
> (defun f ()
> (if (xor *x* NIL)
> '() ; return an empty list
> (symbol-package 'NIL)))
>
> instead of:
>
> (defun f NIL
> (if (xor *x* ())
> 'NIL ; return an empty list
> (symbol-package '())))
>
> --
> __Pascal Bourguignon__ http://www.informatimago.com/
>
> NOTE: The most fundamental particles in this product are held
> together by a "gluing" force about which little is currently known
> and whose adhesive power can therefore not be permanently
> guaranteed.
If it helps you read the source code better do it.
Slobodan Blazeski
In article <························@z28g2000prd.googlegroups.com>,
··········@gmail.com" <·········@gmail.com> wrote:
> hi,everyone, I am a newbies in lisp, and have a basic question.
> I have two procedures, which I use to convert a binary tree to a
> list. The tree is formatted like this
> '( entry (left-branch) (right-branch))
> This two functions like this:
> (defun tree->list-1 (tree)
> (if (not tree) '()
> (append (tree->list-1 (left-branch tree))
> (cons (entry tree)
> (tree->list-1 (right-branch tree))))))
> -----------------------------------------------
> (defun tree->list-2 (tree)
> (defun copy-to-list (tree result-list)
> (if (not tree) result-list
> (copy-to-list (left-branch tree)
> (cons (entry tree)
> (copy-to-list (right-branch
> tree)
> result-list)))))
> (copy-to-list tree '()))
> they both work well,
Note that DEFUN is usually not used like this.
DEFUN does not give you local functions. It defines
global functions. For local functions you
need either FLET or LABELS.
I your example you need LABELS.
(defun tree->list-2 (tree)
(labels ((copy-to-list (tree result-list)
(if (not tree)
result-list
(copy-to-list (left-branch tree)
(cons (entry tree)
(copy-to-list (right-branch tree)
result-list))))))
(copy-to-list tree '())))
> but I have a question here, do the two
> procedures have the same order of growth in the number of steps
> required to convert a balanced tree with n elements to a list ? I
> guess they do not, but can not explain why. Anyone do me a favor?
> Thanks.
--
http://lispm.dyndns.org