Dixin's Blog

As discussed in all the previous functor parts, a functor is a wrapper of a object with a “Select” ability to preserve a morphism to another‘

Given 2 categories C and D, functors C → D forms a functor category, denoted D^C:

If F: C -> D and G: C -> D are both functors from categories C to category D, a mapping can be constructed between F and G, called natural transformation and denoted η : F ⇒ G.

Tuple<> looks like the simplest functor by just wrapping a value. It is most close to the Identity functor of Haskell. Its Select functions are:

A simple functor in DotNet category is Lazy<>. Its Select functions can be easily implemented:

A functor F: C → D is a structure-preserving mapping from category C to category D:

An individual monoid (T, ⊙, I) can be a category M:

A monoid, denoted a 3-tuple (M, ⊙, I), is a set M with

This post and the following posts will introduce category theory and its important concepts via C# and LINQ, including functor, applicative functor, monoid, monad, etc. Categories were first introduced by Samuel Eilenberg and Saunders Mac Lane in 1942–45. It might be tedious, as Wikipedia pointed:

p is the fixed point of function F if and only if:

Iota is an esoteric programming language with minimum elements but still Turing-complete. Iota's universal combinator is:

The previous part shows SKI calculus is untyped and strongly typed C# implementation does not work. So here comes the SKI in untyped C#:

As mentioned in a fundamental part, combinator is a special kind of lambda expression without free variables. So combinatory logic (introduced by Moses Schönfinkel and Haskell Curry) can be viewed as a variant of lambda calculus.

So far a ton has been encoded. Here is a summary.

In lambda calculus, a signed number (integer) can be represented by a Church pair (2-tuple) of Church numerals (natural numbers):

A third way to encode Church list, is to use fold function (also called aggregate in C#/.NET):

Previous part encoded Church list with one Church pair (2-tuple) as a list node. An alternative way is to use 2 tuples as a node, one wrapping the other.

This part will demonstrate how to use lambda expressions to encode another data structure - list (Church list in lambda calculus or LinkedList<T> in .NET).