LINQ Unfold Operator

In Scheme’s SRFI-1 List library there’s a fold and unfold function. The fold is similar to the Aggregate operator in LINQ. However, there doesn’t appear to be anything like an unfold in LINQ. What is it exactly? The Aggregate operator takes an IEnumerable and applies a Func to the elements until you get a single result value. The unfold operation takes a single value and returns an IEnumerable. I needed this because I wanted an easy way to get all the parent classes and interfaces for a type T.

/// seeds: the initial data to unfold
/// stop: if stop(seed) is True, don't go any further
/// map: transform the seed into the final data
/// next: generate the next seed value from the current seed 
public static IEnumerable<R> UnFold<T,R>(this IEnumerable<T> seeds, Predicate<T> stop, 
                                         Func<T,R> map, Func<T,IEnumerable<T>> next) {
	foreach (var seed in seeds) {
		if (!stop(seed)) {
			yield return map(seed);
			foreach (var val in next(seed).UnFold(stop, map, next))
				yield return val; 
		}
	}
}

I’m not too happy about this code, but it should probably work. Now to produce all the parents of a type T:

var parents = new[]{someType}.UnFold(t => t == null, t => t, 
                                     t => t.GetInterfaces().Concat(new[]{t.BaseType}))
                             .Distinct();

For type theory nerds this is called an anamorphism, which is the dual of a catamorphism. There’s a way to generalize this to arbitrary recursive data structures, described in the paper “A Fold For All Seasons” (PDF link). I’ll leave it to someone else to generalize this beyond IEnumerable.

Advertisements