A Collections Framework?
in [Lisp]
|
Prev: scheme problem
Next: lisp student job offer
From: RG on 10 May 2010 12:35 In article <83b6c48e-6aee-4bac-a990-077d20f16755(a)23g2000pre.googlegroups.com>, "Scott L. Burson" <gyro(a)zeta-soft.com> wrote: > On May 10, 6:35 am, Pascal Costanza <p...(a)p-cos.net> wrote: > > > > The Java collection API inherently builds on mutability: It's very hard > > to create collections without having to "add" elements one by one, and > > as soon as you want to iterate over a collection, you get a data > > structure that keeps track of the iteration state by way of side > > effects. I hope that Lisp collection frameworks don't copy such "features". > > Funny you should mention the iterator issue as I puzzled over it for > some time. I eventually decided it made sense even for FSet to > provide stateful iterators; for most uses the difference doesn't > matter, and stateful iterators are more efficient. Also, as noted in > the FSet documentation, if you want to do functional iteration, you > might as well just convert the collection to a list -- it's hard to > improve on lists for functional iteration. (Generating the list > lazily might be some improvement, as it reduces the peak space > requirement, but at a small cost in time because the "CDR"-like > operation is now a little more involved.) Note that lists have this property because -- and only because -- they are essentially caches of precomputed iterators. Every CDR in a linked list is an iterator that points to a particular step in an iteration. You can accomplish exactly the same thing with any immutable data structure. All you need for functional traversal is to cons up a fresh copy of the iteration state for each step. Lists (and vectors) require no consing because their iteration states are immediate values and so require no heap storage. For data structures whose iterators are not immediate values, traversal is typically done with side effects (on the iterator it is worth noting, not the underlying data structure) purely for efficiency, to avoid having to cons up a bunch of iterators that get used once and are immediately (no pun intended) discarded. rg
From: Scott L. Burson on 10 May 2010 14:19 On May 10, 9:35 am, RG <rNOSPA...(a)flownet.com> wrote: > All you need for functional traversal is to cons up a fresh > copy of the iteration state for each step. Yes, exactly, and at one point I was doing that, but then it dawned on me that it required more than one cons per step -- so what was the point? -- Scott
From: RG on 10 May 2010 15:16 In article <1358b55b-b6b9-43ce-bdac-31a5fa7e597a(a)t34g2000prd.googlegroups.com>, "Scott L. Burson" <gyro(a)zeta-soft.com> wrote: > On May 10, 9:35 am, RG <rNOSPA...(a)flownet.com> wrote: > > All you need for functional traversal is to cons up a fresh > > copy of the iteration state for each step. > > Yes, exactly, and at one point I was doing that, but then it dawned on > me that it required more than one cons per step -- so what was the > point? What's the point of what? Functional traversal, or using a data structure other than a list to do it? Functional traversal is mainly handy if you have to backtrack. And using something other than a list as the backing store is handy if, for example, you need to delete elements. Personally I think it's more trouble than it's worth, but a case can be made for it for certain sets of requirements. rg
From: Pascal Costanza on 10 May 2010 16:53 On 10/05/2010 18:17, Scott L. Burson wrote: > On May 10, 6:35 am, Pascal Costanza<p...(a)p-cos.net> wrote: >> >> The Java collection API inherently builds on mutability: It's very hard >> to create collections without having to "add" elements one by one, and >> as soon as you want to iterate over a collection, you get a data >> structure that keeps track of the iteration state by way of side >> effects. I hope that Lisp collection frameworks don't copy such "features". > > Funny you should mention the iterator issue as I puzzled over it for > some time. I eventually decided it made sense even for FSet to > provide stateful iterators; for most uses the difference doesn't > matter, and stateful iterators are more efficient. Also, as noted in > the FSet documentation, if you want to do functional iteration, you > might as well just convert the collection to a list -- it's hard to > improve on lists for functional iteration. (Generating the list > lazily might be some improvement, as it reduces the peak space > requirement, but at a small cost in time because the "CDR"-like > operation is now a little more involved.) I'm concerned about this because using stateful iterators adds unnecessary dependencies, which can hurt if you want to parallelize your code. I think in the future we have to pay a lot more attention to such issues. Pascal -- My website: http://p-cos.net Common Lisp Document Repository: http://cdr.eurolisp.org Closer to MOP & ContextL: http://common-lisp.net/project/closer/
From: Scott L. Burson on 10 May 2010 16:57
On May 10, 12:16 pm, RG <rNOSPA...(a)flownet.com> wrote: > In article > <1358b55b-b6b9-43ce-bdac-31a5fa7e5...(a)t34g2000prd.googlegroups.com>, > "Scott L. Burson" <g...(a)zeta-soft.com> wrote: > > > On May 10, 9:35 am, RG <rNOSPA...(a)flownet.com> wrote: > > > All you need for functional traversal is to cons up a fresh > > > copy of the iteration state for each step. > > > Yes, exactly, and at one point I was doing that, but then it dawned on > > me that it required more than one cons per step -- so what was the > > point? > > What's the point of what? Functional traversal, or using a data > structure other than a list to do it? The latter. > Functional traversal is mainly > handy if you have to backtrack. And using something other than a list > as the backing store is handy if, for example, you need to delete > elements. Well, in the case of FSet, we're talking about functional traversal of a functional collection, so this doesn't apply. May as well use a list. -- Scott |