Discosultan - 1 month ago 8x
C# Question

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

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);
}
}
``````

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.