Various Topics on Lisp

..ss.. ..kol..

Adam Warner <usenet@consulting.net.nz> writes:

> Hi Chris Capel,
>
>> I don't see any function to remove an object based on its index. Is there
>> such a thing for vectors or sequences?
>
> How's this? (untested)
>
> (defun delete-range (adj-vec start &optional end)
> (let ((len-vec (length adj-vec)))
> (unless end (setf end len-vec))
> (loop for start-i from end to (1- len-vec)
> for new-i from start do
> (setf (aref adj-vec new-i) (aref adj-vec start-i)))
> (adjust-array adj-vec (- len-vec (- end start)) :fill-pointer t)))


What's wrong with

(setq v (delete-if #'(lambda (ignored) t) v :start i :count 1))

to destructively delete the i-th element of v, or

(setq v (delete-if #'(lambda (ignored) t) v :start s :end e))

for a range?


---V***il.


--
V***il Nikolov <vnikolov@poboxes.com>

Hollerith's Law of Docstrings: Everything can be summarized in 72 bytes.

.... ..rn..

Hi Chris Capel,

> Although I'm curious--is there a constant time algorithm for this sort of
> thing? /Primae facie/, it seems impossible.

Counterexample: (make-hash-table) using integers as a key.

It's only impossible when you impose constraints upon how arrays may be
implemented. If the adjustable array _must_ be stored as a contiguous
ordinary array then you have no options. If the adjustable array can be
implemented as pointers to contiguous vectors (with say 1MB of elements
each) then you can add a pointer to another contiguous vector at a
constant cost. Lookup is also constant (there's just another level of
indirection). Even if the vector of pointers turned out to be too small
the cost of building a larger pointer of vectors would be low.

Regards,
Adam

.... ..rn..

Hi Peter Seibel,

> And use MAP-INTO to copy the data rather than looping and copying the
> elements yourself; there's at least a chance the implementation will
> have implemented MAP-INTO to use bulk copying primitives where
> possible.

Thanks for the hint Peter!

Regards,
Adam

.... ..rn..

Hi V***il Nikolov,

> Adam Warner <usenet@consulting.net.nz> writes:
>
>> Hi Chris Capel,
>>
>>> I don't see any function to remove an object based on its index. Is there
>>> such a thing for vectors or sequences?
>>
>> How's this? (untested)
>>
>> (defun delete-range (adj-vec start &optional end)
>> (let ((len-vec (length adj-vec)))
>> (unless end (setf end len-vec))
>> (loop for start-i from end to (1- len-vec)
>> for new-i from start do
>> (setf (aref adj-vec new-i) (aref adj-vec start-i)))
>> (adjust-array adj-vec (- len-vec (- end start)) :fill-pointer t)))
>
>
> What's wrong with
>
> (setq v (delete-if #'(lambda (ignored) t) v :start i :count 1))
>
> to destructively delete the i-th element of v, or
>
> (setq v (delete-if #'(lambda (ignored) t) v :start s :end e))
>
> for a range?

Nice idea. It would suck if DELETE-IF turned out to be a synonym for
REMOVE-IF (which is conforming by my reading of the HyperSpec).

Regards,
Adam

.... ..rn..

Hi Chris Capel,

> Although I'm curious--is there a constant time algorithm for this sort of
> thing? /Primae facie/, it seems impossible.

Counterexample: (make-hash-table) using integers as a key.

It's only impossible when you impose constraints upon how arrays may be
implemented. If the adjustable array _must_ be stored as a contiguous
ordinary array then you have no options. If the adjustable array can be
implemented as pointers to contiguous vectors (with say 1MB of elements
each) then you can add a pointer to another contiguous vector at a
constant cost. Lookup is also constant (there's just another level of
indirection). Even if the vector of pointers turned out to be too small
the cost of building a larger vector to hold more pointers would be low.

Regards,
Adam

.... ..meni..

Chris Capel wrote:


> I don't see any function to remove an object based on its index. Is there
> such a thing for vectors or sequences?

(defun delete-ref (sequence position)
(let ((marker (load-time-value (make-symbol "MARKER"))))
(delete marker (progn (setf (elt sequence position) marker)
sequence))))

Wade

..l.. ..a.. ..emita..

Chris Capel <ch.ris@iba.nktech.net> writes:

> I don't see any function to remove an object based on its index.
> Is there such a thing for vectors or sequences?

I think that can be done with DELETE-IF.

(defparameter *a* (vector 'I 'do 'not 'have 'much 'time))
;; => *A*

(delete-if (constantly t) *a* :start 4 :count 1)
;; => #(I DO NOT HAVE TIME)

This is not guaranteed to modify the vector *A*, but in SBCL
0.8.14.9 it apparently does; SB-KERNEL:SHRINK-VECTOR works
even though the vector is not otherwise adjustable.

*a*
;; => #(I DO NOT HAVE TIME)

(array-has-fill-pointer-p *a*)
;; => NIL

(adjustable-array-p *a*)
;; => NIL

.... ..ni..

In article <pan.2004.09.21.04.57.34.726639@consulting.net.nz> , Adam Warner wrote:
> Counterexample: (make-hash-table) using integers as a key.

The hash table must still be coiped once it's full.

> It's only impossible when you impose constraints upon how arrays may be
> implemented. If the adjustable array _must_ be stored as a contiguous
> ordinary array then you have no options. If the adjustable array can be
> implemented as pointers to contiguous vectors (with say 1MB of elements
> each) then you can add a pointer to another contiguous vector at a
> constant cost. Lookup is also constant (there's just another level of
> indirection). Even if the vector of pointers turned out to be too small
> the cost of building a larger vector to hold more pointers would be low.

That's still O(n).

I'm pretty sure that you have to pick between constant time extension and
constant time access, but you can't have both. But I can't think of a
proof right now.

--
Eic Daniel

.... ..rn..

Hi Eric Daniel,

>> It's only impossible when you impose constraints upon how arrays may be
>> implemented. If the adjustable array _must_ be stored as a contiguous
>> ordinary array then you have no options. If the adjustable array can be
>> implemented as pointers to contiguous vectors (with say 1MB of elements
>> each) then you can add a pointer to another contiguous vector at a
>> constant cost. Lookup is also constant (there's just another level of
>> indirection). Even if the vector of pointers turned out to be too small
>> the cost of building a larger vector to hold more pointers would be low.
>
> That's still O(n).
>
> I'm pretty sure that you have to pick between constant time extension and
> constant time access, but you can't have both. But I can't think of a
> proof right now.

With:

(a) A vector that can hold 4096 pointers.
(b) Contiguous vectors holding 1MB elements each.

You can address 4GB elements without even adjusting the size of the vector
of pointers.

To extended the array you add a pointer to a newly allocated contiguous
vector of 1MB elements. This is constant time extension.

To access an element by index you work out how many times the index is
greater than 1MB to get the index into the array of pointers. The
remainder is the index into the relevant contiguous vector. This is
constant time access.

Regards,
Adam

..sc.. ..stan..

Chris Capel wrote:

> OK, now for the big picture. .NET has the idea of "collections"[1], about
> the same as a Lisp sequence, I guess, only it's more consistently used. In
> C#, any collection (really, any IEnumerable, but ICollection implements
> that) can be iterated over using a "foreach". Why can't you do this in
> Lisp? Because the basic types aren't CLOSsy enough. Can you iterate over
> any sequence? It seems to me that list, hashtable, and vector types ought
> to inherit from enumerable-collection, and foreach should be a generic
> method on that. (A hashtable would return a key-value pair for every
> iteration.) MAPCAR and friends should be defined in terms of this generic
> "collection" idea, so they wouldn't be limited to lists. You could still
> get a guaranteed enumeration order, but the order would be a property of
> the type's enumerator. I'm sure there are other ways to make this idea more
> pervasive than it currently seems to be in Lisp.

"Pure" object-oriented single-inheritance languages have to squeeze
everything into cl*** hierarchies. In Lisp, this is not necessary. When
you take a closer look at collection hierarchies, you will notice that
there are unimplemented methods that throw exceptions, etc. So these
hierarchies aren't really hierarchies. Not all methods work on all
cl***es. Therefore, it's ok to have specialized functions that work,
say, only for lists.

The LOOP macro is pretty complete in allowing iteration over the data
structures that Common Lisp provides. Extensible LOOP implementations
allow you to add your own data structures.

> Just to be clear, I'm not advocating changing the language or the standard.
> And I know that a lot of this can be taken care of with the consistent use
> of a few good macros and a cl*** or two. And I know that I could be
> completely wrong. I'm just comparing what I know to what I'm learning. So,
> am I alone in this dim opinion of Lisp collections?

You seem to be a newcomer to Lisp. There's a transition time in which
you expect things to work like they did in other languages. Soon you
will expect things to work like they do in Lisp elsewhere.


Pascal

--
Pascal Costanza University of Bonn
mailto:costanza@web.de Institute of Computer Science III
http://www.pascalcostanza.de Römerstr. 164, D-53117 Bonn (Germany)