[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.lisp

Beginner question on type-error

Anoop GR

10/13/2015 3:10:00 PM

I am writing a treewith 3 children and then writing a copy function for it

(defstruct trt
elt
(left nil)
(middle nil)
(right nil))

(setf trt1 (make-trt :elt 3 :left 2))

(defun copy-trt (trt0)
(cond (trt0
(make-trt :elt (trt-elt trt0)
:left (copy-trt (trt-left trt0))
:middle (copy-trt (trt-middle trt0))
:right (copy-trt (trt-right trt0))))))

(copy-trt trt1)



;;trace

; No value----Enter COPY-TRT
| Arg-1 = #S(TRT :ELT 3 :LEFT 2 :MIDDLE NIL :RIGHT NIL)
| ----Enter COPY-TRT
| | Arg-1 = 2

;;error:
The value 2 is not of type TRT.
[Condition of type TYPE-ERROR]

doubt:
Is it possible to correct the above copy function w/o using 'return-from' function?
How can I add integers and nil to be true for (trt-p *) predicate ?
8 Answers

Antsan

10/13/2015 4:12:00 PM

0

Am Dienstag, 13. Oktober 2015 17:10:29 UTC+2 schrieb Anoop GR:
> I am writing a treewith 3 children and then writing a copy function for it
>
> (defstruct trt
> elt
> (left nil)
> (middle nil)
> (right nil))
>
> (setf trt1 (make-trt :elt 3 :left 2))
>
> (defun copy-trt (trt0)
> (cond (trt0
> (make-trt :elt (trt-elt trt0)
> :left (copy-trt (trt-left trt0))
> :middle (copy-trt (trt-middle trt0))
> :right (copy-trt (trt-right trt0))))))
>
> (copy-trt trt1)
>
>
>
> ;;trace
>
> ; No value----Enter COPY-TRT
> | Arg-1 = #S(TRT :ELT 3 :LEFT 2 :MIDDLE NIL :RIGHT NIL)
> | ----Enter COPY-TRT
> | | Arg-1 = 2
>
> ;;error:
> The value 2 is not of type TRT.
> [Condition of type TYPE-ERROR]
>
> doubt:
> Is it possible to correct the above copy function w/o using 'return-from' function?
> How can I add integers and nil to be true for (trt-p *) predicate ?

You're going about this the wrong way. How would you even call COPY-TRT on 2?
First off, you need to correct your tree.
It would actually be
(setf trt
(make-trt :elt 3
:left (make-trt :elt 2)))
Then the copy-trt would work as expected for that subtree, but not for the other
ones, as NIL also is not of type TRT.
So, when copying you should only copy the subtree if it isn't NIL. Otherwise you
just insert NIL again.

Barry Margolin

10/13/2015 4:16:00 PM

0

In article <642ec453-fdf4-4481-af3e-e8aa6884b50e@googlegroups.com>,
Anoop GR <anoopemacs@gmail.com> wrote:

> I am writing a treewith 3 children and then writing a copy function for it
>
> (defstruct trt
> elt
> (left nil)
> (middle nil)
> (right nil))
>
> (setf trt1 (make-trt :elt 3 :left 2))
>
> (defun copy-trt (trt0)
> (cond (trt0
> (make-trt :elt (trt-elt trt0)
> :left (copy-trt (trt-left trt0))
> :middle (copy-trt (trt-middle trt0))
> :right (copy-trt (trt-right trt0))))))
>
> (copy-trt trt1)
>
>
>
> ;;trace
>
> ; No value----Enter COPY-TRT
> | Arg-1 = #S(TRT :ELT 3 :LEFT 2 :MIDDLE NIL :RIGHT NIL)
> | ----Enter COPY-TRT
> | | Arg-1 = 2
>
> ;;error:
> The value 2 is not of type TRT.
> [Condition of type TYPE-ERROR]
>
> doubt:
> Is it possible to correct the above copy function w/o using 'return-from'
> function?
> How can I add integers and nil to be true for (trt-p *) predicate ?

Why are you putting non-trees in the children in the first place? If
it's supposed to be a leaf, you should use a tree with just an ELT, but
no LEFT/MIDDLE/RIGHT.

But you could simply check in COPY-TRT to see if the tree is a TRT:

(defun copy-trt (trt0)
(if (trt-p trt0)
(make-trt :elt (trt-elt trt0)
:left (copy-trt (trt-left trt0))
:middle (copy-trt (trt-middle trt0))
:right (copy-0trt (trt-right trt0)))
trt0))

--
Barry Margolin, barmar@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***

Kaz Kylheku

10/13/2015 4:32:00 PM

0

On 2015-10-13, Anoop GR <anoopemacs@gmail.com> wrote:
> I am writing a treewith 3 children and then writing a copy function for it
>
> (defstruct trt
> elt
> (left nil)
> (middle nil)
> (right nil))
>
> (setf trt1 (make-trt :elt 3 :left 2))
>
> (defun copy-trt (trt0)
> (cond (trt0
> (make-trt :elt (trt-elt trt0)
> :left (copy-trt (trt-left trt0))
> :middle (copy-trt (trt-middle trt0))
> :right (copy-trt (trt-right trt0))))))

[ snip ]

> Is it possible to correct the above copy function w/o using 'return-from' function?

Of course; just add cases to your conditional.

(cond
((or (null trt0) (integerp trt0)) trt0)
((typep trt0 'trt) ... recursive copy ...)
(t (error ...)))

The above can also be expressed with typecase:

(typecase tp0
((or null integer) tp0)
(trt ... recursive copy ...)
(t (error ...)))

> How can I add integers and nil to be true for (trt-p *) predicate ?

Just replace the function.

(defun trt-p (obj)
(typep obj '(or null trt integer)))

Also, you can suppress the generation of the original trt-p function using the
(:predicate nil) option in defstruct.

I don't think that it's necessary to have trt-p come out true for an integer.

Analogy: we can do (car nil), yet (consp nil) is false; we don't actually need
nil to be considered a cons in order to give meaning to (car nil).

Anoop GR

10/13/2015 4:47:00 PM

0

Thank you Antsan and Barry,
code fixed: yeah!

(defun copy-trt (trt0)
(cond ((trt-p trt0)
(make-trt :elt (trt-elt trt0)
:left (if (null (trt-left trt0))
nil
(copy-trt (trt-left trt0)))
:middle (if (null (trt-middle trt0))
nil
(copy-trt (trt-middle trt0)))
:left (if (null (trt-right trt0))
nil
(copy-trt (trt-right trt0)))))))

Kaz, thank you for the analogy and predicate suppression keyword

Pascal J. Bourguignon

10/13/2015 5:58:00 PM

0

Anoop GR <anoopemacs@gmail.com> writes:

> Thank you Antsan and Barry,
> code fixed: yeah!
>
> (defun copy-trt (trt0)
> (cond ((trt-p trt0)
> (make-trt :elt (trt-elt trt0)
> :left (if (null (trt-left trt0))
> nil
> (copy-trt (trt-left trt0)))
> :middle (if (null (trt-middle trt0))
> nil
> (copy-trt (trt-middle trt0)))
> :left (if (null (trt-right trt0))
> nil
> (copy-trt (trt-right trt0)))))))
>
> Kaz, thank you for the analogy and predicate suppression keyword

The tests for null children are redundant. You already tested for trt-p
in copy-trt and if you call it with nil, then you get nil, so there's no
need to test it before calling copy-trt!

(defun copy-trt (tree)
(cond ((trt-p tree)
(make-trt :elt (trt-elt tree)
:left (copy-trt (trt-left tree))
:middle (copy-trt (trt-middle tree))
:left (copy-trt (trt-right tree))))))

Now what this means is that the type of copy-trt is:

(function (t) (or null trt))

You are accepting the type (or null trt) for children.


Coming back from your original data structure, if you have non (or null
trt) object as children (eg. for the leaves), then you only need to say
it, to say that the type of children is
(or null trt (not (or (null trt))))
this is T, but it leads you to a copy-trt that will handle those non trt
or null children too:


(defun copy-trt (tree)
(cond ((trt-p tree)
(make-trt :elt (trt-elt tree)
:left (copy-trt (trt-left tree))
:middle (copy-trt (trt-middle tree))
:left (copy-trt (trt-right tree))))
(t tree)))

This function has type:

(function (t) t)

it can "copy" anything.

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.� -- Carl Bass CEO Autodesk

Kaz Kylheku

10/13/2015 6:06:00 PM

0

On 2015-10-13, Anoop GR <anoopemacs@gmail.com> wrote:
> Thank you Antsan and Barry,
> code fixed: yeah!
>
> (defun copy-trt (trt0)
> (cond ((trt-p trt0)
> (make-trt :elt (trt-elt trt0)
> :left (if (null (trt-left trt0))
> nil
> (copy-trt (trt-left trt0)))
> :middle (if (null (trt-middle trt0))
> nil
> (copy-trt (trt-middle trt0)))
> :left (if (null (trt-right trt0))
> nil
> (copy-trt (trt-right trt0)))))))

> Kaz, thank you for the analogy and predicate suppression keyword

I gave you more than an analogy. Unfortunately, I thought I was being
clear enough so I left some code unwritten: ... recursion ...

Above you're not handling all the cases. If an integer is considered
a trt, it should be copied: i.e. (copy-trt 42) -> 42.

Moreover, you have no error checking. We can invoke (copy-trt "abc")
and it just returns nil.

Your code is silly because you pushed various checks into the sites
where the recursion is invoked, thereby replicating the checks
three times. And they are completely redundant:

Look:

:middle (if (null (trt-middle trt0) nil) (copy-trt ...)))


If (trt-middle trt0) is nil, then (copy-trt (trt-middle tr0)) already does the
right thing: it returns nil! So the check can be removed, leaving:

:middle (copy-trt (trt-middle trt0))

there is no difference. And it is wrong.

You should write down the recursive *definition* of a TRT and then write the
code accordingly. Example:

"A TRT is defined as either:
-- a structure of three elements (left, middle and right), each of
which is a TRT;
-- an integer;
-- or the symbol nil.

Furthermore, cycles in the TRT structure are not permitted; it is a DAG."

So, how do we deep copy the sucker, assuming the graph has no cycles?
This pops out of the definition:

(defun copy-trt (obj)
(typecase obj
(trt (make-trt :left (copy-trt (trt-left obj))
:middle (copy-trt (trt-middle obj))
:right (copy-trt (trt-right obj))))
((or integer null) obj)
(otherwise (error "copy-trt: ~s is not a trt"))))

That's it! Handle the three cases, plus error.

The integer and nil cases fold into one, because integers and nil are immutable
objects; we copy them just by returning them. (or integer null) is a Common Lisp
type expression denoting the union of the types integer and the null type
whose instance is the nil object.




--
Music DIY Mailing List: http://www.kylhe...
ADA MP-1 Mailing List: http://www.kylhe...

taruss

10/13/2015 6:09:00 PM

0

On Tuesday, October 13, 2015 at 9:46:42 AM UTC-7, Anoop GR wrote:
> Thank you Antsan and Barry,
> code fixed: yeah!
>
> (defun copy-trt (trt0)
> (cond ((trt-p trt0)
> (make-trt :elt (trt-elt trt0)
> :left (if (null (trt-left trt0))
> nil
> (copy-trt (trt-left trt0)))
> :middle (if (null (trt-middle trt0))
> nil
> (copy-trt (trt-middle trt0)))
> :left (if (null (trt-right trt0))
> nil
> (copy-trt (trt-right trt0)))))))
>
> Kaz, thank you for the analogy and predicate suppression keyword

Just a couple of style notes on this function.
(1) Instead of (IF (NULL (F ...)) NIL ...) it is often clearer to write
(WHEN (F ...) ...) without the NULL predicate if you will just return
NIL when the predicate is false.
(2) A COND (or IF statement, for that matter) with only one clause is also
better replaced by a WHEN or UNLESS form. That gives a more stream-lined
result:

(defun copy-trt (trt0)
(when (trt-p trt0)
(make-trt :elt (trt-elt trt0)
:left (when (trt-left trt0)
(copy-trt (trt-left trt0)))
:middle (when (trt-middle trt0)
(copy-trt (trt-middle trt0)))
:left (when (trt-right trt0)
(copy-trt (trt-right trt0))))))


(3) Although not as robust, since the COPY-TRT form returns NIL if given NIL
as its input, you could remove the test for copying the children. But as
noted, that will make the function less robust for future changes.

taruss

10/13/2015 6:21:00 PM

0

On Tuesday, October 13, 2015 at 8:10:29 AM UTC-7, Anoop GR wrote:
> I am writing a treewith 3 children and then writing a copy function for it
>
> (defstruct trt
> elt
> (left nil)
> (middle nil)
> (right nil))
>
> (setf trt1 (make-trt :elt 3 :left 2))
>
> (defun copy-trt (trt0)
> (cond (trt0
> (make-trt :elt (trt-elt trt0)
> :left (copy-trt (trt-left trt0))
> :middle (copy-trt (trt-middle trt0))
> :right (copy-trt (trt-right trt0))))))
>
> (copy-trt trt1)
>
>
>
> ;;trace
>
> ; No value----Enter COPY-TRT
> | Arg-1 = #S(TRT :ELT 3 :LEFT 2 :MIDDLE NIL :RIGHT NIL)
> | ----Enter COPY-TRT
> | | Arg-1 = 2
>
> ;;error:
> The value 2 is not of type TRT.
> [Condition of type TYPE-ERROR]
>
> doubt:
> How can I add integers and nil to be true for (trt-p *) predicate ?

And to clean up this question.

The problem that is causing the error is when you end up calling TRT-ELT on the
integer 2, which should clearly be an error.

Even if you modify the TRT-P predicate to accept integers and nil, you will
still run into an error if you try to call TRT-ELT (or TRT-LEFT, etc.) on NIL
or an integer. So the problem isn't with the type predicate, but rather with
the structure of your tree. But others have already pointed out the fix for
that.