Functional Collections + Delegates

I haven't decided if i want to my collections totally functional or not.  However, it's clear to me that they will have some functional properties to them.  For example, people need to be comfortable using folds or maps over these collections as they are far too powerful.  However, it's not clear if persistent data structures are worth the implementation complexity.  So i might end up with two hierarchies.  A purely functional hierarchy, and a purely OO hierarchy.  However, in any event I know that I will need to following functional data types:

delegate B Function<A,B>(A a);

delegate A Creator<A>();

delegate void Operator<A>(A a);

Users of functional langauges will recognize this simply as: 

'a => 'b

() => 'a

'a => ()

Note that Creator and Operator are simply degenerate cases of Function, namely Function<void,A> and Function<A,void>. However, since void is not a valid type in C# we need to explicitly include these.

I was considering including

delegate bool Predicate<A>(A a);

However, the risk with that is that while it reads better,

Predicate<A> != Function<A,true>

So you can't interchange them. I see that as being a problem in the future. So rather than introducing Predicate, i will stick to Function<A,bool>

Unfortunately, i see no way to test these. Like interfaces they are just a signature and so you cannot test without an actual implementation. However, unlike interfaces it does not even seem like you can place invariants on a delegate. In the last blog I showed how i could write tests to ensure that Add/Empty maintained certain invariants. However, because i only have one signature I don't see what invariants I can have. Are delegates testable?