Systematize and Complete the Coalton Collections Library

[Jason94]

The current Coalton collections library suffers from several problems.

1. Missing functionality: Some key data structures, such as mutable/immutable sets are missing. Some exiting data structures, particularly Seq, are missing important functions that make them difficult to use.
2. Poor ergonomics: Existing collections represent the same operations with different names and type signatures. Some collections are overly-protective with returning Optional types, particularly Ord-Map. Most collections functions are not in prelude-indeed they cannot be because they would collide with each other-and are annoying to use because you have to prepend the package nickname.
3. Lack of abstraction: Besides the traditional ML favorites (Monoid, Traversable, etc) the collections library is not wrapped in useful typeclasses. This impedes library design because you cannot generalize on a collection and is the reason that the collections functions cannot live nicely together in prelude.
4. Low discoverability. There's no source of documentation on the collections library as a whole. (See: https://docs.scala-lang.org/overviews/collections-2.13/overview.html as a good example.) To learn what collections Coalton provides, you have to comb through the reference page and see what you find. Some important functions, particularly map, are brought in through typeclasses. For a Lisper unexperienced with Haskell-style FP languages, it could be very confusing why List doesn't seem to have a map function.

Here is a propsoal to standardize and complete the collections library, fixing the above problems:

1. Move all of the collections into new COALTON-LIBRARY/COLLECTIONS/IMMUTABLE/ and COALTON-LIBRARY/COLLECTIONS/MUTABLE/ packages. This mirrors the Scala organization, and it's very nice! Move packages like COALTON-LIBRARY/SLICE which support the collections library to the root COALTON-LIBRARY/COLLECTIONS package.
2. Standardize the naming conventions of all collections functions. I proposed a naming convention of combining a prefix representing the command with a postfix representing what you're taking. So remove-where removes the first element that matches a predicate. remove-at removes the element at an index.find-where returns the first element matching a predicate. index-where returns the index of the first element matching a predicate. contains-where? returns a bool if you're matching a predicate, etc. Unfortunately this means discarding some of the historical Lisp functions like car, but those can remain specific to the List type in case anyone likes to use them!
3. Cover all of the standard collections functions with a complete Typeclass hierarchy capturing all of the necessary functionality. Wrap all of the collection datatypes in the new typeclasses. This will put some operations on dataclasses that aren't efficient (appending to Vector, etc.) but that's okay. The library should allow programmers to perform O(n) operations.
4. Export all of the now-standard functions for the collection typeclasses in the Prelude package, so they no longer have to be qualified.
5. The generic interface should support two values in its type signature: safety and ergonomics. This means having options like (UFix -> Seq :a -> Optional :a) and (UFix -> Seq :a -> :a) available. The collections interface should not sacrifice ergonomics to merely provide information via the types (particularly the return type). This means signatures like Ord-Map:insert :: ∀ :A :B. ORD :A ⇒ ((MAP :A :B) → :A → :B → (OPTIONAL (MAP :A :B))) should be avoided, because the Optional return type only provides information, not safety, to the user at the expense of ergonomics. Another example, signatures like List:take :: ∀ :A. (UFIX → (LIST :A) → (LIST :A)) should be favored over List:tail :: ∀ :A. ((LIST :A) → (OPTIONAL (LIST :A))). In both cases a reasonable return value can be constructed, and tail sacrifices ergonomics but gains neither safety nor information. Individual collections can have concrete functions that take this approach to support particular use-cases, but they shouldn't be on the generic interface.
6. Always have the collection be the last argument in the function. First, I find this more intuitive because it's putting the operand next to the operand suffix. find-where odd? xs, etc. Second, it's more useful with currying because that way you can thread collections through partially applied collection operations without needing to construct intermediate lambdas.

Here are a few elements of the proposal I'm not sure about, and should definitely be discussed:

1. I personally use unsafe versions of get, etc, liberally. The current paradigm is to use the convention function-unsafe for those functions. I suggested use of the # symbol (it's sharp, so it's pretty unsafe - it could poke an eye out!) instead for better ergonomics. get# instead of get-unsafe, insert!# instead of insert-unsafe!, etc.
2. To favor getting more functionality up fast, I would suggest building off of existing fset collections for any new immutable datastructures. I'm not sure about the long term trade-offs of having Coalton native collections (which is the case for all of the current immutable collections, I believe) vs reusing the work of libraries like fset.
3. I took an innovation by treating linear, integer indexed collections like List, Vector, etc. as UFix-keyed maps. The Scala collections (or others that I've seen) don't do this, but I didn't see any reason not to do it.
4. I'm not sure if we should give the mutable/immutable collections different names or not. In Scala they often have the same name. But their package system works better, so they're able to provide Set as an out-of-the-box default for the immutable set. But, you can import scala.collection.mutable.Set and now Set creates a mutable set, and the compiler doesn't complain like Common Lisp's does.

Finally, this is a big, breaking change - even for < 1.0 software like Coalton. It can be done in pieces:

1. Copy, not move, collection packages into the new package structure. Update the new versions to use the new naming conventions and typeclasses, leave the old ones exactly as-is.
2. Export in Prelude only the typeclass functions that don't conflict with existing functions already exported in prelude.
3. (Maybe not necessary? Not sure to treat existing Coalton users.) Add a depracation warning to each of the old collection packages, pointing them to the package they should migrate to. Each package will have an internal tracker if the deprecation warning has been printed or not. The first time per each program run that a function in that package is called, it prints the deprecation warning. Could add a bool in each package to disable.

Here is the proposed TypeClass hierarchy:

Typeclass	Description	Implements	Concrete Collections
Collection :a	Root collection typeclass. A "Collection" is an object that contains a finite number of :a elements.	Monoid, Applicative, Functor, Monad, Traversable
ImmutableCollection :a		Collection :a	Set*
MutableCollection :a		Collection :a	MutSet*
KeyedCollection :k :v	A collection of unordered, keyed elements.	Collection (Tuple :k :v)
ImmutableKeyedCollection :k :v		KeyedCollection :k :v ImmutableCollection (Tuple :k :v)	Ord-Map
MutableKeyedCollection :k :v		KeyedCollection :k :v MutableCollection (Tuple :k :v)	Hashmap
LinearCollection :a	A collection of ordered elements with indexable access by position.	KeyedCollection (Tuple UFix :a)
ImmutableLinearCollection :a		ImmutableKeyedCollection (Tuple UFix :a) LinearCollection :a	Seq, List
MutableLinearCollection :a		MutableKeyedCollection (Tuple UFix :a) LinearCollection :a	Vector, Queue, Lisparray

(* - Set does not currently exsit)

Here is a chart showing the typeclass hierarchy along with the existing collections (plus mutable and immutable Sets):

Finally, because it's too big to include here, I've created a spreadsheet with the proposed functions and the status of the current collections. I'll continue to clean this up and add which typeclass each function should belong to.

[Jason94]

Also, I think that some of the list functions could be more efficient if they used mutation internally, while still not "leaking" any mutability. For example, append could be implemented more efficiently by building up new cons cells as it walks the first operand list, then mutating the cdr of the previous cell to point to the new one. Currently, though, the List module is written almost entirely in Coalton, and it'd need to undergo a heavy refactor using cells to make that possible.

(I'm not going to fix this here, but I'll probably raise it as a separate issue.)

[Jason94]

After more work, I think the originally proposed method of collection inheritance is going to introduce more complexity than I'd initially anticipated. Particularly, it will make working with LinearCollections less intuitive.

The definitions:

  (define-class (Collection :m :a (:m -> :a))
    ...
  (define-class (Collection :m (Tuple :k :v) => KeyedCollection :m :k :v (:m -> :k :v)))
    ...
  (define-class (KeyedColleciton :m UFix :a => LinearCollection :m :a)
    ...

run into some issues with wanting the Collection methods to be described inconsistently for KeyedCollections and LinearCollections.

For example, take filter :: (:a -> Boolean) -> :m -> :m) on the Collection typeclass. On a Map type, it makes sense to call something like this. It nicely utilizes the fact that all KeyedCollections are Collections of tuples to reuse the filter function.

(filter (fn (key-value) (> (snd key-value) (fst key-value))) my-map)

However, suppose you wanted to do something simple like remove all of the negative integers in a list of integres. You'd have to do something like this, because all LinearCollections are KeyedCollections with UFIx keys, which are in turn Collections of (UFix :a) tuples.

(filter (fn (index-value) (>= (fst index-value) 0))) my-list)

That's obviously untenable as a solution for the library. The obvious answer, if you want to maintain the class hierarchy, is to add a filter-values function to the KeyedCollection typeclass. Then you can just call this on your list:

(filter-values (fn (index-value) (>= (fst index-value) 0))) my-list)

And that's not so bad. The filter-values function should probably exist in the KeyedCollection typeclass anyway, so that's fine. But it does make using LinearCollections more awkward - especially because this pattern will repeat itself for many of the original Collection methods.

• remove-duplicates would be useless on LinearCollections, because you could never have a duplicate (key value) since LinearCollections only have unique keys, so you would need remove-duplicate-values
• contains-elt? would look for key/value pairs, so you would need contains-value?
• etc.

For KeyedCollections, a more specialized and less commonly used datatype, all of these functions should exist. They are a more flexible datatype and they'll incur extra complexity for it. But, LinearCollections are the most used and should probably be the simplest of the types of Collections.

---

One solution is to break the hierarchy up so that KeyedCollection and LinearCollection are both Collection instances, but LinearCollections are not KeyedCollection instances.

A second solution is to break it up so that a LinearCollection is a KeyedCollection and a Collection, but a KeyedCollection and a Collection have no relationship.

Either way, there are going to need to be some redundant functions defined.

---

I'm currently leaning towards the second solution, because I imagine it would be useful in more scenarios to perform operations like splitting an ordered map than it would be to treat a map like a generic collection of tuples.

[slburson]

If there's anything I can do to make the FSet collections more useful to you, please file an issue.

[Jason94]

Thank you! From what I recall, the main hurdle to implementing Coalton collections as wrappers on FSet collections is the generic method used for ordering. There's probably a sound way to bridge that to the Coalton Ord typeclass, and to be fair it's probably easier than implementing complex collections from scratch! Other than that, it's a good idea.

When we get to some of the missing collections, I'll certainly file an issue if there's anything that would help us.

[stylewarning]

Threading through a generic function will not work because we may have types erased. There is no guarantee we will have classes to dispatch on. Two challenges:

• we would need a "back door" alternative to the data structure that doesn't use GFs. This may or may not be easy.

• we would desire (but not necessarily absolutely require) the ability for Coalton to optimize with e.g. monomorphization. This is an impossible ask without FSet being implemented in Coalton.

[slburson]

The whole task of adding a GF-free path is a fair amount of work, which is why I've been putting it off despite multiple people asking me for it 😸 There are two subtasks:

• adding a comparator parameter to all the internal WB-tree functions that require it, and calling that instead of compare

• adding code to the API layer to deal with collections with custom comparators

The second part looks to be the larger, because it involves things like handling equality, set union, etc. when the two operands use different comparators. In some cases this will just be an error; in others, I'll have to write generic O(n log n) implementations, none of which are complicated, but all have to be written and tested.

However, technically, you only need the first part. You could use the internal tree implementations directly, with your own API layer. This would let you elide the consing of the wrapper object on updates, giving a small performance improvement.

I don't see much point to recoding the internals in Coalton; unless I'm missing something, there's little to be gained from monomorphization at that level.

[slburson]

I have FSet support for user-supplied comparison functions pretty close to complete, in a PR. I'm still polishing and adding tests, but I think it's time to invite you to have a look. If the way I've done this doesn't work for you somehow, this is your chance to get it changed before I merge the PR.

[YarinHeffes]

@Jason94

I'm a fan of the organization that you're proposing and I like some of the conventions you introduced in your PR, like # to indicate that a function is unsafe.

I had a different view on how type classes would be mixed into this that I wanted to suggest. I like the idea of sorting our collections into files and directories with consistent naming conventions. However, I don't think that we should use type classes to describe the inheritance, for example, from Collection -> ImmutableCollection -> List. Rather, I think each collection should have it's own identity and it should implement type classes where appropriate to enforce consistent naming. For example, consider the following

;; basics:

;; could be implemented by List, HashSet, HashMap, OrdTree, OrdMap, etc.
(define-class (Eq :elt => Set :col :elt (:col -> :elt))
  (empty :col)
  (union (:col -> :col -> :col))
  (intersection (:col -> :col -> :col))
  (difference (:col -> :col -> :col))
  (element-of? (:col -> :elt -> Boolean)))

;; could be implemented be (Cell (List :t)), Vector, etc.
(define-class (Stack :col :elt (:col -> :elt))
  (empty? (:col -> Boolean))
  (push! (:elt -> :col -> Unit))
  (peak (:col -> Optional :elt))
  (pop! (:col -> Optional :elt)))

;; slightly more experimental:

(define-class (Iterable :col :elt (:col -> :elt))
  (%docollection (:col -> (:elt -> Unit) -> Unit))
  (%somecollection (:col -> (:elt -> Boolean) -> Boolean))
  (%everycollection (:col -> (:elt -> Boolean) -> Boolean))
  (%bestcollection (:col -> (:elt -> :elt -> Boolean) -> :elt)))

(declare contains? ((Eq :elt) (Iterable :col :elt) => :col -> :elt -> Boolean))
(define (contains? col elt)
  (somecollection (e col) 
    (==  e elt)))

There are just some features that are unique to certain data structures. For example, head and tail is unique to linked-lists and suggests something about the way linked-lists should be used.

What do you think?

[YarinHeffes]

These are just my thoughts.

Re. having classes like Stack, Set, Indexed vs. LinearCollection: There are two benefits to splitting it up. First, the class methods are intuitive from the name, like Stack implementing push! and pop!. Second, some collections don't implement all of these functions, such as OrdTree and a (not yet in existence) HashSet implementing Set but not Stack. Similarly, a user can define custom collections that use the same syntax as standard library collections without having to implement every method, for example an abstract set like the one below. We do the same with with our math library, with classes like Num, Reciprocable, Trigonometric, etc.

(define-type (AbstractSet :t)
  EmptySet
  (PredSet (:t -> Boolean))
  (FiniteSet (List :t))
  (UnionSet (AbstractSet :t) (AbstractSet :t))
  ...)

Also, I think this might be easier to implement incrementally, but of course just because it's easier doesn't mean it's better.

Re. supporting head and tail on vector, etc.: you're absolutely right. head/tail are more "natural" for List but they are used with many other collections, and of course it's better to support them. I could recommend using (index vector 0) and (subseq vector 1 0) instead, and maybe that's the style I prefer, but that shouldn't be forced on the programmer.

[Jason94]

I definitely agree that my setup makes it hard to bring new collections in, because they need basically all of the functionality at once. For List and Vector, which are pretty simple, that wasn't that hard.

I also agree that if there are any "functional" fault lines, where there are concrete collections then we should split that up. I think I've achieved that, but if you can think of any concrete collections that could implement some but not all of the LinearCollection class, for example, that would be a sign to split that one up.

Our difference in thinking might be what I mean by "functional fault" and "concrete collection." A Stack, for example, isn't really a concrete collection in the way that a Vector, List, Doubly linked list, etc are. A Stack is really an interface on top of some concrete collection implementation - you could use a Vector or a mutable linked list to implement a stack. But you couldn't use a Vector to implement a list.

Thinking about it this way, I don't see the value in splitting up the classes across different conceptual interfaces, because that's mixing two different concerns: data structure interfaces and collections. However, suppose that for some reason only half of the MutableLinearCollection class could be implemented by a mutable singly linked list. That would be s good reason to split that class into two.

[Jason94]

I see where you're coming from, because the approach you're describing is more in line with how things like the Monad class hierarchy is designed. I guess I think that collections have different design goals: more focus on usability and ergonomics, because it's such an important part of the nuts and bolts of implementing functional programs.

[Jason94]

As for the hierarchy, I could go either way on that. It turns out that you can't treat a linear collection as a map from ordinals to elements (it causes some type mismatches), so the chart I'd posted wouldn't work anyway. The only benefit i can see of making all LinearCollections have to be Collections is that it saves you having to type the second class for generic functions where you need both interfaces.

[YarinHeffes]

Apologies for the delay, I spent some time thinking about this and tinkering with some design ideas.

First, you're right, I am thinking about this like the Monad hierarchy and also, especially, the math type classes like Num, Reciprocable, Exponentiable, etc. That is more aligned with how I think about type classes.

The nice thing about the math type classes is that if I create my own data type and I just need simple arithmetic, I can just instance Eq, Num, and Reciprocable to get going.

That's one of the reasons that my vision for the collections type classes is a series of type classes that are minimally interdependent and as sparse as possible.

By minimally interdependent, I mean that as a user, I should have to implement the minimal number of dependencies to get at a feature that I want, meaning that all and only the relevant methods will be implemented.

By sparse, I mean that we define the most generic version of a method, and then define a function on the class that is more specific.

I'll give an example that reflects both of these points below. Note that we are able to define head and member? without implementing them as methods or constraining type class definitions on Eq, for example. There still is a hierarchy here, but it's much more shallow, and if I want, for example, member?, I only need to implement four methods.

Some type classes that I would want implemented for collections include Sequence, Stack, Queue, Set, and Map.

;; Classes

(define-class (Sequence :c :e (:c -> :e))
  (index (:c -> UFix -> Optional :e))
  (subseq (:c -> UFix -> UFix -> Optional :e)))

(define-class (Sequence :c :e => ImmutableSequence :c :e (:c -> :e))
  (insert (:c -> UFix -> :e -> Optional :c)))

(define-class (Sequence :c :e => MutableSequence :c :e (:c -> :e))
  (insert! (:c -> UFix -> :e -> Optional :c)))

(define-class (Sequence :c :e => FiniteSequence :c :e (:c -> :e))
  (length (:c -> UFix))
  (search-from (UFix -> :c -> (:e -> Boolean) -> Optional UFix)))

(define-class (FiniteSequence :c :e => ImmutableFiniteSequence :c :e (:c -> :e))
  (concatenate (:c -> :c -> :c))
  (sort-by ((:e -> :e -> Boolean) -> :c -> :c)))

(define-class (FiniteSequence :c :e => MutableFiniteSequence :c :e (:c -> :e))
  (concatenate! (:c -> :c -> :c))
  (sort-by! ((:e -> :e -> Boolean) -> :c -> :c))
  (copy (:c -> :c)))

;; Functions (class extensions)

(declare head (Sequence :c :e => :c -> Optional :e))
(define (head sequence)
  (index sequence 0))

(declare tail (FiniteSequence :c :e => :c -> Optional :c))
(define (tail sequence)
  (subseq sequence 1 (length sequence)) ; Currently, does not work because of a bug in functional dependencies.

(declare find-from ((Eq :e) (FiniteSeqeunce :c :e) => UFix -> :c -> :e -> Optional UFix))
(define (find-from n sequence element)
  (search-from n sequence (== element)))

(declare find ((Eq :e) (FiniteSeqeunce :c :e) => :c -> :e -> Optional UFix))
(define (find sequence element)
  (find-from 0 sequence element))

(declare member? ((Eq :e) (FiniteSeqeunce :c :e) => :c -> :e -> Optional UFix))
(define (member? sequence element)
  (some? (find sequence element)))

Now, the collections themselves, I still think can be organized according to your tree or something similar.

- coalton
|-library
||-collections
|||-mutable-collections
|||||-mutable-sets
|||||-mutable-sequences
||||||-vector.lisp
||||||-array.lisp
|||||-mutable-maps
||||||-hashtable.lisp
|||-immutable-collections
||||-immutable-sets
|||||-hashset.lisp
|||||-ordset.lisp
||||-immutable-sequences
|||||-list.lisp
|||||-seq.lisp
||||-immutable-maps
|||||-hashmap.lisp

But I still don't think that the file and package hierarchies need to match/should match the type class structure.

[Jason94]

Dropping a few recent relevant PR's here:

Linear Collections:
#1707
#1701
#1337

Map Collections:
#1709
#1697