Polymorphic higher order functions

Its been a while since my last posting. That's because a lot of changes have been happening under the hood. Objects (vectors and hashtables) now have printed representations, higher order functions are now polymorphic - they can be used on lists, vectors and hashtables, the diagnostic messages are now more extensive and several hashtable bugs have been fixed. There is a fairly serious language departure from standard Scheme which doesn't have polymorphic operators, but I chose this for ease of use. Here, I describe what's available as of revision 21 in the svn repository.

The following operations are now applicable to lists, vectors and hashtables. Wherever you see collection, it means you can use any of those. -

(map (fn (x) ...) collection)

Creates a structurally similar collection with all the values transformed using the given function. The hashtable keys are not processed.

(join list1 list2 ...)
(join vector1 vector2 ...)
(join hashtable1 hashtable2 ...)

Concatenates all the objects into a single collection. All objects must be of the same type. Lists get concatenated into a single list, vectors get concatenated into a single vector. For hashtables, a union hashtable is created with all the key-value pairs of all the hashtables.

If two hashtables have the same key, the value for that key will be the value in the hashtable that's later in the argument sequence. You can influence this by supplying an optional reduction function as the first argument to join. The default behaviour is as though the reduction function is (fn (v1 v2) v2).

(length collection)

You can use the same length function to get the size of any data structure. A synonym size is available as well for clarity.

(find item collection)

Finds the item in the given collection and returns something that you can use to locate the item within the collection, or () if the item cannot be found. In the case of lists, it returns the remainder of the list starting from the object. In the case of vectors, it returns the index of the item. In the case of hashtables, it returns the key for which the given item is the value.

(reduce (fn (acc x) ...) initial collection)

Uses the given reduction function and reduces the given collection of values to a single value. This is the foldl operation that must be familiar to functional programming afficionados. This function only uses the values in the data structures. The keys of a hashtable, for example, are not touched.

(for-each func collection)

Invokes the function for each entry in the data structure. The result value is always (). The function is expected to have the signature -

(fn (obj) ...)

It is to be noted that the iteration always happens over the value objects. You don't have access to the keys of hashtables or the indices of vectors when using for-each. For a more generalized iteration construct, see collect below. This (new) behaviour is since v120.

(andmap predicate collection)

Returns T if all elements satisfy the predicate and () if even one doesn't. The signature of the predicate has the same signature constraints as that for for-each.

(ormap predicate collection)

Returns () if none of the elements satisfy the predicate. If even one satisfies the predicate, returns a reference into the data structure (like find) using which you can locate the element. The predicate signature constraints are the same as for andmap and for-each. You can use ormap as a generalized version of find.

(collect collection predicate mapper [reduction-fn])

This is an experimental generalized construct that fuses filtering, mapping and reduction operations into a single loop. The predicate selects elements from the collection, the mapper transforms the elements and the (optional) reduction-fn combines multiple values into a single entry in the result.

The predicate has to have the signature (fn (x) ...) for lists. For vectors, it is expected to have the signature (fn (index . value) ...) and for hashtables, it must be (fn (key  . value) ...). If you want to run the mapper on every element, you can simply pass () as the predicate - indicating that you don't wish to do the test.

Once an element passes the predicate test, it is passed to the mapper function. If no mapper function is given, the identity map is assumed and in this case collect behaves like a pure filter.

1. For lists, the mapper function should have the usual signature (fn (x) ...).


2. For vectors, the signature is expected to be (fn (index . value) ...). The index will be the filtered index of the value and not the original index in the vector. The mapper function is expected to return a pair of the form (result-index . result-value). The result is used to determine where in the result vector the result-value should be placed. The result vector is automatically resized to fit the set of returned indices. The (optional) reduction-fn is used to determine how to combine multiple values if more than one value is mapped to the same result index.


3. For hashtables, the case is similar to that of vectors, except that instead of index-value pairs, the mapper works with (key . value) pairs and is expected to return a (result-key . result-value) pair. The reduction function is also applied similar to the case of vectors.