« Return to Thread: Towards a revised collection API
Re: Towards a revised collection API
by David MacIver
::
Rate this Message:
On Fri, Apr 18, 2008 at 1:13 PM, Jamie Webb <j@...> wrote:
> On 2008-04-18 12:28:38 David MacIver wrote:
> > So, with the recent noise I've been making about the collections API,
> > I figured I should put some thoughts down on screen.
> >
> > As I see it one of the main problems with the current collection API
> > is that in order to make things play nicely you need to override
> > methods at every step of the way. map, filter, flatMap etc all return
> > the "wrong" things. This is a pain to write and easy to get wrong.
>
> This is what Martin is talking about fixing with type constructor
> polymorphism, which seems preferable by far.
Sure. This solution uses type constructor polymorphism too. But
getting it to handle returning the right type automatically without
having to constantly reimplement isn't totally trivial.
> > The other thing I don't like about the collections API is that I'm not
> > a big fan of iterators. They're really cumbersome to create for custom
> > collection types and are designed around a really irritating "check
> > then proceed" style. Really all we care about is how to traverse the
> > data structure, and constructing an iterator to do so is often not the
> > best way.
>
> Agreed. See scalax.control.ManagedSequence for some code that gets
> badly bitten by this. However, aside from creating one or more
> superclasses of Iterable that define the more functional interfaces,
> it's hard to see how to improve.
Either the mailing list stripped the attached file, or you missed it.
In the case that it's the former, here's a pastebin:
http://pastebin.com/m23106284
My point is you can reimplement basically the entire Iterable trait
sans "elements" based on only foreach.
> > - Consequently it's ok if we return the "wrong" thing.
>
> Only if we assume that all our operations are non-strict, which I don't
> think is a good thing.
I think this is ok. The useage I have in mind is that you do a bunch
of calculations with a "suspended" result and then immediately thunk
the whole thing.
> > - In fact it may be desirable to do so!
> > - All we care about generically are how to traverse a data structure
> > and how to build one, so these are the operations the API should be
> > designed around.
>
> Clearly, but that is already the case.
Not really. The API is poorly constructed for building, and the
traversal strategies center around creating iterators.
> > So the API defines a trait Enumerable which describes how to traverse
> > a structure and a trait Buildable which describes how to build one
> > (the data structure doesn't implement Buildable, one makes an implicit
> > instance available). Implementations do not override the enumerable
> > map, flatMap, etc. methods - these continue to return a generic
> > enumerable. However at the end of a bunch of operations you explicitly
> > "cast" to the desired result.
>
> Do you have some type signatures for these classes that you can show us?
As before, see attached file / pastebin.
> > We can use return from inside passed closures to control evaluation
> > and exit the loop prematurely, which allows efficient implementation
> > of things like exists, foreach and take. For example:
>
> Non-local returns are implemented via exceptions, so they are not
> really efficient. I think any move away from iterators is likely to
> imply a performance loss.
I disagree. Exceptions are extremely fast on the JVM and have been for
years. They basically compile to gotos. It's just stack trace
generation which is slow, which you can surpress in your
implementation of Throwable (which I assume Scala's non-local returns
do. If not, I'd consider that a bug. I'll check later).
I'm not saying this will never be slower. But equally I expect there
are a lot of times where it will be faster, particularly when it can
eliminate a bunch of intermediate structures.
> On 2008-04-18 12:28:38 David MacIver wrote:
> > So, with the recent noise I've been making about the collections API,
> > I figured I should put some thoughts down on screen.
> >
> > As I see it one of the main problems with the current collection API
> > is that in order to make things play nicely you need to override
> > methods at every step of the way. map, filter, flatMap etc all return
> > the "wrong" things. This is a pain to write and easy to get wrong.
>
> This is what Martin is talking about fixing with type constructor
> polymorphism, which seems preferable by far.
Sure. This solution uses type constructor polymorphism too. But
getting it to handle returning the right type automatically without
having to constantly reimplement isn't totally trivial.
> > The other thing I don't like about the collections API is that I'm not
> > a big fan of iterators. They're really cumbersome to create for custom
> > collection types and are designed around a really irritating "check
> > then proceed" style. Really all we care about is how to traverse the
> > data structure, and constructing an iterator to do so is often not the
> > best way.
>
> Agreed. See scalax.control.ManagedSequence for some code that gets
> badly bitten by this. However, aside from creating one or more
> superclasses of Iterable that define the more functional interfaces,
> it's hard to see how to improve.
Either the mailing list stripped the attached file, or you missed it.
In the case that it's the former, here's a pastebin:
http://pastebin.com/m23106284
My point is you can reimplement basically the entire Iterable trait
sans "elements" based on only foreach.
> > - Consequently it's ok if we return the "wrong" thing.
>
> Only if we assume that all our operations are non-strict, which I don't
> think is a good thing.
I think this is ok. The useage I have in mind is that you do a bunch
of calculations with a "suspended" result and then immediately thunk
the whole thing.
> > - In fact it may be desirable to do so!
> > - All we care about generically are how to traverse a data structure
> > and how to build one, so these are the operations the API should be
> > designed around.
>
> Clearly, but that is already the case.
Not really. The API is poorly constructed for building, and the
traversal strategies center around creating iterators.
> > So the API defines a trait Enumerable which describes how to traverse
> > a structure and a trait Buildable which describes how to build one
> > (the data structure doesn't implement Buildable, one makes an implicit
> > instance available). Implementations do not override the enumerable
> > map, flatMap, etc. methods - these continue to return a generic
> > enumerable. However at the end of a bunch of operations you explicitly
> > "cast" to the desired result.
>
> Do you have some type signatures for these classes that you can show us?
As before, see attached file / pastebin.
> > We can use return from inside passed closures to control evaluation
> > and exit the loop prematurely, which allows efficient implementation
> > of things like exists, foreach and take. For example:
>
> Non-local returns are implemented via exceptions, so they are not
> really efficient. I think any move away from iterators is likely to
> imply a performance loss.
I disagree. Exceptions are extremely fast on the JVM and have been for
years. They basically compile to gotos. It's just stack trace
generation which is slow, which you can surpress in your
implementation of Throwable (which I assume Scala's non-local returns
do. If not, I'd consider that a bug. I'll check later).
I'm not saying this will never be slower. But equally I expect there
are a lot of times where it will be faster, particularly when it can
eliminate a bunch of intermediate structures.
« Return to Thread: Towards a revised collection API
| Free embeddable forum powered by Nabble | Forum Help |
