time for updating records (was Re: A simple doubt about // operator)

[Hal Daume III]

Hi Andrew,

I'd never actually thought of that, but it's somewhat less of an issue
since records/data types tend to have only a small number of elements,
whereas arrays tend to have a large number of elements.

One thing, though, for data types (and hence records) which just occurred
to me is that it seems that it really should be logarithmic in the number
of fields, if the compiler/programmer needed it.  For instance, one could
transform:

> data Foo a b c d = Foo a b c d

into

> data Foo  a b c d = Foo1 (Foo2 a b) (Foo2 c d)
> data Foo2 a b     = Foo2 a b

This would make updates happen in logarithmic time, but reads would now
take also log time, instead of constant time (I assume reads take constant
time, though I haven't verified it).

Obviously one could and should be smarter about doing this...if the
program this datatype is used in tends to modify a and c simultaneously,
then these should be put together.

Anyway, I assume no one does this, probably because it would slow down
reads...but I wonder whether one could detect that a datatype is modified
frequently and, if so, transform it into this...I also wonder if it would
really matter -- the constant terms would be higher, so you'd really have
to have a large datatype to notice the difference, I'd imagine...

 - Hal

--
 Hal Daume III                                   | hdaume at isi.edu
 "Arrest this man, he talks in maths."           | www.isi.edu/~hdaume

On Sun, 2 Nov 2003 ajb at spamcop.net wrote:

> G'day all.
> 
> Quoting Hal Daume III <hdaume at ISI.EDU>:
> 
> > In general, I think the name "array" for these data structures is a bit
> > misleading, since nearly everyone expects an array to have constant time
> > read and update, while these only have constant time read.
> 
> It's no worse than "record" in this respect.  Wouldn't everyone expect a
> field update to be constant time, not linear in the number of fields?
> 
> Cheers,
> Andrew Bromage
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
>