This draft PR is a start to implementing the proposal in this discussion. The code mostly matches the API described in the proposal, with small differences as development arose.

Not mentioned in the discussion, but I've also started on a macro-based test suite to verify that all collections conform to the Collections contract.

Will resolve: #1303

Depends on: #1342

Example Code

The following snippet demonstrates usage of the new API. Note the creation of functions generic over LinearCollections, calling the same functions directly on Lists and Vectors, and that the entire collections API is able to be imported directly through coalton-prelude.

(coalton-toplevel
  (declare push-end-tens (LinearCollection :m => :m UFix -> :m UFix))
  (define (push-end-tens coll)
    (let result = (cel:new coll))
    (for x in (iter:range-increasing 10 10 91)
      (cel:write! result (push-end x (cel:read result))))
    (cel:read result))
  
  (declare push-end-tens! (MutableLinearCollection :m => :m UFix -> :m UFix))
  (define (push-end-tens! coll)
    (for x in (iter:range-increasing 10 10 91)
      (push-end! x coll))
    coll))

(coalton-toplevel
  (define vec (the (Vector UFix) (new-from 4 (fn (x) x))))
  (define lst (the (List UFix)   (new-from 4 (fn (x) x)))))

(coalton
  (progn
   (push 100 vec)
   (push 100 lst)
   (head vec)
   (head lst)))

(coalton
  (progn
    (traceobject "Push tens onto vec" (push-end-tens vec))      ; -> Push tens onto vec: #(0 1 2 3 10 20 30 40 50 60 70 80 90)
    (traceobject "Push tens onto list" (push-end-tens lst))     ; -> Push tens onto list: (0 1 2 3 10 20 30 40 50 60 70 80 90)
    (traceobject "Original vec" vec)                            ; -> Original vec: #(0 1 2 3)
    (traceobject "Original list" lst)                           ; -> Original list: (0 1 2 3)
    (traceobject "Push! tens onto vec" (push-end-tens! vec))    ; -> Push! tens onto vec: #(0 1 2 3 10 20 30 40 50 60 70 80 90)
    (traceobject "Original vec" vec)))                          ; -> Original vec: #(0 1 2 3 10 20 30 40 50 60 70 80 90)

;; Doesn't compile:
; (coalton
;   (push-end-tens! lst))

Progress

Goals for this pull request:

• Collection typeclass
• KeyedCollection typeclass
• LinearCollection typeclass
• Extend List behavior to satisfy typeclasses
• Extend Vector behavior to satisfy typeclasses
• Create a collections testing suite
• (Partial) Create and link to a barebones collections doc page with a quick note at the top and tables with all of the functions

Work that I believe should be left to a future PR:

• Modify the test suite so it uses elements of a type provided by the collection's tests, to be able to accommodate ex. Strings (Collection Char), Maps (Collection (Tuple k v)), etc.
• Bring String into the collection suite as collections/mutable/String, and implement the (mutable) linear collection typeclasses
• Extend OrdMap
• Extend HashTable
• Extend Seq
• Create an immutable Set collection
• Flesh out the documentation page with more information about the typeclasses, how to write functions generic on collection type, how to add a new collection, etc.

Open Questions

I'm posting here to get general feedback on the API as I continue, and also to request input on a few specific questions.

1. Start with List & Vector, or go all in?

OrdMap and Seq will probably require substantial work to get them to feature parity with the other Collections, since the underlying data structures are much more complicated. (AT least, if done efficiently) HashTable might be easier. List and Vector are basically already done. We could release the Collections API just covering List and Vector initially, and then release PR's to bring the others up to parity afterwards. Or we could wait to release them all at once.

2. How much effort to put into backwards compatibility?

The new API is a big departure in behavior, function naming, and packaging. It will certainly break old code. It will probably require broad but safe refactors (mostly renaming functions) for any existing Coalton code. The discussion proposed a deprecation warning scheme. The current PR doesn't go that far, but does at least preserve the old packages as duplicate files in the meantime.

Release Notes

• Overall, migrating should be easy, with a few footguns. The now-deprecated coalton-library/list and coalton-library/vector still exist, and are largely unchanged, so that code can continue using the old function names & signatures.
• The coalton-library/collections/classes package adds a few dozen new function symbols into prelude, which could break existing code if they're not shadowed.
• vector:pop! and vector:push! - Previously list:push pushed to the front and vector:push! pushed to the end. The new API has been unified so that any unqualified function manipulates the head (push, pop!, etc) and end functions are specified (push-end, pop-end!, etc). add and add! are new functions on the Collection typeclass that requires the element be added, but it doesn't specify where, to allow the datatype to add it in the most efficient way (and to accommodate non-linear collections like sets).
  • Most usages should probably switch to add/add! unless you care about the ordering.
  • Any existing usage of vector:pop! or vector:push! needs to switch to vector:pop-end! and vector:add!/vector:push-end!.
• collections-library/list is no longer re-exported into coalton-prelude. Most of the functions from that package have an exact or close analogue in coalton-library/collections, which is re-exported from prelude.
  • For the remaining functions, existing code can :use collections-library/collections/immutable/list without any issues to restore those functions to scope.