A Map Function with O(1) Complexity
An interesting feature of Cat is that it is partially lazy: evaluation may not occur if there is no reason for it. This allows for some fun optimizations that have been traditionally the domain of fully lazy languages like Haskell. One example is the map function. The map function takes a list and a unary function, it then returns a new list that would result by transforming each value using the function. For example:
>> [1 2 3] list [2 *] map
stack: (2, 4, 6)
In Cat this function usually takes O(1) time because instead of iterating over all items, a new list object is generated. This list is a sub-type of list, and only performs the transformation as items in the list are requested.
If you are interested in this and other similar kinds of lazy optimizations for C# there is a functional lists library in the Cat source code in the file CatFunctionalList.cs.