Re: Growable arrays?

[Stefan Israelsson Tampe <stefan.itampe@gmail.com>]

[-- Attachment #1.1: Type: text/plain, Size: 2752 bytes --]

Maybe this could be a first stub for a table structure that is uses both an
array and a hash-table. I do think that implementing this might need fine
tuning in order
to have good defaults and so on. So in that sense one probably need to
check out reference
implementations. But this is for discussion!

I Assumed growing here and have no shrinking!

I made it nonfunctional.

One note to the discussion. It is not just to combine a growable vector
with a growable hash
in ordder to have a one tool for all cases. The reason is that one need to
tackle the issue with sparse tables with integer keys. I tried to add that
feature as well in some way.

Anyway it shows that you don't need a ton of code to get something pretty
functional.


On Mon, Jun 11, 2012 at 4:19 PM, David Kastrup <dak@gnu.org> wrote:

> Daniel Hartwig <mandyke@gmail.com> writes:
>
> > On 11 June 2012 20:20, David Kastrup <dak@gnu.org> wrote:
> >>> P.S.: I still need to look at vlists.  They might already address this
> >>>       issue, though I can't use them in Guile 1.8.
> >>
> >> No, the "immutable" angle would make them unsuitable again.
> >
> > Note that vlists are only immutable in the sense that you can not
> > modify the value of a slot already allocated.
>
> Which makes it useless here.
>
> >> Scheme/Guile vectors are fixed size.  Now I have a situation where I
> >> have a basic type lattice with records stored in vectors, and this type
> >> lattice may be extended dynamically (which typically happens at the
> >> start of a whole file, for potentially multi-file runs).
> >
> > From this I gather that your use case only appends to the lattice, if
> > so, vlist is suitable for that task.
>
> Wrong.  My use case only _allocates_ at the end of the existing type
> lattice, but the records are not read-only.
>
> >> Cough, cough.  Standard vectors are not growable.  Which is the
> >> original problem of this thread, never mind Lua.
> >
> > True, but a growable vector is a tiny step away from the standard
> > vector.
>
> A tiny step if you are modifying the C code.  A not so tiny step if you
> are working with Scheme.
>
> >> hashtables have additional indirection
> >> through hash buckets and coalescing lists
> >
> > This is fairly standard for a hash table.  I would be quite surprised
> > if the hash table part of a Lua table did not also use buckets.
>
> But it is not standard for a growable vector that it only comes with
> buckets and chains.
>
> >> Except that this one isn't.
> >
> > Why not?
> >
> > You take a vector and a hash table, store your values in them, and
> > grow either as needed.  This is not a complicated type.
>
> Except that vectors don't grow.  Are you even reading what you are
> replying to?
>
> --
> David Kastrup
>
>
>

[-- Attachment #1.2: Type: text/html, Size: 3631 bytes --]

[-- Attachment #2: hasharray.scm --]
[-- Type: application/octet-stream, Size: 1549 bytes --]

(use-modules (srfi srfi-11))

(define (make-table)
  (list 10 (make-vector 10 #f) (make-hash-table)))

(define table-ref 
  (case-lambda
    ((tb x) (table-ref tb x #f))
    ((tb x fail)
     (if (integer? x)
         (let ((r (vector-ref (cadr tb) (modulo x (car tb)))))
           (if r
               (if (= (car r) x) 
                   (cdr r)
                   fail)
               fail))
         (hash-ref (caddr tb) x fail)))))

(define (make-larger vec n)
  (let loop ((n2 (* n 2)))
    (let ((vec2  (make-vector n2 #f)))
      (let loop2 ((i 0))
        (if (< i n)
            (let ((r (vector-ref vec i)))
              (if r
                  (let ((r2 (vector-ref vec2 (modulo (car r) n2))))
                    (if r2 
                        (loop (* 2 n2))
                        (begin
                          (vector-set! vec2 (modulo (car r) n2) r)
                          (loop2 (+ i 1)))))
                  (loop2 (+ i 1))))
            (values vec2 n2))))))

(define (table-set! tb k v)
  (if (integer? k)
      (let ((vec (cadr tb))
            (n   (car  tb)))
        (let ((r (vector-ref vec (modulo k n))))
          (if r
              (if (= (car r) k)
                  (set-cdr! r v)
                  (let-values (((vec2 n2) (make-larger vec n)))
                    (set-car! tb  n2)
                    (set-car! (cdr tb) vec2)
                    (table-set! tb k v)))
              (vector-set! vec (modulo k n) (cons k v)))))
      (hash-set! (caddr tb) k v)))