Butterflys, stamps, coins

Yep, we're going to talk about collections.

  (defprotocol Collection
    (empty? [coll])
    (empty [coll])
    (count [coll])
    (conj [coll x])
    (filter [coll f])
    (reduce [coll x f]))

Those are the functions that data types which hold some number of other values can implement. Let's run through them quickly. If you're familiar with Clojure, these should be obvious.

empty?

If the collection coll has no values inside it, this function should return <Maybe coll>. But if it contains values, it should return nothing.

empty

This should return a value of the same type as coll but that contains no values.

count

This should return the number of values contained in coll. Always 0 or more.

conj

This should create a new value of the same type as coll but with x added to the collection.

filter

This applies the function f to each of the values contained in coll, returning either a nothing value or a Maybe value which contains some value. The result is a collection of the same type as coll but that only contains the values from coll that f does not return nothing for. Notice that the values in the new collection come from coll. They are not the results of appling f to the values in coll.

reduce

Takes a collection, an initial value and a function. It calls the function once with the initial value and an item from the collection. Then it calls the function again with the result of the first invocation and another value in the collection. It proceeds to iterate through the rest of the collection, each time calling the given function with the value returned from the last invocation and a new item from the collection. If the initial collection is empty, the given function is not called and the initial value is returned.

In all of these functions, there is no concept of an ordering of the values in the collection.

Sequences

For collections that do have some concept of an ordering of the contents, the Seqable protocol defines some functions

  (defprotocol Seqable
    (seq [coll])
    (vec [coll])
    (first [coll])
    (rest [coll])
    (last [coll])
    (butlast [coll])
    (split [coll n])
    (split [coll n prefix])
    (split-with [l pred prefix])
    (split-with [l pred])
    (reverse [coll])
    (to-str [coll]))

Again, most of these should be familiar to Clojure programmers.

seq

Produces a list from an ordered collection

vec

Produces a vector from an ordered collection

first

Returns a Maybe value that contains the first item in the collection, or nothing if the collection is empty.

rest

Returns the collection with all of the contents except for the first one. Possibly returns an empty collection.

last

Returns a Maybe value that contains the last item in the collection, or nothing if the collection is empty.

butlast

Returns the collection with all of the contents except for the last one. Possibly returns an empty collection.

split

This shows how to specify multiple arities for a protocol function. The 2 argument arity would be the most commonly used. The 3 argument arity would most likely be used in the implementation of the 2 argument arity.

split returns a list of 2 collections, the first item in the list is a new collection with the first n items from the original collection. The second item in the returned list is a new collection of the remaining items. If the original collection has fewer than n items, the second item in the list is an empty collection.

split-with

Similar to split but uses a predicate function instead of an integer to determine where to split the collection at.

reverse

Produces a new collection with the contents in the reverse order as the original.

to-str

Constructs a string from the string representations of each of the items from the collection in order.

Indexed

And there's one other aspect of collections, which mostly arise because of the Vector type. And that is one whose contents are accessed by an integer index.

  (defprotocol Indexed
    (nth [coll n])
    (store [coll n v]))

nth

Returns a Maybe value that contains the nth item in the collection, or nothing if the collection has fewer than n items.

store

Returns a Maybe value that contains a new collection with the value at the nth location replaced. Or nothing if the collection has fewer than n items.

Failure

It's interesting to notice how the absence of a nil/null value in Toccata forces the values returned by some functions to be of the Maybe type so they can indicate failure. I've found this has implications in the code I write. I can still screw things up and try to call extract, but I have to think about it every time. I can't just blithely assume I'll get back a value and leave a hidden landmine that will blow up in my face with an NPE at a later time.

I also like how these functions can be implemented for new collection types. For example, a tree data structure could implement reduce that would let you traverse it's leaves in some order.