Functional Lists in C# and in the Cat Interpreter
I’ve just finished implementing an optimized set of immutable (functional) list data types for the Cat interpreter (http://cat-language.googlecode.com/svn/trunk/FunctionalList.cs).
The library consists a base list class called CForEach, and a number of specializations of that class. Many operations return a new list of a different type that also inherits from ForEach. From a user standpoint though, you simply write everything in terms of CForEach. For example: if you call TakeN on a CArray you get back a CRangedArray. The classes are:
- CForEach - the base class.
- CConcatPair - the result of a concatenation operation.
- CEmpty - an empty list (there is only one: gNil)
- CUnit - a list optimized for one item
- CPair - a list optimized for two items
- CArray - a list which is implemented as an array (fast indexing, and counting)
- CRangedArray - a sub-range of a CArray
- CMappedForEach - the default result of a map operation
- CFilteredForEach - the default result of a filter operation
- CConsCell - a naive “cons” implementation of a functional list
- CRepeater - an infinite list containing the same value over and over
- CRangeGenerator - a list generated from a function on a range of indexes
- CGenerator - a list generated from successive application of a generation function (may be infinite).
These classes all provide the following interface:
- public abstract void ForEach(Accessor a)
- public virtual bool IsEmpty()
- public virtual int Count()
- public virtual object Fold(object init, FoldFxn f)
- public virtual CForEach Map(MapFxn f)
- public virtual object Nth(int n)
- public virtual Object First()
- public virtual CForEach Rest()
- public virtual Object Last()
- public virtual CForEach Filter(FilterFxn f)
- public virtual CForEach DropN(int n)
- public virtual CForEach TakeN(int n)
- public virtual CForEach TakeRange(int first, int count)
- public virtual CForEach TakeWhile(FilterFxn f)
- public virtual CForEach DropWhile(FilterFxn f)
Notice that only “ForEach” is abstract. This means that by simply inheriting from CForEach and overriding the ForEach method, you get all of the other functionality for free. I have purposefully left out any generic parameters, for simplicity and the fact that I wanted a universal empty list. Feel free to implement your own.
This file is not bound to any C# module other than the System root module, and is completely uncoupled from the rest of Cat. I am hoping that some people can find the functional lists library useful in its own right.
The current revision of the Cat interpreter source code (155) is also compiling and seems to be working, though I have more testing to do.
April 21st, 2007 at 1:00 pm
Christopher,
Have you thought about balancing the internal (lazy) structures? For instance, if you concatenate N (10000) CUnit’s you will end up with essentially a linked list of N (10000) CConcatPairs so indexing or querying will become O(N).
April 21st, 2007 at 3:36 pm
Yes that is a good point and I have been thinking about doing that. There seems to be no reason not to. Another optimization I have been thinking about is also using vlists ( http://en.wikipedia.org/wiki/VList ) instead of cons cells. Any other ideas?
April 21st, 2007 at 7:26 pm
I am now also looking at adding CFlattenList and CUnflattenList so that “[cat] fold” and “[unit] map” can be dealt with in O(1) time.
April 21st, 2007 at 9:51 pm
Vlists have some drawbacks that balanced binary trees in general don’t have.
AVL trees (with a size member at each node) or other balanced trees have better overall performance. I have implemented an sized balanced binary implementation that is both simple and performant which I use for Enchilada.
Another trick that Enchilada uses is that it tries to balance any structure. For instance, the following linear expression:
[1;2;3] [4;5;6] + [7;8;9] + …. (etc)
.. becomes a balanced expression tree that can also can be dually interpreted as the following list:
[1;2;3;4;5;6;7;8;9;...]
April 23rd, 2007 at 6:29 pm
[...] non-trivial issue with the functional lists library I blogged about earlier is partial list traversal. Many common algorithms (such as get the n-th item) are guaranteed to [...]