Menu
▾
▴
lua-users-stdlib
|
From: Reuben T. <rr...@sc...> - 2004-02-01 19:04:04
|
I have just committed some changes provoked by Jamie Webb's submission of
his std.lua library, which was mostly aimed at core functionality
(manipulation of arrays, sets, tables and functions).
So far I have incorporated all the stuff which matched existing functions.
I've also removed some functions (from my stuff) that didn't look that
useful and made other miscellaneous fixes and improvements that occurred
to me as I read through the code.
I'm left mostly with the functions that don't match anything I have, which
I'll divide into groups: those I have no problems with and will go ahead
and add later, those I don't think are necessary, and those I don't know
what to do with:
The following are fine:
function std.succ(x)
function std.generate(f, start, length)
function std.deep_copy(t) (but what to call it and shallow_copy?)
function std.intersect(a, b) -- I'll reimplement my set module
function std.difference(a, b) -- with these in mind, probably
-- getting rid of my set type
The following look good but I'm not sure how best to handle them:
function std.dump(value, key, fh, depth, pr, done) -- better done
-- by reimplementing my tostring using a visitor and then
-- reusing the visitor for dump
the functionalised operators +, -, .. &c. -- not sure how best to
-- include these, e.g. how to name them, how general they
-- really should be (arity &c.)
The following I plain don't understand:
function std.getter(name) -- what's this for?
function std.method(name, ...) -- what's this for?
function std.bind_method(t, m) -- what's this for?
I'm dubious about the following:
function std.map_tbl(f, t) -- it is really wise to map over a table?
function std.filter_tbl(f, t) -- these should only be used on lists/arrays IMO
function std.conjunction(...) -- this seems a bit specialised;
it's really reverseMap composed
with functionalised "and"
--
http://www.mupsych.org/~rrt/ | perfect, a. unsatirizable
|
|
From: Jamie W. <j...@jm...> - 2004-02-02 02:01:15
|
On Sunday 01 February 2004 19:03, Reuben Thomas wrote:
> the functionalised operators +, -, .. &c. -- not sure how best to
> -- include these, e.g. how to name them, how general they
> -- really should be (arity &c.)
Naming: yeah, dunno. Arity: I decided it made sense only for commutative
operators to be variadic.
> The following I plain don't understand:
>
> function std.getter(name) -- what's this for?
> function std.method(name, ...) -- what's this for?
> function std.bind_method(t, m) -- what's this for?
Say I have a list of objects and I want to get a list of those which have
attribute foo = true:
footrue = std.filter(std.getter("foo"), objects)
Say I want to call method swizzle(5) on each of a list of (maybe polymorphic)
objects:
results = std.map(std.method("swizzle", 5), objects)
bind_method() as I said is just a convenience. It means I can write
std.bind_method(object, "method", ...) rather than std.bind(object.method,
object, ...). It just happens that I had some code where I needed to do that
a lot.
> I'm dubious about the following:
>
> function std.map_tbl(f, t) -- it is really wise to map over a table?
> function std.filter_tbl(f, t) -- these should only be used on
> lists/arrays IMO
Why not? Changing the keys is maybe not such a great idea, but there doesn't
seem to be any reason not to map/filter over the values. Obviously the order
is undefined, but that's just expected from any operation on tables. I don't
really see why one shouldn't map (most likely injections) over sets either.
> function std.conjunction(...) -- this seems a bit specialised;
> it's really reverseMap composed
> with functionalised "and"
Fair enough. I just didn't think of that; I've never come across reverseMap
before. I don't see it in your library though.
-- Jamie Webb
|
|
From: Reuben T. <rr...@sc...> - 2004-02-02 10:29:52
|
> Naming: yeah, dunno. Arity: I decided it made sense only for commutative
> operators to be variadic.
Whereas in e.g. APL they all are, and you get alternating differences with
-. I'm not sure what's worse: providing variadic / (what is that for?) or
not providing it (why doesn't my code work suddenly when I replace + with
/?).
> > The following I plain don't understand:
> >
> > function std.getter(name) -- what's this for?
> > function std.method(name, ...) -- what's this for?
> > function std.bind_method(t, m) -- what's this for?
>
> Say I have a list of objects and I want to get a list of those which have
> attribute foo = true:
>
> footrue = std.filter(std.getter("foo"), objects)
Seems a bit contrived. If you wanted those that had attribute foo < 4,
you'd still need to make a function.
> Say I want to call method swizzle(5) on each of a list of (maybe polymorphic)
> objects:
>
> results = std.map(std.method("swizzle", 5), objects)
And again, that only works with constant values. If you wanted to call
swizzle(self.foo+self.bar), again, you'd need a function.
> > I'm dubious about the following:
> >
> > function std.map_tbl(f, t) -- it is really wise to map over a table?
> > function std.filter_tbl(f, t) -- these should only be used on
> > lists/arrays IMO
>
> Why not? Changing the keys is maybe not such a great idea, but there doesn't
> seem to be any reason not to map/filter over the values. Obviously the order
> is undefined, but that's just expected from any operation on tables. I don't
> really see why one shouldn't map (most likely injections) over sets either.
> Fair enough. I just didn't think of that; I've never come across reverseMap
> before. I don't see it in your library though.
No, I haven't needed it yet!
--
http://www.mupsych.org/~rrt/ | Academics age by degrees
|
|
From: Jamie W. <j...@jm...> - 2004-02-03 22:30:00
|
On Monday 02 February 2004 10:29, Reuben Thomas wrote:
> > Naming: yeah, dunno. Arity: I decided it made sense only for commutative
> > operators to be variadic.
>
> Whereas in e.g. APL they all are, and you get alternating differences with
> -. I'm not sure what's worse: providing variadic / (what is that for?) or
> not providing it (why doesn't my code work suddenly when I replace + with
> /?).
How about:
["/"] = function(a,b,c) assert(c == nil, "/ is binary only") return a/b end
At least you get a meaningful error that way.
> Seems a bit contrived. If you wanted those that had attribute foo < 4,
> you'd still need to make a function.
small = std.filter(std.compose(std.bind(std.op[">"], 4), std.getter("foo")),
objects)
Seriously though, I realise it's not very general, but I have found it useful.
I suppose it just depends on how large you want the library to end up.
> > Say I want to call method swizzle(5) on each of a list of (maybe
> > polymorphic) objects:
> >
> > results = std.map(std.method("swizzle", 5), objects)
>
> And again, that only works with constant values. If you wanted to call
> swizzle(self.foo+self.bar), again, you'd need a function.
method() is to methods what bind() is to functions (bind_method() lies
somewhere in the middle). I don't see how you can claim that one is useful
but not the other. Personally, I use them both about equally, and from my
libary use only map() more frequently.
If I wanted self.foo+self.bar, then yes, I'd probably write a function (or
make a swizzle_foo_bar() method). But in general where the values are not
constant:
results = std.map(std.method("swizzle"), objects, params)
-- Jamie Webb
|
|
From: Reuben T. <rr...@sc...> - 2004-02-04 10:59:00
|
> Seriously though, I realise it's not very general, but I have found it
> useful. I suppose it just depends on how large you want the library to
> end up.
That's a difficult question, of course: we have multiple goals. First, to
reach into and improve the libraries actually shipped with Lua. Secondly,
to add some core programming utils (this is mostly what we've discussed so
far). Thirdly, to add lots of special purpose stuff (like Diego's mbox
parser, which I was eulogising last night).
So far I've not really separated 1 and 2 (in a sense they shouldn't be,
because both are aiming at the goal of providing an improved standard
library that is actually shipped, or at least in our view should be
shipped, with the standard distribution).
However, it's easy to tell the difference between 1+2 and 3 (if you'll
forgive the pun): code for 1 & 2 have mostly been put in modules with the
same names as the existing C libraries, and the rest has gone in special
modules.
I've already removed some of my functions that I haven't used much or at
all; I think the first thing to do should be to try to find an optimum
"shape" for the core stuff. Options include
1 Inventing a new "core" library and simply keeping it as small as
possible (perhaps setting a hard limit on number of lines of code,
which may sound silly, but could be helpful in focussing the mind on
what's important)
2 Putting everything strictly in table & string; this doesn't really
work, because a lot of stuff we have is really to do with functions,
not tables.
3 Adding a few new libraries as necessary. For example, I propose to
abolish my set module, folding it back into table, but adding a vector
module is arguably good.
I'll end with a concrete proposal of what I think is best from the above:
we should add "vector" and "function" to the current "string", "table"
&c., and put all our additions into those four tables. One or two are
tricky (are map and filter in function or table?) but they all fit in one
of the four. Once that's done we can take another look.
> method() is to methods what bind() is to functions (bind_method() lies
> somewhere in the middle). I don't see how you can claim that one is useful
> but not the other. Personally, I use them both about equally, and from my
> libary use only map() more frequently.
Fair enough. Arguments like this are difficult to resolve until we've had
more experience with a larger community of programs and more lines of
code. There's scope for a little bloat in the interests of variety to
start with in the library as long as it's understood that it should get
smaller (in the core), not bigger. I don't think there's much of a problem
with outlying modules getting bigger.
Of course, this is always going to be the stuff that people argue over the
most, too.
--
http://www.mupsych.org/~rrt/ | golf, n. a good walk spoiled (Twain)
|
|
From: Johann H. <jhi...@ya...> - 2004-02-05 03:38:44
|
On Feb 4, 2004, at 5:58 AM, Reuben Thomas wrote: > I'll end with a concrete proposal of what I think is best from the > above: > we should add "vector" and "function" to the current "string", "table" > &c., and put all our additions into those four tables. One or two are > tricky (are map and filter in function or table?) but they all fit in > one > of the four. Once that's done we can take another look. Hm. From an aesthetic point of view, I'd still rather have functions such as map, filter, and their friends in a "list" package, rather than in a "vector" package. "list" is a human word, more accurate than "vector" for what amounts to a linear sequence. I know many people look at "list" and think "linked list", but "vector" is just bad. Well, at least it seems like poor terminology unless you can point me at the scaling operators and the identity, and demonstrate that they're closed under addition. I suppose that's just taste. However, to steal an idea from Common Lisp, would it be a good idea to have a set of "sequence" functions, in their own package, that are designed to be smart enough to try to decide what kind of type they're dealing with and Do The Right Thing? I'm still working on my package of lispy routines. Obvious things that I use all the time are "find", "find_if", "position", "position_if", and "member." The other functions, like "substitute", are also handy, just not as often. These can be applied over tables and strings at least, and perhaps over other types that are defined. I'm just afraid that if the library becomes too functional, the Typical Programmer would have a hard time figuring out how to apply all the elegant tools. -Johann |
|
From: Reuben T. <rr...@sc...> - 2004-02-05 09:15:51
|
> I'm just afraid that if the library becomes too functional, the Typical > Programmer would have a hard time figuring out how to apply all the > elegant tools. I don't think there's too much danger of that with the mix we have so far. I think I'll shut up now until I've had a chance actually to finish a first cut with the results of the recent conversation we've had. I'm going to be away for a week starting tomorrow, so it probably won't happen until I get back, but hopefully I'll have some time while away to work on it. -- http://www.mupsych.org/~rrt/ | wet nurse, n. lactating lackey |
|
From: Jamie W. <j...@jm...> - 2004-02-04 17:19:46
|
On Wednesday 04 February 2004 10:58, Reuben Thomas wrote:
> > Seriously though, I realise it's not very general, but I have found it
> > useful. I suppose it just depends on how large you want the library to
> > end up.
>
> That's a difficult question, of course: we have multiple goals. First, to
> reach into and improve the libraries actually shipped with Lua. Secondly,
> to add some core programming utils (this is mostly what we've discussed so
> far). Thirdly, to add lots of special purpose stuff (like Diego's mbox
> parser, which I was eulogising last night).
I'm wondering though if the special-purpose stuff wouldn't be better going
straight into Cheia rather than stdlib.
> 1 Inventing a new "core" library and simply keeping it as small as
> possible (perhaps setting a hard limit on number of lines of code,
> which may sound silly, but could be helpful in focussing the mind on
> what's important)
Perhaps some metrics on level of usage of each function would be more
appropriate.
> 2 Putting everything strictly in table & string; this doesn't really
> work, because a lot of stuff we have is really to do with functions,
> not tables.
I agree.
> 3 Adding a few new libraries as necessary. For example, I propose to
> abolish my set module, folding it back into table, but adding a vector
> module is arguably good.
Mmm... except that most of what is in Lua table ought to be in vector.
> I'll end with a concrete proposal of what I think is best from the above:
> we should add "vector" and "function" to the current "string", "table"
> &c., and put all our additions into those four tables. One or two are
> tricky (are map and filter in function or table?) but they all fit in one
> of the four. Once that's done we can take another look.
Well, fn or something rather than function presumably. Given the argument
order, the existing convention suggests that map and filter ought to be in
function. Trouble with that is that then you can't have vector.map, list.map,
table.map, etc. So, either the argument order needs changing (bad, because
other languages have it that way round, and it makes the most sense for
partial applicaton), the convention needs abandoning (might be bad, depending
on this whole { __index = table } business), or map needs to be on vectors
only (bad; not very forward-thinking).
-- Jamie Webb
|
|
From: Reuben T. <rr...@sc...> - 2004-02-04 17:30:17
|
> I'm wondering though if the special-purpose stuff wouldn't be better going
> straight into Cheia rather than stdlib.
Quite possibly. It's really just a question of presentation.
> Perhaps some metrics on level of usage of each function would be more
> appropriate.
Right.
> Mmm... except that most of what is in Lua table ought to be in vector.
So that's part of our re-org of the existing libraries.
> > I'll end with a concrete proposal of what I think is best from the above:
> > we should add "vector" and "function" to the current "string", "table"
> > &c., and put all our additions into those four tables. One or two are
> > tricky (are map and filter in function or table?) but they all fit in one
> > of the four. Once that's done we can take another look.
>
> Well, fn or something rather than function presumably
Keyword, duh. func?
> Given the argument order, the existing convention suggests that map and
> filter ought to be in function. Trouble with that is that then you can't
> have vector.map, list.map, table.map, etc. So, either the argument order
> needs changing (bad, because other languages have it that way round, and
> it makes the most sense for partial applicaton), the convention needs
> abandoning (might be bad, depending on this whole { __index = table }
> business), or map needs to be on vectors only (bad; not very
> forward-thinking).
It's a real pity that next() is linear or map over vectors wouldn't have
to be different from map over tables.
--
http://www.mupsych.org/~rrt/ | maxim, n. wisdom for fools
|
|
From: Jamie W. <j...@jm...> - 2004-02-04 18:25:57
|
On Wednesday 04 February 2004 17:30, Reuben Thomas wrote: > So that's part of our re-org of the existing libraries. Yeah. Just means that stdlib will break existing code, slowing uptake. > Keyword, duh. func? I suppose. Given that those functions are likely to be used in groups, it would be nice to have something really short, but I suppose fn is too likely to get shadowed by people's locals. > It's a real pity that next() is linear or map over vectors wouldn't have > to be different from map over tables. It would anyway. Map over vectors needs to miss out the n if present. Also, next() doesn't honour numerical order. And why do you say next is linear? -- Jamie Webb |
|
From: Reuben T. <rr...@sc...> - 2004-02-04 18:36:37
|
> > So that's part of our re-org of the existing libraries. > > Yeah. Just means that stdlib will break existing code, slowing uptake. Well, we'll have to minimise that. There's no big problem in duplicating to start with. > I suppose. Given that those functions are likely to be used in groups, it > would be nice to have something really short, but I suppose fn is too likely > to get shadowed by people's locals. Sadly. A lot of the time I'm annoyed by the new naming scheme and having to type table. and string. all the time. > > It's a real pity that next() is linear or map over vectors wouldn't have > > to be different from map over tables. > > It would anyway. Map over vectors needs to miss out the n if present. n is evil. > Also, next() doesn't honour numerical order. Doesn't matter unless the mapped function is assuming something about the underlying list. It shouldn't be. > And why do you say next is linear? Cos it is. Discussed on the list; look at the code if you're not convinced. It's necessary because the table can be rehashed while you're traversing it. I think Squirrel avoids this. -- http://www.mupsych.org/~rrt/ | robber, n. a candid man of affairs (Bierce) |
|
From: Jamie W. <j...@jm...> - 2004-02-04 21:39:40
|
On Wednesday 04 February 2004 18:36, Reuben Thomas wrote:
> n is evil.
Perhaps, but the weird hidden n is a bit evil too. I agree that that is
something that ought to be rationalised one way or the other though.
> > Also, next() doesn't honour numerical order.
>
> Doesn't matter unless the mapped function is assuming something about the
> underlying list. It shouldn't be.
Lua isn't a pure language. If map doesn't do what users expect, they will just
go back to their for-loops.
> Cos it is. Discussed on the list; look at the code if you're not
> convinced. It's necessary because the table can be rehashed while you're
> traversing it. I think Squirrel avoids this.
The code below definately runs in O(N), meaning next() is O(1):
t = {}
for i = 1,N do t[i] = true end
k,v = next(t)
while k do
t[k] = false
k,v = next(t,k)
end
I can believe there are situations in which it is linear (can't be bothered to
look at the source), but for the normal case where the keys are not modified,
it doesn't appear to be.
|
|
From: Reuben T. <rr...@sc...> - 2004-02-04 21:50:59
|
> > Doesn't matter unless the mapped function is assuming something about the > > underlying list. It shouldn't be. > > Lua isn't a pure language. If map doesn't do what users expect, they will just > go back to their for-loops. Fair enough. And there's another rather more compelling reason: if you're building some kind of result, you want it in order. > > Cos it is. Discussed on the list; look at the code if you're not > > convinced. It's necessary because the table can be rehashed while you're > > traversing it. I think Squirrel avoids this. > > The code below definately runs in O(N), meaning next() is O(1): Once again, I'm talking rubbish. next(t) is linear; next(t,e) is constant time. -- http://www.mupsych.org/~rrt/ motive, n. a mental wolf in moral wool (Bierce) |
|
From: Jamie W. <j...@jm...> - 2004-02-05 11:48:25
|
On Thursday 05 February 2004 03:22, Johann Hibschman wrote:
> Hm. From an aesthetic point of view, I'd still rather have functions
> such as map, filter, and their friends in a "list" package, rather than
> in a "vector" package. "list" is a human word, more accurate than
> "vector" for what amounts to a linear sequence.
In what sense do you mean more accurate?
> I know many people look at "list" and think "linked list", but "vector"
> is just bad. Well, at least it seems like poor terminology unless you
> can point me at the scaling operators and the identity, and demonstrate
> that they're closed under addition.
Scaling: map(bind(op["*"], x), v)
(identity being x == 1)
Addition: map(op["+"], v1, v2)
Or with Reuben's version: zipWith(op["+"], {v1, v2})
Additive identity: generate(id, 0, table.getn(v))
(closed as usual, and a vector space if you configure Lua to do its arithmetic
with integers IIRC)
> I suppose that's just taste. However, to steal an idea from Common
> Lisp, would it be a good idea to have a set of "sequence" functions, in
> their own package, that are designed to be smart enough to try to
> decide what kind of type they're dealing with and Do The Right Thing?
Ideally. The modern take on that is either OOP or generic programming, where
table, vector, etc. all implement/model sequence. I'd like to see that sort
of thing, but it doesn't appear to be practical in Lua presently, because
both require a stronger notion of type. Trying to do it just by analysing
tables seems very unpleasant.
> I'm still working on my package of lispy routines. Obvious things that
> I use all the time are "find", "find_if", "position", "position_if",
> and "member." The other functions, like "substitute", are also handy,
> just not as often. These can be applied over tables and strings at
> least, and perhaps over other types that are defined.
Well, I hope you'll contribute them when you're done.
> I'm just afraid that if the library becomes too functional, the Typical
> Programmer would have a hard time figuring out how to apply all the
> elegant tools.
As Reuben says, the library has functional stuff for those who want it, and
more general stuff as well. Functional programming is always going to require
imperative programmers to adjust their mindset somewhat, and I don't think
that providing fewer primitives (making it less helpful), or trying to give
the functions more cuddly names (so they don't match up with the literature)
is going to change that.
|
|
From: Johann H. <jhi...@ya...> - 2004-02-06 03:42:33
|
On Feb 5, 2004, at 6:48 AM, Jamie Webb wrote:
> On Thursday 05 February 2004 03:22, Johann Hibschman wrote:
>> Hm. From an aesthetic point of view, I'd still rather have functions
>> such as map, filter, and their friends in a "list" package, rather
>> than
>> in a "vector" package. "list" is a human word, more accurate than
>> "vector" for what amounts to a linear sequence.
>
> In what sense do you mean more accurate?
Well, "list" is a natural language word, so it's broad and doesn't
promise much. A "vector" is a rather specialized technical word, more
specialized than even "array", so it promises a lot.
It seems equally likely that someone will see "vector" and think
"element of a vector space" as someone will see "list" and think
"linked list". I think a vanishingly small number of people are going
to be confused by using the word "list" for something with O(1) access,
just like a vanishingly small number of people will expect a vector to
have a fixed dimension and pre-defined mathematical operations.
If that's the case, why not go for the word that's common, has two
fewer characters, and is easier to touch-type?
> Scaling: map(bind(op["*"], x), v)
> (identity being x == 1)
>
> Addition: map(op["+"], v1, v2)
> Or with Reuben's version: zipWith(op["+"], {v1, v2})
> Additive identity: generate(id, 0, table.getn(v))
> (closed as usual, and a vector space if you configure Lua to do its
> arithmetic
> with integers IIRC)
I think you missed my point; these definitions work for linked lists
just as well as for 1D arrays, so they don't really show the
"vector"-ness of vectors.
>> I suppose that's just taste. However, to steal an idea from Common
>> Lisp, would it be a good idea to have a set of "sequence" functions,
>> in
>> their own package, that are designed to be smart enough to try to
>> decide what kind of type they're dealing with and Do The Right Thing?
>
> Ideally. The modern take on that is either OOP or generic programming,
> where
> table, vector, etc. all implement/model sequence. I'd like to see that
> sort
> of thing, but it doesn't appear to be practical in Lua presently,
> because
> both require a stronger notion of type. Trying to do it just by
> analysing
> tables seems very unpleasant.
Hm. In lisp, they're typically multiple-dispatch "multimethods", so,
yes, this is OOP, just not in foo.bar(baz) form. In Lua, I guess all
you could do would be to have the same functions work for both strings
and tables, so it's probably not worth the effort.
> As Reuben says, the library has functional stuff for those who want
> it, and
> more general stuff as well. Functional programming is always going to
> require
> imperative programmers to adjust their mindset somewhat, and I don't
> think
> that providing fewer primitives (making it less helpful), or trying to
> give
> the functions more cuddly names (so they don't match up with the
> literature)
> is going to change that.
Well, there are cuddly names and there are cuddly names. "reduce" is a
better word than "foldl", for one, but "foldl" allows you to also
define "foldr", which is good. I think I'd personally rather have
"reduce" with an optional from_end argument than foldl/foldr, but
clearly tastes differ.
At work, I'm converting over some old APL programs, so I'll probably
have some extremely screwy ideas in a few weeks, if I can ever get the
blasted font to work. Now _there_'s a concise language.
-Johann
|
|
From: Jamie W. <j...@jm...> - 2004-02-07 23:15:54
|
On Friday 06 February 2004 03:42, Johann Hibschman wrote: > On Feb 5, 2004, at 6:48 AM, Jamie Webb wrote: > > On Thursday 05 February 2004 03:22, Johann Hibschman wrote: > >> Hm. From an aesthetic point of view, I'd still rather have functions > >> such as map, filter, and their friends in a "list" package, rather > >> than > >> in a "vector" package. "list" is a human word, more accurate than > >> "vector" for what amounts to a linear sequence. > > > > In what sense do you mean more accurate? > > Well, "list" is a natural language word, so it's broad and doesn't > promise much. A "vector" is a rather specialized technical word, more > specialized than even "array", so it promises a lot. That's just it though: all three are rather specialised technical words. The exact way in which they are specialised depends on the field you work in. Since Lua is a mixed imperative/functional language, we should take our definitions from those worlds: Arrays are fixed-size, n-dimensional mutable structures with O(1) random access, O(n) inserts, etc., Vectors are single-dimensional, mutable and resizable in imperative languages, with O(1) random access, O(n) inserts, etc. Lists are mutable and resizable in imperative languages, and have O(n) random access and O(1) inserts. Data Structures books may qualify such lists as linked lists, but programming languages such as C++, ML, and LISP don't. > It seems equally likely that someone will see "vector" and think > "element of a vector space" as someone will see "list" and think > "linked list". I think a vanishingly small number of people are going > to be confused by using the word "list" for something with O(1) access, > just like a vanishingly small number of people will expect a vector to > have a fixed dimension and pre-defined mathematical operations. Difference: A [Lua table with integer keys] may well be a member of a vector space (well, as good as; I don't think double quite qualifies as a field), but it would never be a linked list. Also, the implications of a misunderstanding differ: If a user were to assume he was dealing with a mathematical vector when in fact he wasn't, that could only be as a consequence of a more direct misunderstanding of the operations he is performing, and the interpreter is likely to complain very quickly. OTOH, if a programmer were to assume he was dealing with a linked list, he could quite happily produce a working program, only to discover once he tries it on production-scale data that it runs N times slower than expected. > I think you missed my point; these definitions work for linked lists > just as well as for 1D arrays, so they don't really show the > "vector"-ness of vectors. They show that vectors, arrays, and lists all satisfy your 'element of a vector space' criterion. Therefore, in mathematical terms, we could call any one of them a vector (assuming the elements are numbers). In programming terms, as explained above, a [Lua table with integer keys] has the properties of a vector, and not those of an array or list. > Hm. In lisp, they're typically multiple-dispatch "multimethods", so, > yes, this is OOP, just not in foo.bar(baz) form. In Lua, I guess all > you could do would be to have the same functions work for both strings > and tables, so it's probably not worth the effort. Indeed. > Well, there are cuddly names and there are cuddly names. "reduce" is a > better word than "foldl", for one, but "foldl" allows you to also > define "foldr", which is good. I think I'd personally rather have > "reduce" with an optional from_end argument than foldl/foldr, but > clearly tastes differ. Well, Reuben already has zip = unzip = transpose. Maybe there's an argument for having foldl = reduce, map = foreach, etc. > At work, I'm converting over some old APL programs, so I'll probably > have some extremely screwy ideas in a few weeks, if I can ever get the > blasted font to work. Now _there_'s a concise language. Mmm... I thought those people who still dealt with APL tended to use ASCII representations these days? -- Jamie Webb |
|
From: Jamie W. <j...@jm...> - 2004-02-07 23:23:56
|
On Saturday 07 February 2004 23:15, Jamie Webb wrote: > Well, Reuben already has zip = unzip = transpose. Maybe there's an argument > for having foldl = reduce, map = foreach, etc. Actually, map = transform is probably better, following C++. |
|
From: Reuben T. <rr...@sc...> - 2004-02-14 13:29:13
|
> On Saturday 07 February 2004 23:15, Jamie Webb wrote: > > Well, Reuben already has zip = unzip = transpose. Maybe there's an argument > > for having foldl = reduce, map = foreach, etc. > > Actually, map = transform is probably better, following C++. I'd rather reduce the number of names if possible. I had zip = unzip = transpose because I thought that it was unlikely that programmers used to zip and unzip would realise that they were both transpose in Lua. OTOH, that's a fairly small community I'm catering too, and discussion among users of the libraries might be hampered by having all these names... OTOOH, those names are much more obvious when you're reading code and you're trying to work out what it's doing... I think the answer is probably (as usual) to strike a balance. My view of that balance would be to provide those names that make code easier to read, and not provide extra names just to give people the names they're used to. zip, unzip and transpose are different ideas (they have different types in strongly-typed languages, after all!). map and transform aren't. In the end, the only way to keep this thing small and simple (as it should be) is to have a "one true way". This should really be as close as possible to *the* One True Way, and I'm quite happy to argue over it lots, but in the end, I think we have to make a decision. -- http://www.mupsych.org/~rrt/ | wit, n. educated insolence (Aristotle) |
|
From: Johann H. <jhi...@ya...> - 2004-02-08 23:48:14
|
On Feb 7, 2004, at 6:15 PM, Jamie Webb wrote: > On Friday 06 February 2004 03:42, Johann Hibschman wrote: >> Well, "list" is a natural language word, so it's broad and doesn't >> promise much. A "vector" is a rather specialized technical word, more >> specialized than even "array", so it promises a lot. > > That's just it though: all three are rather specialised technical > words. The > exact way in which they are specialised depends on the field you work > in. Well, there is still a difference. "list" is common language, that's been co-opted by many programming languages to mean linked lists, but it's certainly not omni-present. For example, I do a lot of Python, and Python lists are vector-like lists, not linked lists. However, it's certainly true that the list/vector difference is maintained in Scheme, Common Lisp, Java, OCaml, and probably many other languages. It doesn't really matter that much. I can always rename any "vector" module to "list" and be done. I'm just lazy, find it easier to type "list", and think its natural-language overtones mesh better with the word "table". > Since Lua is a mixed imperative/functional language, we should take > our > definitions from those worlds: Arrays are fixed-size, n-dimensional > mutable > structures with O(1) random access, O(n) inserts, etc., Vectors are > single-dimensional, mutable and resizable in imperative languages, > with O(1) > random access, O(n) inserts, etc. Lists are mutable and resizable in > imperative languages, and have O(n) random access and O(1) inserts. > Data > Structures books may qualify such lists as linked lists, but > programming > languages such as C++, ML, and LISP don't. Actually, this reminds me. What are the times on Lua tables? I know that integer indices are special, but do they get true O(1) access? Presumably, other keys are O(log n), as usual. > Also, the implications of a misunderstanding differ: If a user were to > assume > he was dealing with a mathematical vector when in fact he wasn't, that > could > only be as a consequence of a more direct misunderstanding of the > operations > he is performing, and the interpreter is likely to complain very > quickly. > OTOH, if a programmer were to assume he was dealing with a linked > list, he > could quite happily produce a working program, only to discover once > he tries > it on production-scale data that it runs N times slower than expected. That's certainly true, but I think it's very unlikely. >> At work, I'm converting over some old APL programs, so I'll probably >> have some extremely screwy ideas in a few weeks, if I can ever get the >> blasted font to work. Now _there_'s a concise language. > > Mmm... I thought those people who still dealt with APL tended to use > ASCII > representations these days? Nah, ASCII representations are for the weak. You need the funny arrows and things. :-) In any case, I don't see much of a point in continuing to discuss this, since I can always rename packages to whatever I prefer. If you would really rather call it a vector package, we can just go with that. Cheers, Johann |
|
From: Reuben T. <rr...@sc...> - 2004-02-14 14:13:45
|
> It doesn't really matter that much. I can always rename any "vector" > module to "list" and be done. I'm just lazy, find it easier to type > "list", and think its natural-language overtones mesh better with the > word "table". I strongly agree with this. List is a reasonably vague word, and it's obvious and nice to type. > Actually, this reminds me. What are the times on Lua tables? I know > that integer indices are special, but do they get true O(1) access? > Presumably, other keys are O(log n), as usual. Integer indices that end up in the array part of the table get O(1) access (effectively they have space reserved for them). However, which keys are actually in the array part is a little harder to determine. Basically, it's all the keys up to N such there are at least half of all possible keys in the range 1-N, i.e. occupancy of the array is at least 50%. But if you add bigger keys (>N) then even when occupancy of some larger N becomes >50%, those keys will be kept in the hash table part until it overflows and the table is resized. When this happens depends on the table. If you never put anything but integer keys in a table, then almost all your keys will almost always have O(1) access time. > Nah, ASCII representations are for the weak. You need the funny arrows > and things. :-) Funny thing, I've been reading the docs on K recently, and I'm impressed (I've been meaning to do it for years...). -- http://www.mupsych.org/~rrt/ | art, n. romanticized mundanity |
|
From: Jamie W. <j...@jm...> - 2004-02-09 01:44:29
|
On Sunday 08 February 2004 23:48, Johann Hibschman wrote: > It doesn't really matter that much. I can always rename any "vector" > module to "list" and be done. I'm just lazy, find it easier to type > "list", and think its natural-language overtones mesh better with the > word "table". At present, you could gave the module an alias, but if you deleted the original name it would break the internal references. That probably ought to be changed. > Actually, this reminds me. What are the times on Lua tables? I know > that integer indices are special, but do they get true O(1) access? > Presumably, other keys are O(log n), as usual. They are hash tables, so in practice can usually be treated as O(1). Integer indices are implemented as an array, so are guaranteed O(1). There is a 'sparsity' heuristic which determines the size of the array. Any indices falling outside the array are hashed as usual. > In any case, I don't see much of a point in continuing to discuss this, > since I can always rename packages to whatever I prefer. If you would > really rather call it a vector package, we can just go with that. TBH I don't much like vector either. I just also don't like misnaming things, not least because it leaves no name for the real thing. In terms of wasted keystrokes and display width, perhaps vec would be better than vector. |
|
From: Reuben T. <rr...@sc...> - 2004-02-14 14:14:41
|
> At present, you could gave the module an alias, but if you deleted the > original name it would break the internal references. That probably ought to > be changed. Good point. I hadn't thought of that. -- http://www.mupsych.org/~rrt/ | What you don't know controls you |
Thanks for helping keep SourceForge clean.
X