Freigeben über

Unfold

  • Artikel

F# has a handy method called Unfold.  Think of it as the logical opposite of an Aggregate function.  Aggregates take a sequence of elements and convert them to a single element.  An unfold method will take a single element and turn it into a (potentially infinite) sequence of elements. 

The API is straight forward.  It takes two parameters

  1. A seed/start value
  2. A function which takes in a seed value and returns either an Empty option to indicate the end of a sequence or a value of Type tuple with two arguments.  The first is the next element in the sequence and the second is the next seed value passed into the function.

This is a very powerful function which allows you to quickly build all sorts of interesting functions.  Lets look at a potential implementation of Enumerable.Range as an unfold expression.

 public static IEnumerable<int> Range(int start, int count)
{
    return Enumerable.Unfold(
        start,
        x => x - start < count
            ? Option.Create(Tuple.Create(x, x + 1))
            : Option.Empty);
}

Not as efficient as the framework version of Range but a good mental exercise to get your head around using Unfold.  Implementing this method in C# is fairly straight forward.

 public static IEnumerable<TResult> Unfold<TSource, TResult>(
    TSource state, 
    Func<TSource, Option<Tuple<TResult, TSource>>> func)
{
    if (func == null)
    {
        throw new ArgumentNullException("func");
    }

    return UnfoldHelper(state, func);
}

private static IEnumerable<TResult> UnfoldHelper<TSource, TResult>(
    TSource state, 
    Func<TSource, Option<Tuple<TResult, TSource>>> func)
{
    do
    {
        var result = func(state);
        if (!result.HasValue)
        {
            break;
        }

        yield return result.Value.First;
        state = result.Value.Second;
    } while (true);
}

Comments