Category Theory via C# (1) Fundamentals

[LINQ via C# series]

[Category Theory via C# series]

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 category-theoretic structure.

Category and category laws

In category theory, a category C is a algebraic structure consists of the following 3 kinds of mathematical entities:

  • A collection of objects, denoted ob(C). This is not the objects in object-oriented programming paradigm.
  • A collection of morphisms (relations, aka arrows or maps) between objects, denoted hom(C). A morphism m from source object X to target object Y is denoted m: X → Y.
  • A composition operation of morphisms, denoted ∘. For m1: X → Y and m2: Y → Z, their composition is also a morphism (m2∘ m1): Y → Z. Here the name of m1 of m2 also implies the order. m2 ∘ m1 can be read as m2 after m1.
    image

And these entities must satisfy the following 2 category laws:

  • Associative law: the composition of morphisms associative: For m1: W → X, m2: X → Y and m3: Y → Z, there is (m3 ∘ m2) ∘ m1≡ ≡ m3 ∘ (m2 ∘ m1).
    image                                                                                                                               
  • Identity law: for each object X, there is an identity morphism: idx : X → X, and identity morphism is neutral for morphism composition. For m: X → Y, there is idY ∘ m ≡ m ≡ m ∘ idX.
    image


To make above abstract definitions intuitive, a category can be represented by the following interface:

public interface ICategory<TObject, TMorphism>
{
    IEnumerable<TObject> Objects { get; }

    TMorphism Compose(TMorphism morphism2, TMorphism morphism1);

    TMorphism Id(TObject @object);
}

A simple example of category is the category of integers, where the collection of objects are all integers, and the collection of morphisms are ≤ (less than or equal to) relations, from an integer either to itself, or to another integer greater than or equal to it, for example: m1: 0 → 1 (0 ≤ 1), m2: 1 → 10 (1 ≤ 10), etc. Regarding the transitivity of inequality, the ≤ morphisms can be composed, for example, m1: 0 → 1 (0 ≤ 1) and m2: 1 → 10 (1 ≤ 10) can be composed to another morphism (m2 ∘ m1): 0 → 10 (0 ≤ 10).

image

image

Apparently, the above composition is associative, foe example: ((1 ≤ 10) ∘ (0 ≤ 1)) ∘ (-1 ≤ 0) ≡ -1 ≤ 10 ≡ (1 ≤ 10) ∘ ((0 ≤ 1) ∘ (-1 ≤ 0)). And for each integer X, there is an identity morphism idX: X → X (X ≤ X), and (Y ≤ Y) ∘ (X ≤ Y) ≡ X ≤ Y ≡ (X ≤ Y) ∘ (X ≤ X). So the category laws are satisfied. In C#, integer can be represented by int, and the morphism of ≤ relation can be represented by a BinaryExpression of node type LessThanOrEqual, so the category can be represented as:

public class Int32Category : ICategory<int, BinaryExpression>
{
    public IEnumerable<int> Objects
    {
        get
        {
            for (int int32 = int.MinValue; int32 <= int.MaxValue; int32++)
            {
                yield return int32;
            }
        }
    }

    public BinaryExpression Compose(BinaryExpression morphism2, BinaryExpression morphism1) =>
        Expression.LessThanOrEqual(morphism2.Left, morphism1.Right); // (Y <= Z) ∘ (X <= Y) => X <= Z.

    public BinaryExpression Id(int @object) =>
        Expression.LessThanOrEqual(Expression.Constant(@object), Expression.Constant(@object)); // X <= X.
}

DotNet category

.NET can also be viewed as a category of types and functions, called DotNet:

  • ob(DotNet): the collection of objects in DotNet category are .NET types, like string (System.String), int (System.Int32), bool (System.Boolean), etc.
  • hom(DotNet): the collection of morphisms in DotNet category are .NET pure functions between the input type (source object) to the output type (target object), like int.Parse: string → int, DateTime.IsLeapYear: int → bool, etc.
  • ∘: in DotNet category, the composition operation of morphisms is the composition of functions.

As already discussed in lambda calculus chapter, function composition is associative, and the unit function Id is the identity morphism:

public static partial class Functions
{
    public static Func<TSource, TResult> o<TSource, TMiddle, TResult>(
        this Func<TMiddle, TResult> function2, Func<TSource, TMiddle> function1) =>
            value => function2(function1(value));

    public static TSource Id<TSource>(T value) => value;
}

So that the category laws are satisfied.

image

The DotNet category can be represented as:

public partial class DotNetCategory : ICategory<Type, Delegate>
{
    public IEnumerable<Type> Objects =>
        SelfAndReferences(typeof(DotNetCategory).Assembly)
            .SelectMany(assembly => assembly.GetExportedTypes());

    public Delegate Compose(Delegate morphism2, Delegate morphism1) =>
        // return (Func<TSource, TResult>)Functions.Compose<TSource, TMiddle, TResult>(
        //    (Func<TMiddle, TResult>)morphism2, (Func<TSource, TMiddle>)morphism1);
        (Delegate)typeof(Linq.FuncExtensions).GetMethod(nameof(Linq.FuncExtensions.o))
            .MakeGenericMethod( // TSource, TMiddle, TResult.
                morphism1.Method.GetParameters().Single().ParameterType,
                morphism1.Method.ReturnType,
                morphism2.Method.ReturnType)
            .Invoke(null, new object[] { morphism2, morphism1 });

    public Delegate Id(Type @object) => // Functions.Id<TSource>
        typeof(Functions).GetMethod(nameof(Functions.Id)).MakeGenericMethod(@object)
            .CreateDelegate(typeof(Func<,>).MakeGenericType(@object, @object));

    private static IEnumerable<Assembly> SelfAndReferences(
        Assembly self, HashSet<Assembly> selfAndReferences = null)
    {
        selfAndReferences = selfAndReferences ?? new HashSet<Assembly>();
        if (selfAndReferences.Add(self))
        {
            self.GetReferencedAssemblies().ForEach(reference => 
                SelfAndReferences(Assembly.Load(reference), selfAndReferences));
            return selfAndReferences;
        }
        return Enumerable.Empty<Assembly>(); // Circular or duplicate reference.
    }
}

In DotNet category, each object is a type represented by System.Type, so Objects method queries all available types in current assembly, and also recursively query all available assemblies in all reference assemblies. And each morphism is a function from one type to another, which can be represented by System.Delegate, so the composition is just to call the o operator with 2 Delegate instances.

47 Comments

  • Hello
    I think there is a typo in:
    > A composition operation of morphisms, denoted ∘. For m1: X → Y and m2: Y → Z, their composition is also a morphism (m2∘ m1): Y → Z. Here the name of m1 of m2 also implies the order. m2 ∘ m1 can be read as m2 after m1
    the statement
    > their composition is also a morphism (m2∘ m1): Y → Z
    should be rewritten
    > their composition is also a morphism (m2∘ m1): X → Z

  • This is an invaluable article.
    Thanks.

  • This is an invaluable article.
    Thanks.

  • In the Functions class

    public static TSource Id<TSource>(T value) => value;

    T should be TSource right?

    --------------------------
    In the DotNetCategory

    (Delegate)typeof(Linq.FuncExtensions).GetMethod(nameof(Linq.FuncExtensions.o))

    Should be

    (Delegate)typeof(Functions).GetMethod(nameof(Functions.o))

  • It looks like .NET code snippets are not generating proper HTML anymore.

  • A pedido de amigos os resultados anteriores foram incluídos nesta página.
    Deu no poste.
    Segunda-Feira 2020 O resultado do jogo do bicho,
    deu no poste desta Domingo,
    segue abaixo para apuração.
    Pesquise sempre por
    “jogo do bicho portalbrasil.


  • Deu no Poste ? Resultados Jogo do Bicho das 11 horas, 14 horas, 16 horas, 18 horas, 21 horas.
    Mostramos-lhe a tabela de resultados do jogo do bicho.

  • Amazon.com/mytv - enter the 6 digit amazon mytv code you receive at screen at www.amazon.com/mytv to regiter your device. contact amazon support for hel

  • Hello there! Nice article!!! But anyways here’s one of the trusted online baccarat site we can offer you so many promo and event everyday!! Good luck!!!

  • Thank you for sharing your truth! I have so much more that I would like to say but I don't think its necessary. Just visit my site:

  • Great article, This post helps me a lot Thank you. Anyways I have this site recommendation for you, Just follow the given link here:

  • Reading this info So i am glad to convey that I have a very just right uncanny feeling I found out exactly what I needed. See more about sportstoto:

  • استفاده از سرویس ادوردز، نیاز به تخصص و تجربه کافی در این زمینه دارد. از این رو، مدیریت اکانت های ادوردز، در سال های اخیر به یک شغل محبوب تبدیل شده است که بسیاری از کارشناسان و شرکت های حوزه دیجیتال مارکتینگ، آن را ارائه می دهند. اگر به اندازه کافی با کار کردن با این سیستم آشنایی ندارید، یک اشتباه کوچک در آن می تواند هزینه های شما را هدر بدهد و منجر به کلیک های بی هدف شود.

  • مجموعه تولیدی زعیم ZAEEM با سابقه طولانی در زمینه تهیه و توزیع انواع نهاده های کشاورزی، با اتکا به دانش روز تولید نهاده های کشاورزی، اقدام به تولید انواع کود های مایع ، پودری و گرانول نموده و محصولات خود را با افتخار با نام تجاری ZAEEM به بازار عرضه می نماید. تمامی محصولات ZAEEM در پایلوت های مشخص مورد آزمون قرار گرفته و پس از دریافت مجوز های لازم از موسسه خاک و آب کشور به بازار ارائه می گردد. کشاورزان محترم می توانند با دانلود کاتالوگ محصولات زعیم در سایت ZAEEM و در بخش همکاران ZAEEM، اطلاعات تماس نمایندگی ها و عوامل فروش شرکت در سطح کشور را مشاهده کرده و از خدمات و محصولات مورد نیاز خود با کمترین هزینه ارسال کالا و درکمترین زمان ممکن برخوردار شوند.

  • <a href="https://tahvienovin.com/">شرکت تهویه نوین ایرانیان</a> با بهره گیری از کادری مجرب و حرفه ای، متشکل از مهندسین با تجربه و نیروهای متخصص بر آن است تا در مسیر تحقق مشتری مداری گامهایی مؤثرتر بردارد. در این راستا با ارائه محصولاتی با کیفیت، عملکردی مطلوب، هزینه ای بهینه و نیز خدمات پس از فروش، در پی جلب رضایت مشتریان گرامی است.

  • This post is really astounding one! I was delighted to read this, very much useful. Many thanks

  • awesome post. I’m a normal visitor of your web site and appreciate you taking the time to maintain the nice site. I’ll be a frequent visitor for a long time.

  • This article is really fantastic and thanks for sharing the valuable post.

  • I arrived here from https://tyrrrz.me/blog/monadic-comprehension-via-linq. I've never seen anyone try to express category theory via C#, and even if it's less-suited to this type of exposition than, say, Haskell, it's still a very nice presentation of the concepts!

    I would like to make a small, hopefully constructive criticism of the commutative diagrams. I found the text written written in yellow, labeling the yellow morphsim arrows, nearly impossible to read.

    All the recent comments look like spam, so I have no idea if this comment will ever be read, but nice work!

  • Hello thankyou so much for this ,if someone taking online class so I believe it is very difficult for him and for that visit our website we have experts who will help you guys for taking your online class and online exam.

  • I am delighted to share after reading this awesome piece of writing. Excellent post.

  • https://ma-study.blogspot.com/

  • آموزش جوشکاری صفر تا صد با ارائه مدرک بین المللی فنی و حرفه ای جهت مهاجرت
    آموزش جوشکاری در آموزشگاه جوشکاری آریاگستر از جمله دوره های فنی می باشد که بازار کار خوبی داشته و معمولا جوشکاران از درآمد بالایی برخوردارند. نیاز جوامع به تولید و صنعت به این شغل باعث شده که افراد زیادی خواهان آموزش جوشکاری باشند .

    www.ariavash.ir
    https://ariavash.ir/fa/%D8%A2%D9%85%D9%88%D8%B2%D8%B4-%D8%AC%D9%88%D8%B4%DA%A9%D8%A7%D8%B1%DB%8C/

  • Thank you for helping people get the information they need. Great stuff as usual. Keep up the great work!!!.

  • Betting users who wish to use Sports Toto are advised to practice sports analysis techniques consistently. If you learn this knowledge by discussing the analysis of very good fixers, you can gain a useful position in sports betting as a constant.

  • Thank you for the auspicious writeup. It in fact was a amusement account it. Look advanced to more added agreeable from you!

  • Magnificent post, very informative. I’m wondering why the opposite experts of this sector do not realize this. You should continue our writing. I am sure, you’ve a great readers’ base already!

  • To an extraordinary degree beautiful and enthralling post. I was chasing down this sort of data and recognized inspecting this one. Continue posting. Grateful for sharing.
    <a href="https://www.19guide03.com/" target="_blank" title="성인웹툰">성인웹툰</a>

  • <a href="https://images.google.co.za/url?q=https://www.currentschoolnews.com/job/companies-that-hire-for-remote-virtual-assistant-jobs-2022/%2F">virtual assistant jobs</a><br />
    <a href="https://cse.google.lt/url?q=https://www.currentschoolnews.com/job/companies-that-hire-for-remote-virtual-assistant-jobs-2022/%2F">virtual assistant job</a><br />
    <a href="https://images.google.lt/url?q=https://www.currentschoolnews.com/job/companies-that-hire-for-remote-virtual-assistant-jobs-2022/%2F">virtual assistant jobs near me</a><br />
    <a href="https://cse.google.rs/url?q=https://www.currentschoolnews.com/job/companies-that-hire-for-remote-virtual-assistant-jobs-2022/%2F">part time virtual assistant jobs</a><br />
    <a href="https://maps.google.rs/url?q=https://www.currentschoolnews.com/job/companies-that-hire-for-remote-virtual-assistant-jobs-2022/%2F">virtual assistant jobs for beginners</a><br />
    <a href="https://images.google.rs/url?q=https://www.currentschoolnews.com/job/companies-that-hire-for-remote-virtual-assistant-jobs-2022/%2F">virtual assistant jobs online</a><br />
    <a href="https://www.google.com.mx/url?q=https://www.currentschoolnews.com/job/companies-that-hire-for-remote-virtual-assistant-jobs-2022/%2F">virtual assistant jobs part time</a><br />
    <a href="https://cse.google.com.mx/url?q=https://www.currentschoolnews.com/job/companies-that-hire-for-remote-virtual-assistant-jobs-2022/%2F">virtual assistant jobs from home</a><br />
    <a href="https://maps.google.com.mx/url?q=https://www.currentschoolnews.com/job/companies-that-hire-for-remote-virtual-assistant-jobs-2022/%2F">virtual assistant jobs no experience</a><br />
    <a href="https://images.google.com.mx/url?q=https://www.currentschoolnews.com/job/companies-that-hire-for-remote-virtual-assistant-jobs-2022/%2F">virtual personal assistant jobs</a><br />
    <a href="https://www.google.fi/url?q=https://www.currentschoolnews.com/job/companies-that-hire-for-remote-virtual-assistant-jobs-2022/%2F">virtual assistant jobs amazon</a><br />
    <a href="https://cse.google.fi/url?q=https://www.currentschoolnews.com/job/companies-that-hire-for-remote-virtual-assistant-jobs-2022/%2F">virtual assistant jobs teenager</a><br />
    <a href="https://maps.google.fi/url?q=https://www.currentschoolnews.com/job/companies-that-hire-for-remote-virtual-assistant-jobs-2022/%2F">virtual.assistant jobs</a><br />
    <a href="https://images.google.fi/url?q=https://www.currentschoolnews.com/job/companies-that-hire-for-remote-virtual-assistant-jobs-2022/%2F">virtual assistant jobs chicago  </a><br />
    <a href="https://cse.google.lt/url?q=https://suntrustblog.com/lamb-chops-2/">lamb chops</a><br />
    <a href="https://maps.google.lt/url?q=https://suntrustblog.com/lamb-chops-2/">lamb chops near me</a><br />
    <a href="https://images.google.lt/url?q=https://suntrustblog.com/lamb-chops-2/">lamb chops recipe</a><br />
    <a href="https://cse.google.rs/url?q=https://suntrustblog.com/lamb-chops-2/">how to cook lamb chops</a><br />
    <a href="https://maps.google.rs/url?q=https://suntrustblog.com/lamb-chops-2/">grilled lamb chops</a><br />
    <a href="https://images.google.rs/url?q=https://suntrustblog.com/lamb-chops-2/">lamb</a><br />
    <a href="https://www.google.com.mx/url?q=https://suntrustblog.com/lamb-chops-2/">lamb chops</a><br />
    <a href="https://cse.google.com.mx/url?q=https://suntrustblog.com/lamb-chops-2/">mutton chops</a><br />
    <a href="https://maps.google.com.mx/url?q=https://suntrustblog.com/lamb-chops-2/">lamb chop recipes</a><br />
    <a href="https://images.google.com.mx/url?q=https://suntrustblog.com/lamb-chops-2/">rack of lamb</a><br />
    <a href="https://www.google.fi/url?q=https://suntrustblog.com/lamb-chops-2/">air fryer</a><br />
    <a href="https://cse.google.fi/url?q=https://suntrustblog.com/lamb-chops-2/">medium</a><br />
    <a href="https://maps.google.fi/url?q=https://suntrustblog.com/lamb-chops-2/">lamb</a><br />
    <a href="https://images.google.fi/url?q=https://suntrustblog.com/lamb-chops-2/">fresh thyme</a><br />
    <a href="https://www.google.hu/url?q=https://suntrustblog.com/lamb-chops-2/">pan</a>

  • قهوه فرانسه یک نوع قهوه سبک و دمی، که انتخاب مناسبی برای وعده صبحانه می باشد. به دلیل در مجاورت بودن آب و قهوه موقع دم کشی، کافئین خوبی هم دارد. برای دم کردن این قهوه از وسیله‌ای بنام فرنچ پرس، استفاده می‌ شود.


  • برای مشاهده و خرید انواع لاک ژل در رنگ بندی و مدل‌های مختلف کلیک کنید

  • خریدshadowlands ، شدولند مکانی است که تمام مردگان و ارواح به آنجا سفر میکنند . سیلواناس به رهبری هلیا ، گروهی برای مبارزه تشکیل داده . سیلوانا قصد دارد در دنیای آزروت ، تمام موجودات را نابود و به شدولند ببرد .
    تمام قدرت سیلوانا به خاطر شخصی است که با او در ارتباط است . سیلوانا Domination را شکست میدهد و مرز بین آزروت و شدولند ( زندگی بعد از مرگ ) را از بین میبرد .امپراطوری سیاه بر پا خواهد شد . جنگجویان بعد از کشتن هر قربانی ، روحشان را به شدولند میفرستند . الینس ها با خدایان در شدولند میجنگند . هاکار قصد دارد تا با بلعیدن رواح قدرتمند شود .
    سیلواناس با هدایت جنگ ، قصد دارد ارواح را از هاکار به سمت هلیا هدایت کند . ارواح تمام ترول هایی که در تزمیر کشته شده اند ، در موربارا ساکن اند . در النیر ریفت‌لندز بیشترین فساد وید در دراگون آیلز و رویای زمردین وجود دارد . شهر و قرارگاه اصلی به عنوان منطقه آرام در ژیروس قرار دارد . این ناحیه دارای مقدار خیلی زیادی از کؤست لاین و دو دانجن میباشد . در مجموع 9 دانجن که 5 تا در شدولند و بقیه در دراگون ایلز است و اسمی ندارد .

  • Popularity of Gametime for two months:
    As mentioned above, the 60-day game time has been more popular than other game times for several months. This is because it has both the right time and the right price. The reason why World of Warcraft players use this type of game time is the duration. Because the game time of 60 days is an average game time and most people use the days of this game time. One advantage that this game time has over other game times is its duration.

    All kinds of game time regions
    In general, the two-month game time is made from 2 regions, Europe and America. But an important point is that it is recommended to get a region of Gametime that is compatible with your Shadowland region. If you are looking for our advice, we recommend you to buy Region Europe. Because it is close to Middle East servers and usually you get better ping.
    Prepared from the Jet Game website

  • Apk

  • From some point on, I am preparing to build my site while browsing various sites. It is now somewhat completed. If you are interested, please come to play with Keo nha cai !!

  • As I am looking at your writing, Keonhacai I regret being unable to do outdoor activities due to Corona 19, and I miss my old daily life. If you also miss the daily life of those days, would you please visit my site once? My site is a site where I post about photos and daily life when I was free.

  • The 60-day game time is currently the only game time provided by the Blizzard company for the players of the game, Word of Warcraft. In the past, game times such as 30 days and 180 days were also available, but due to the new policies of this company and the policy it has considered, the only game time that is currently available for dear gamers is Game Time 60. It is fasting. In the following, we have collected interesting explanations about Game Time for you, which are worth reading.

    Game time application for two months

    Currently, 2-month game time is used in all areas of World of Warcraft. But if you want to experience a series of interesting and new experiences, you should buy this game time. These experiences include:
    Using new extensions
    Play on new maps
    Lollup in a new style
    Change in the shape of the game
    Prepared from the Jet Game website

  • Your writing is perfect and complete. baccaratsite However, I think it will be more wonderful if your post includes additional topics that I am thinking of. I have a lot of posts on my site similar to your topic. Would you like to visit once?

  • such a wonderful post.

  • very nice post.

  • very nice post.

  • very nice post.

  • such a great post.

  • رشد جمعیت مسلمانان در حال حاضر چهره اروپا را از نظر اجتماعی، سیاسی و اقتصادی تغییر داده است. از نظر اجتماعی، جامعه مسلمان بیشتر از جامعه مسیحی، جامعه‌گرایی را تجربه می‌کند. این دومی از نظر کلیساها، اعتقادات و عمل پراکنده تر است. مسلمانان به شدت به اعتقادات و ریشه های خود وابسته هستند و اگر مهاجر باشند معمولاً با کشور مبدا خود رابطه دارند. از نظر سیاسی، جامعه مسلمان شامل رأی دهندگان چپ بیشتری است، احزاب سیاسی چپ معمولاً طرفدار ادغام مهاجران مسلمان در جامعه اروپایی هستند (Dancygier, 2018).

  • I've been searching for hours on this topic and finally found your post. majorsite I have read your post and I am very impressed. We prefer your opinion and will visit this site frequently to refer to your opinion. When would you like to visit my site?

  • The looks really great. Most of these smaller details are usually created employing wide range of heritage knowledge. I would like all of it substantially.

  • What You Should Know About Satta Matka

    Whether you are new to <a href="https://sattamatkaji.net"> satta matka</a> or a seasoned player, there are certain things that you should know before you start betting on the sattamatka games. The game is very simple and is a popular one among Indians, but it is important to know the rules before you start.
    Online <a href="https://sattamatkaji.net"> sattamatka</a> gambling is a good choice

    Whether you are looking to win big or just play the game, online <a href="https://sattamatkaji.net/blog"> satta matka</a> gambling is definitely one of the best options you can choose. However, it can also be dangerous. You need to be aware of the right sites to play on. The best ones are ones <a href="https://siliguriff.com"> kolkata ff</a> that are operated by reputable companies and are licensed to do so. You need to also be aware of scams.

    A good online <a href="https://matkaplay.in"> matka play</a> gambling site should be user-friendly and offer a variety of options. This is especially important when you are looking to win big. You should also be aware of the safety and security measures in place

Add a Comment

As it will appear on the website

Not displayed

Your website