Archives

Category Theory via C# (8) Advanced LINQ to Monads
Monad is a powerful structure, with the LINQ support in C# language, monad enables chaining operations to build fluent workflow, which can be pure. With these features, monad can be used to manage I/O, state changes, exception handling, shared environment, logging/tracing, and continuation, etc., in the functional paradigm.

Category Theory via C# (7) Monad and LINQ to Monads
As fore mentioned endofunctor category can be monoidal (the entire category. Actually, an endofunctor In the endofunctor category can be monoidal too. This kind of endofunctor is called monad. Monad is another important algebraic structure in category theory and LINQ. Formally, monad is an endofunctor equipped with 2 natural transformations:

Category Theory via C# (6) Monoidal Functor and Applicative Functor
Given monoidal categories (C, ⊗, I_{C}) and (D, ⊛, I_{D}), a strong lax monoidal functor is a functor F: C → D equipped with:

Category Theory via C# (5) Bifunctor
A functor is the mapping from 1 object to another object, with a “Select” ability to map 1 morphism to another morphism. A bifunctor (binary functor), as the name implies, is the mapping from 2 objects and from 2 morphisms. Giving category C, D and E, bifunctor F from category C, D to E is a structurepreserving morphism from C, D to E, denoted F: C × D → E:

Category Theory via C# (4) Natural Transformation
If F: C → D and G: C → D are both functors from categories C to category D, the mapping from F to G is called natural transformation and denoted α: F ⇒ G. α: F ⇒ G is actually family of morphisms from F to G, For each object X in category C, there is a specific morphism α_{X}: F(X) → G(X) in category D, called the component of α at X. For each morphism m: X → Y in category C and 2 functors F: C → D, G: C → D, there is a naturality square in D:

Category Theory via C# (3) Functor and LINQ to Functors
In category theory, functor is a mapping from category to category. Giving category C and D, functor F from category C to D is a structurepreserving morphism from C to D, denoted F: C → D:

Category Theory via C# (2) Monoid
Monoid is an important algebraic structure in category theory. A monoid M is a set M equipped with a binary operation ⊙ and a special element I, denoted 3tuple (M, ⊙, I), where

Category Theory via C# (1) Fundamentals
Category theory is a theoretical framework to describe abstract structures and relations in mathematics, first introduced by Samuel Eilenberg and Saunders Mac Lane in 1940s. It examines mathematical concepts and properties in an abstract way, by formalizing them as collections of items and their relations. Category theory is abstract, and called "general abstract nonsense" by Norman Steenrod; It is also general, therefore widely applied in many areas in mathematics, physics, and computer science, etc. For programming, category theory is the algebraic theory of types and functions, and also the rationale and foundation of LINQ and any functional programming. This chapter discusses category theory and its important concepts, including category, morphism, natural transform, monoid, functor, and monad, etc. These general abstract concepts will be demonstrated with intuitive diagrams and specific C# and LINQ examples. These knowledge also helps building a deep understanding of functional programming in C# or other languages, since any language with types and functions is a categorytheoretic structure.

Lambda Calculus via C# (8) Undecidability of Equivalence
All the previous parts demonstrated what lambda calculus can do – defining functions to model the computing, applying functions to execute the computing, implementing recursion, encoding data types and data structures, etc. Lambda calculus is a powerful tool, and it is Turing complete. This part discuss some interesting problem that cannot be done with lambda calculus – asserting whether 2 lambda expressions are equivalent.

Lambda Calculus via C# (7) Fixed Point Combinator and Recursion
p is the fixed point (aka invariant point) of function f if and only if:

Lambda Calculus via C# (6) Combinatory Logic
In lambda calculus, the primitive is function, which can have free variables and bound variables. Combinatory logic was introduced by Moses Schönfinkel and Haskell Curry in 1920s. It is equivalent variant lambda calculus, with combinator as primitive. A combinator can be viewed as an expression with no free variables in its body.

Lambda Calculus via C# (5) List
In lambda calculus and Church encoding, there are various ways to represent a list with anonymous functions.

Lambda Calculus via C# (4) Tuple and Signed Numeral
Besides modeling values like Boolean and numeral, anonymous function can also model data structures. In Church encoding, Church pair is an approach to use functions to represent a tuple of 2 items.

Lambda Calculus via C# (3) Numeral, Arithmetic and Predicate
Anonymous functions can also model numerals and their arithmetic. In Church encoding, a natural number n is represented by a function that calls a given function for n times. This representation is called Church Numeral.

Lambda Calculus via C# (2) Church Encoding: Boolean and Logic
Lambda calculus is a formal system for function definition and function application, so in lambda calculus, the only primitive is anonymous function. Anonymous function is actually very powerful. With an approach called Church encoding. data and operation can be modeled by higherorder anonymous functions and their application. Church encoding is named after Alonzo Church, who first discovered this approach. This part discusses Church Boolean  modeling Boolean values and logic operators with functions.

Lambda Calculus via C# (1) Fundamentals
Lambda calculus (aka λcalculus) is a theoretical framework to describe function definition, function application, function recursion, and uses functions and function application to express computation. It is a mathematics formal system, but can also be viewed as a smallest programming language that can express and evaluate any computable function. As an universal model of computation, lambda calculus is important in programming language theory, and especially it is the foundation of functional programming. The knowledge of lambda calculus greatly helps understanding functional programming, LINQ, C# and other functional languages.

Functional Programming and LINQ via C#