[Grace-core] more comments on collections

[Andrew P. Black]

On 12 Jul 2014, at 8:44, Kim Bruce <kim at cs.pomona.edu> wrote:

> Andrew,
> 
> Here are some comments on the collection classes.  I hope you find them helpful.
> 
> As I was adding types, I found I needed to (trivially) convert list to a class because it now takes a type parameter.  Interestingly, you had written similar things for your traits: collectionFactory.trait and iterable.trait.  Perhaps it would be more consistent to make them all classes.

List always was a class, in the sense of an factory object.   I couldn’t declare it with the dotted class syntax because that syntax did not provide for inheritance between factory objects.  (list needs to inherit from collectionFactory).   I could use the class method syntax, and did so for the month that this was in the language, but now that its out again,  I removed it. 

> A (perhaps picky) conceptual issue with your library design.  Operations like remove on sets returns "self", which makes it convenient to chain together operations.  However, other operations like "-" returns a new list.  

Perhaps you mean - on sets?

> I find it a bit confusing that both have essentially the same type (and otherwise look very similar).  This requires very good comments (and the user to read them!) to understand when the operation is a mutates the current data structure and when it results in a new one.  I'm not sure what the right answer is (don't worry about chaining operations?), but it seems like it would be confusing, especially to new programmers.

Well, perhaps.  Certainly the types do not tell the client what the operations do; for that you need a specification.   My thought was that sets should have the mathematical set operations (union, intersection, and difference), and that these should answer new sets, whereas operation like remove and add mutate the receiver.   This seems clear to me from the names — but, as you say, not necessarily clear to novices.    

> Here are the types of List<T> and Set<T> as I've extracted them from your code.  One question:  Why both add and addAll in List, 

Because add() takes a variable arity argument list.   But, as we have discussed previously, if you want to call add() and you have a collection of things to add, we have no syntax to “explode” that collection into an argument list.    So we need addAll, and the convention that whenever one defines a variable arity method, one should always do so in terms of another method that takes a collection. I violated that rule with remove, which I should supplement with removeAll.

> where add in Set seems to be like addAll in List rather than add.  

add in list should be a variable arity method too.  Good catch.   

> Also set has a copy operation, while list doesn't.  Why?  

Another oversight on my part.  The interfaces came from mgcollections, which is where some of the strange names come from (e.g, push)

> Finally Range's == seems to require a Collection<T> for the argument, while == for List and Set both accept any Object.  Consistency would be useful.

I agree.  I wrote range first.   Do we want equality to work between the receiver and any object, or just between the receiver and types that might be equal?
> 

> type List<T> = {  
>     at(n: Number) -> T
>    [](n: Number) -> T

keep both of these?

>    at(n: Number)put(x: T) -> List<T>
>    []:=(n: Number,x: T) -> List<T> 

keep both of these?

>    add(x: T) -> List<T>
>    push(x: T) -> List<T>

delete this?

>    addLast(x: T) -> List<T>    // compatibility
>    removeLast -> T 
>    addFirst(x: T) -> List<T> 
>    removeFirst -> T 
>    removeAt(n: Number) -> T
>    pop -> T

delete this?

>    indices -> List<Number>   // range type?

It does return a range, which is a Sequence type — like List, but without the mutators.

>    first -> T 
>    second -> T
>    third -> T
>    fourth -> T 
>    last -> T 
>    ++(o: List<T>) -> List<T>
>    asString -> String
>    addAll(l) -> List<T>
>    extend(l: List<T>) -> Done

delete this; extend(l) is a synonym for { addAll(); done }, introduced for compatibility with mgcollections. 

>    contains(element) -> Boolean
>    do(block1: Block1<T,Done>) -> Done
>    ==(other: Object) -> Boolean
>    iterator -> Iterator<T>

you forgot the methods in enumerable.trait

    do(body:Block1<T,Done>)separatedBy(separator:Block0<Done>) -> Done
    fold(blk:Block1<T,X>)startingWith(initial:T) -> X
    map(blk:Block1<T,X>) -> Iterator<X>
    filter(condition:Block1<T,Boolean>) -> Iterator<T>
> }
> 
> type Set<T> = {
>     size -> Number
>     add(*elements:T) -> Set<T>
>     remove(*elements: T) -> Set<T>
>     remove(*elements: T)ifAbsent(block: Block0<Done>) -> Set<T>
>     contains(x: T) -> Boolean
>     includes(booleanBlock: Block1<T,Boolean>) -> Boolean
>     find(booleanBlock: Block1<T,Boolean>)ifNone(notFoundBlock: Block0<T>) -> T
>     asString -> String
>     -(o: T) -> Set<T>
>     extend(l: Collection<T>) -> Set<T>
>     do(block1<T,Done>) -> Done
>     iterator -> Iterator<T>
>     ==(other: Object) -> Boolean
>     copy -> Set<T>
> }
> 
> I'm having trouble typing dictionary because of the tricky defs of unused and removed, which don't have the right types.  I may have to recode to make it typable.  Any suggestions/concerns?

I personally wouldn’t bother — typing the i interfaces is very useful, but typing the internals will do nothing but slow these methods down.  However, if you really want to, then the PrimitiveArray inside a dictionary object should be a PrimitiveArray<T|Marker>, where Marker is a type that describes the Markers unused and removed, each of which should be a singleton type.

I’ll make some corrections based on what you wrote above.  But now we have three versions — in Collections, in StnadardPrelude, and in setsNLists.   That’s 2 too many for me to track ...

	Andrew

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailhost.cecs.pdx.edu/pipermail/grace-core/attachments/20140716/c57c0028/attachment.html>