What is an anamorphism, and how does one look like in C#?

Question

I am trying to wrap my head around the concept of anamorphism.

In functional programming, an anamorphism is a generalization of the concept of unfolds on lists. Formally, anamorphisms are generic functions that can corecursively construct a result of a certain type and which is parameterized by functions that determine the next single step of the construction.

Its dual, catamorphism, is nicely described in this post: What is a catamorphism and can it be implemented in C# 3.0?.

A nice example of catamorphic behavior in C# is the LINQ's Aggregate method.

What would an anamorphic equivalent be? Is it correct to think of a pseudo-random number generator Random as an anamorphic construct or should the process of unfolding always include an accumulator function like the one below (code snippet taken from Intro to Rx)?

IEnumerable<T> Unfold<T>(T seed, Func<T, T> accumulator)
{
    var nextValue = seed;
    while (true)
    {
        yield return nextValue;
        nextValue = accumulator(nextValue);
    }
}

The Wikipediaentry says Zip is an example. Which takes two sequences and "zips" them together. LINQ has a function called Zip. The example you provided suits the definition aswell. However there is no "finished" predicate, which is stated as optional. — CSharpie, Jun 15 '15 at 12:10
According to http://enumeratethis.com/category/c/, `Observable.Generate` is an example of anamorphism. Though, like Aggregate, then aren't true implementations as they are not truly generic and are specific to certain data types. — David Arno, Jun 15 '15 at 12:17

score 8 · Accepted Answer · edited May 23 '17 at 12:08

LINQ's Aggregate method has the signature

T Aggregate<T>(IEnumerable<T> source, Func<T, T, T> accumulator)

So the corresponding unfolding would be

IEnumerable<T> Unfold<T>(T seed, Func<T, Nullable<T>> accumulator)
{
    Nullable<T> nextValue = new Nullable<T>(seed);
    while (nextValue.HasValue)
    {
        yield return nextValue.Value;
        nextValue = accumulator(nextValue);
    }
}

In pure functional programming, folding and unfolding must include a deterministic function. For C#'s System.Random, this is true if you consider its deterministic internals as an implicit function, as you suggest. One could recreate this precise PRNG using Unfold, so it may not use folding but be functionally and semantically equivalent to a fold.

The two folding and unfolding of lists above are special cases of the more general folding of lists:

B Fold<A, B>(Func<A, B, B> acc, B seed, IEnumerable<A> source);
IEnumerable<B> Unfold<A, B>(Func<A, Nullable<Tuple<A, B>>> acc, A seed);

In LINQ, this generality is present in other combinators such as Select.

As Brian's answer to the question What is a catamorphism and can it be implemented in C# 3.0?:

Catamorphisms in general refer to the pattern of folding for an arbitrary data type.

Likewise, one may construct anamorphisms on binary trees in C#:

public class Tree<T> {
    public T Data { get; private set; }
    public Tree<T> Left { get; private set; }
    public Tree<T> Right { get; private set; }

    public Tree(T data, Tree<T> left, Tree<T> right)
    {
        this.Data = data;
        this.Left = left;
        this.Right = right;
    }
}

public struct Triple<T> {
    public T Result;
    public Nullable<T> LeftSeed;
    public Nullable<T> RightSeed;
}

public static Tree<T> Unfold<T>(Func<T, Triple<T>> water, T seed)
{
    Triple<T> tmp = water(seed);
    Tree<T> leftTree = null;
    Tree<T> rightTree = null;

    if (tmp.LeftSeed.HasValue)
        leftTree = Unfold<T>(water, tmp.LeftSeed.Value);

    if (tmp.RightSeed.HasValue)
        rightTree = Unfold<T>(water, tmp.RightSeed.Value);

    return new Tree(tmp.Result, leftTree, rightTree);
}

Here is a rather silly example of how to build the Collatz numbers in this XKCD strip:

public static Tree<int> CollatzTree(int max)
{
    return Unfold<int>(i => {
        if (i >= max) return new Triple(i, null, null);
        int? tpo = (i - 1) % 3 == 0 ? (i - 1) / 3 : null;
        return new Triple(i, tpo, 2*i);
    }, max);
}

Here is a heteronormative example of building a family tree:

public static Tree<Person> FamilyTree(Person youngestPerson) {
    return Unfold<Person>(child => {
        Person mother = GetMotherFromDatabase(child);
        Person father = GetFatherFromDatabase(child);
        return new Triple(p, mother, father);
    }, youngestPerson);
}

I didn't run any of the code above so there may be errors.

I need to use Trees more often. – CSharpie Jun 16 '15 at 14:37 — CSharpie, Jun 16 '15 at 14:37

What is an anamorphism, and how does one look like in C#?

1 Answers1