Hi.
I wondered if anyone out there could help me with a problem conserning the
mergesort algorithm.
(It is to an assignment, but I'm not asking for the correct answers, only
for what I'm doing wrong..)
We are suppose to write a sorting function using mergesort, and I have
written
(defun mergesort (elems &key(key #'identity)(pred #'<))
(cond
((atom elems) elems)
(t (let (len (length elems))
(mergelist (mergesort (subseq elems 0 (truncate (/ len 2))) :key
key :pred pred)
(mergesort (subseq elems (truncate (/ len 2))):key key
:pred pred)
:key key :pred pred)))))
The mergelist function is written this way:
(defun mergesort (elems &key(key #'identity)(pred #'<))
(cond
((atom elems) elems)
(t (let (len (length elems))
(mergelist (mergesort (subseq elems 0 (truncate (/ len 2))) :key
key :pred pred)
(mergesort (subseq elems (truncate (/ len 2))):key key
:pred pred)
:key key :pred pred)))))
The problem is that when I call mergesort something like this:
(mergesort '(3 1 2))
I get the following error message.
Error: EXCL::/_2OP: `NIL' is not of the expected type `NUMBER'
[condition type: TYPE-ERROR]
My question is then, Why?
As far as I can see, the only place where this kind of error could occur is
in the mergelist function when called with to list, where one of them is
empty. This however should never occur since the (atom elems) is supposed to
catch any list that are empty or only has one element.
Hope anyone can help.
Tord A. Fredriksen
First of all, nice first attempt. You still need to work on your indenting
and spacing though :-).
> As far as I can see, the only place where this kind of error could occur
is
> in the mergelist function when called with to list, where one of them is
> empty. This however should never occur since the (atom elems) is supposed
to
> catch any list that are empty or only has one element.
This is the crux of the issue...
Try debugging the form (mergesort '(1)). Then look to see what the two
calls (subseq '(1) 0 0) and
(subseq '(1) 0) - what you're passing into you recursive calls or
mergesort - return. You will see that one of your assumptions listed above
is incorrect.
Another way to see this is to notice that the cond of your recurrence is
strange. In one portion, you're concentrating on the listness of the input
and in another the length. In general, recursions based on more than one
topic are not only hard to understand, but often wrong. The code as written
seems to assume that you are planning to pass as input to the function items
that are not lists as well as items that are. Is this indeed the case?
Think about this carefully. Is a list with one item, e.g., (1), the same
thing AS the item, 1? Might you more reasonably recurse on the length of
the list passed?
faa
"Tord A. Fredriksen" <·······@stud.ntnu.no> wrote in message
·················@kopp.stud.ntnu.no...
> Hi.
> I wondered if anyone out there could help me with a problem conserning the
> mergesort algorithm.
> (It is to an assignment, but I'm not asking for the correct answers, only
> for what I'm doing wrong..)
>
> We are suppose to write a sorting function using mergesort, and I have
> written
> (defun mergesort (elems &key(key #'identity)(pred #'<))
> (cond
> ((atom elems) elems)
> (t (let (len (length elems))
> (mergelist (mergesort (subseq elems 0 (truncate (/ len 2))) :key
> key :pred pred)
> (mergesort (subseq elems (truncate (/ len 2))):key key
> :pred pred)
> :key key :pred pred)))))
>
> The mergelist function is written this way:
> (defun mergesort (elems &key(key #'identity)(pred #'<))
> (cond
> ((atom elems) elems)
> (t (let (len (length elems))
> (mergelist (mergesort (subseq elems 0 (truncate (/ len 2))) :key
> key :pred pred)
> (mergesort (subseq elems (truncate (/ len 2))):key key
> :pred pred)
> :key key :pred pred)))))
> The problem is that when I call mergesort something like this:
> (mergesort '(3 1 2))
> I get the following error message.
> Error: EXCL::/_2OP: `NIL' is not of the expected type `NUMBER'
> [condition type: TYPE-ERROR]
>
> My question is then, Why?
> As far as I can see, the only place where this kind of error could occur
is
> in the mergelist function when called with to list, where one of them is
> empty. This however should never occur since the (atom elems) is supposed
to
> catch any list that are empty or only has one element.
>
> Hope anyone can help.
>
> Tord A. Fredriksen
>
>
"Tord A. Fredriksen" wrote:
> .... This however should never occur since the (atom elems) is supposed to
> catch any list that are empty or only has one element.
The latter is your problem; a list with one element is a list, not an
atom.
(atom '(1) ) --> NIL.
You could try
(or (atom elems) (atom (rest elems)))
However, I'd suggest establishing the "len" variable in a local
context that is outside your conditional testing.
Lyman
"Tord A. Fredriksen" wrote:
> (defun mergesort (elems &key(key #'identity)(pred #'<))
> (cond
> ((atom elems) elems)
> (t (let (len (length elems))
> (mergelist (mergesort (subseq elems 0 (truncate (/ len 2))) :key
> key :pred pred)
> (mergesort (subseq elems (truncate (/ len 2))):key key
> :pred pred)
> :key key :pred pred)))))
>
> The mergelist function is written this way:
> (defun mergesort (elems &key(key #'identity)(pred #'<))
> (cond
> ((atom elems) elems)
> (t (let (len (length elems))
> (mergelist (mergesort (subseq elems 0 (truncate (/ len 2))) :key
> key :pred pred)
> (mergesort (subseq elems (truncate (/ len 2))):key key
> :pred pred)
> :key key :pred pred)))))
> The problem is that when I call mergesort something like this:
> (mergesort '(3 1 2))
> I get the following error message.
> Error: EXCL::/_2OP: `NIL' is not of the expected type `NUMBER'
> [condition type: TYPE-ERROR]
While the other replies to this so far seem interesting, I think they
bypassed the actual error you are stumbling on.
- If you haven't found it yet, this EXCL::/_2OP is just Allegro's
2-operator division operation, so your problem is in the (/ len 2) part.
In the let form you are creating a local variable, len, which gets as
its value NIL, and another variable, length, with the value elems. That
was probably not what you intended, so how about adding a few
parentheses?
Try (let ((len (length elems))) ...
--