Skip to content

Instantly share code, notes, and snippets.

@kylechui

kylechui/functional_patterns.md

Last active September 23, 2023 00:19
Download ZIP

Revisions

  1. kylechui revised this gist Mar 14, 2023. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion functional_patterns.md
    View file
    Original file line number Diff line number Diff line change
    @@ -59,7 +59,7 @@ $$
    e\cdot a = a\cdot e = a. \tag{Identity element}
    $$

    We write this as $M = (T, \cdot, e)$.
    For brevity, we write this monoid as $(T, \cdot, e)$.

    ### Example 1: `int`s with addition

  2. kylechui revised this gist Mar 14, 2023. 1 changed file with 3 additions and 3 deletions.
    6 changes: 3 additions & 3 deletions functional_patterns.md
    View file
    Original file line number Diff line number Diff line change
    @@ -9,9 +9,9 @@
    - [Introduction](#introduction)
    - [Monoids](#monoids)
    - [Definition](#definition)
    - [Example 1: `int`s with addition](#example-1%3A-ints-with-addition)
    - [Example 2: `string`s with concatenation](#example-2%3A-strings-with-concatenation)
    - [Why do we care?](#why-do-we-care%3F)
    - [Example 1: `int`s with addition](#example-1-ints-with-addition)
    - [Example 2: `string`s with concatenation](#example-2-strings-with-concatenation)
    - [Why do we care?](#why-do-we-care)
    - [Functors: WIP](#functors)
    - [Monads: TODO](#monads)
    - [Applicatives: TODO](#applicatives)
  3. kylechui revised this gist Mar 14, 2023. 1 changed file with 26 additions and 4 deletions.
    30 changes: 26 additions & 4 deletions functional_patterns.md
    View file
    Original file line number Diff line number Diff line change
    @@ -2,20 +2,40 @@
    > better understand these concepts in relation to their pure mathematical
    > foundations. Comments and suggestions welcome!
    # Functional Design Patterns
    ---

    ## Table of contents

    - [Introduction](#introduction)
    - [Monoids](#monoids)
    - [Definition](#definition)
    - [Example 1: `int`s with addition](#example-1%3A-ints-with-addition)
    - [Example 2: `string`s with concatenation](#example-2%3A-strings-with-concatenation)
    - [Why do we care?](#why-do-we-care%3F)
    - [Functors: WIP](#functors)
    - [Monads: TODO](#monads)
    - [Applicatives: TODO](#applicatives)
    - [Sources](#sources)

    ---

    <div id="introduction"/>

    ## Introduction

    This gist aims to give a brief overview of certain mathematical objects and why
    programmers care about them. The overall structure for each section will start
    with a definition for the object, then a few examples, followed by motivation
    for why we should care about these objects.
    with a definition for the object, then a few examples, followed by a list of
    properties that makes the object useful/interesting to programmers.

    Some additional notes for this gist:

    - Basic proof-reading and some mathematical maturity is assumed for the
    definitions.
    - All of the examples use OCaml-style notation, although it shouldn't matter too
    much if you're unfamiliar with OCaml.
    - We will treat programming types as sets.
    - We treat programming types as sets, i.e. `int` is the same as $\mathbb{Z}$.
    - Many of the definitions denote sets using $T$ for "type".

    ## Monoids

    @@ -110,6 +130,8 @@ $$

    we get the monoid $(\texttt{int * string}, *, (0, \texttt{""}))$.

    ## Functors

    # Sources

    - [The Functional Programmer's Toolkit - Scott Wlaschin](https://www.youtube.com/watch?v=Nrp_LZ-XGsY)
  4. kylechui revised this gist Mar 13, 2023. 1 changed file with 12 additions and 4 deletions.
    16 changes: 12 additions & 4 deletions functional_patterns.md
    View file
    Original file line number Diff line number Diff line change
    @@ -88,7 +88,7 @@ beyond.
    start with for computation? Remember that monoids contain an identity
    element; in the case of summing `int`s, we can start with the value 0.
    - **Note**: This is sometimes called "reducing", since we can reduce a `list`
    of `int`s to a single `int` via repeated application $+$.
    of `int`s to a single `int` via repeated application of $+$.
    - **Incremental computation**: Again, since addition is closed, we can
    incrementally compute the sum of `int`s. If we have a current sum and are
    given more `int`s to add, we don't have to recompute anything; we can simply
    @@ -98,9 +98,17 @@ beyond.
    computation, since multiple cores can add parts of the `list` simultaneously,
    before the partial sums are added together.

    **Note**: Combinations (read: Cartesian products) of monoids are also monoids!
    This can be done by performing each monoid's operators component-wise on the
    product.
    **Note**: Combinations of monoids are also monoids! For example, consider the
    monoids $(\texttt{int}, +, 0)$ and $(\texttt{string}, \wedge, \texttt{""})$. We
    show that the set `int * string` forms a monoid, by defining a binary operation
    and identity element pairwise. Let $n_1, n_2\in \texttt{int}$ and
    $s_1, s_2\in \texttt{string}$. Then if we define $*$ by

    $$
    (n_1, s_1) * (n_2, s_2) = (n_1 + n_2, s_1\wedge s_2),
    $$

    we get the monoid $(\texttt{int * string}, *, (0, \texttt{""}))$.

    # Sources

  5. kylechui revised this gist Mar 13, 2023. 1 changed file with 30 additions and 30 deletions.
    60 changes: 30 additions & 30 deletions functional_patterns.md
    View file
    Original file line number Diff line number Diff line change
    @@ -39,64 +39,64 @@ $$
    e\cdot a = a\cdot e = a. \tag{Identity element}
    $$

    We write this as $M = (T, \cdot, e)$.

    ### Example 1: `int`s with addition

    Consider the set of `int`s with the usual addition operator
    $+\colon\texttt{int}\times \texttt{int}\to \texttt{int}$. We can verify that
    this is a monoid, since for all $\{a, b, c\}\in \texttt{int}$, we have
    Consider the monoid $(\texttt{int}, +, 0)$. We can verify that this is a monoid,
    since for all $\{a, b, c\}\in \texttt{int}$, we have

    $$
    (a + b) + c = a + (b + c), \tag{Associativity}
    $$

    as well as $0\in \texttt{int}$ satisfying
    and $0\in \texttt{int}$ satisfies

    $$
    0 + a = a + 0 = a. \tag{Identity element}
    $$

    ### Example 2: `string`s with concatenation

    Consider the set of `string`s with the usual concatenation operator
    $\wedge\colon\texttt{string}\times \texttt{string}\to \texttt{string}$. We can
    verify that this is a monoid, since for all $\{a, b, c\}\in \texttt{string}$, we
    have
    Let $\wedge$ denote the string concatenation operator. Consider the monoid
    $(\texttt{string}, \wedge, \texttt{""})$. We can verify that this is a monoid,
    since for all $\{a, b, c\}\in \texttt{string}$, we have

    $$
    (a\wedge b)\wedge c = a\wedge (b\wedge c), \tag{Associativity}
    $$

    as well as the empty string $\texttt{""}\in \texttt{int}$ satisfying
    and the empty string $\texttt{""}\in \texttt{string}$ satisfies

    $$
    \texttt{""}\wedge a = a\wedge \texttt{""} = a. \tag{Identity element}
    $$

    ### Why do we care?

    - **List computation**: Since the binary operation for a monoid is closed (e.g.
    addition maps `int`s to `int`s), we can "lift" the operator to apply to an
    arbitrary number of objects, instead of just two. For example, you can use $+$
    to sum an arbitrary number of `int`s, instead of just two, by continually
    applying the operator until you are left with one `int` (the sum).
    _Prototypical monoid for this section_: $(\texttt{int}, +, 0)$. Keep in mind
    that everything discussed here extends to _all_ monoids, including
    $(\texttt{int}, \cdot, 1)$, $(\texttt{string}, \wedge, \texttt{""})$, and
    beyond.

    - **List computation**: Since addition is closed (i.e. adding two `int`s yields
    another `int`), we can apply the $+$ operator to an arbitrary number of `int`s
    (i.e. a `list` of `int`s), instead of just two. We do this by continually
    applying $+$ between our current sum and the next value in the `list`, until
    we have summed up the entire `list`.
    - **Note**: Since our operator takes in two arguments, what value should we
    start with for computation? Remember that the monoid contains an identity
    start with for computation? Remember that monoids contain an identity
    element; in the case of summing `int`s, we can start with the value 0.
    - **Incremental computation**: Suppose we are given a collection of objects that
    we wish to perform a binary operation over (i.e. summing a `list` of `int`s).
    If the set and operator form a monoid, then if we aggregate the entire
    collection, we can still process more elements without restarting the
    computation. For example, in the case of summing a `list` of `int`s, we can
    add more `int`s to an existing sum without recomputing the sum of the first
    few elements.
    - **Parallel computation**: Again, suppose we are given a collection of objects
    that we wish to perform a binary operation over (i.e. summing a `list` of
    `int`s). If the set and operator form a monoid, then we know that the operator
    is associative, and we can perform it in any arbitrary order. This lends
    itself very well to parallelizing the computation, since multiple cores can
    aggregate parts of the collection simultaneously, the results of which can
    then be collected.
    - **Note**: This is sometimes called "reducing".
    - **Note**: This is sometimes called "reducing", since we can reduce a `list`
    of `int`s to a single `int` via repeated application $+$.
    - **Incremental computation**: Again, since addition is closed, we can
    incrementally compute the sum of `int`s. If we have a current sum and are
    given more `int`s to add, we don't have to recompute anything; we can simply
    add to our existing sum.
    - **Parallel computation**: Since addition is associative, we can perform it in
    any arbitrary order. This lends itself very well to parallelizing the
    computation, since multiple cores can add parts of the `list` simultaneously,
    before the partial sums are added together.

    **Note**: Combinations (read: Cartesian products) of monoids are also monoids!
    This can be done by performing each monoid's operators component-wise on the
  6. kylechui revised this gist Mar 12, 2023. 1 changed file with 4 additions and 3 deletions.
    7 changes: 4 additions & 3 deletions functional_patterns.md
    View file
    Original file line number Diff line number Diff line change
    @@ -25,8 +25,7 @@ A _monoid_ is a set equipped with an associative binary operation and an
    identity element. More concretely, suppose we have:

    - Some set $T$
    - Some binary operator $\cdot\colon T\times
    T\to T$
    - Some binary operator $\cdot\colon T\times T\to T$

    This forms a monoid if for all $\{a, b, c\}\in T$, we have

    @@ -100,7 +99,9 @@ $$
    - **Note**: This is sometimes called "reducing".

    **Note**: Combinations (read: Cartesian products) of monoids are also monoids!
    This can be done by performing each monoid's operators component-wise on the
    product.

    # Sources

    - [The Functional Programmer's Toolkit -- Scott Wlaschin](https://www.youtube.com/watch?v=Nrp_LZ-XGsY)
    - [The Functional Programmer's Toolkit - Scott Wlaschin](https://www.youtube.com/watch?v=Nrp_LZ-XGsY)
  7. kylechui revised this gist Mar 12, 2023. 1 changed file with 70 additions and 1 deletion.
    71 changes: 70 additions & 1 deletion functional_patterns.md
    View file
    Original file line number Diff line number Diff line change
    @@ -9,6 +9,14 @@ programmers care about them. The overall structure for each section will start
    with a definition for the object, then a few examples, followed by motivation
    for why we should care about these objects.

    Some additional notes for this gist:

    - Basic proof-reading and some mathematical maturity is assumed for the
    definitions.
    - All of the examples use OCaml-style notation, although it shouldn't matter too
    much if you're unfamiliar with OCaml.
    - We will treat programming types as sets.

    ## Monoids

    ### Definition
    @@ -29,9 +37,70 @@ $$
    and there exists some $e\in T$ such that

    $$
    e\cdot a = a\cdot e = a. \tag{Identity}
    e\cdot a = a\cdot e = a. \tag{Identity element}
    $$

    ### Example 1: `int`s with addition

    Consider the set of `int`s with the usual addition operator
    $+\colon\texttt{int}\times \texttt{int}\to \texttt{int}$. We can verify that
    this is a monoid, since for all $\{a, b, c\}\in \texttt{int}$, we have

    $$
    (a + b) + c = a + (b + c), \tag{Associativity}
    $$

    as well as $0\in \texttt{int}$ satisfying

    $$
    0 + a = a + 0 = a. \tag{Identity element}
    $$

    ### Example 2: `string`s with concatenation

    Consider the set of `string`s with the usual concatenation operator
    $\wedge\colon\texttt{string}\times \texttt{string}\to \texttt{string}$. We can
    verify that this is a monoid, since for all $\{a, b, c\}\in \texttt{string}$, we
    have

    $$
    (a\wedge b)\wedge c = a\wedge (b\wedge c), \tag{Associativity}
    $$

    as well as the empty string $\texttt{""}\in \texttt{int}$ satisfying

    $$
    \texttt{""}\wedge a = a\wedge \texttt{""} = a. \tag{Identity element}
    $$

    ### Why do we care?

    - **List computation**: Since the binary operation for a monoid is closed (e.g.
    addition maps `int`s to `int`s), we can "lift" the operator to apply to an
    arbitrary number of objects, instead of just two. For example, you can use $+$
    to sum an arbitrary number of `int`s, instead of just two, by continually
    applying the operator until you are left with one `int` (the sum).
    - **Note**: Since our operator takes in two arguments, what value should we
    start with for computation? Remember that the monoid contains an identity
    element; in the case of summing `int`s, we can start with the value 0.
    - **Incremental computation**: Suppose we are given a collection of objects that
    we wish to perform a binary operation over (i.e. summing a `list` of `int`s).
    If the set and operator form a monoid, then if we aggregate the entire
    collection, we can still process more elements without restarting the
    computation. For example, in the case of summing a `list` of `int`s, we can
    add more `int`s to an existing sum without recomputing the sum of the first
    few elements.
    - **Parallel computation**: Again, suppose we are given a collection of objects
    that we wish to perform a binary operation over (i.e. summing a `list` of
    `int`s). If the set and operator form a monoid, then we know that the operator
    is associative, and we can perform it in any arbitrary order. This lends
    itself very well to parallelizing the computation, since multiple cores can
    aggregate parts of the collection simultaneously, the results of which can
    then be collected.
    - **Note**: This is sometimes called "reducing".

    **Note**: Combinations (read: Cartesian products) of monoids are also monoids!

    # Sources

    - [The Functional Programmer's Toolkit -- Scott Wlaschin](https://www.youtube.com/watch?v=Nrp_LZ-XGsY)
  8. kylechui revised this gist Mar 12, 2023. 1 changed file with 36 additions and 2 deletions.
    38 changes: 36 additions & 2 deletions functional_patterns.md
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,37 @@
    > **Note**: While this is public, this is mostly written for my own sake, to better understand these concepts. Comments and suggestions welcome!
    > **Note**: While this is public, this is mostly written for my own sake, to
    > better understand these concepts in relation to their pure mathematical
    > foundations. Comments and suggestions welcome!
    # Functional Design Patterns
    # Functional Design Patterns

    This gist aims to give a brief overview of certain mathematical objects and why
    programmers care about them. The overall structure for each section will start
    with a definition for the object, then a few examples, followed by motivation
    for why we should care about these objects.

    ## Monoids

    ### Definition

    A _monoid_ is a set equipped with an associative binary operation and an
    identity element. More concretely, suppose we have:

    - Some set $T$
    - Some binary operator $\cdot\colon T\times
    T\to T$

    This forms a monoid if for all $\{a, b, c\}\in T$, we have

    $$
    (a\cdot b)\cdot c = a\cdot (b\cdot c), \tag{Associativity}
    $$

    and there exists some $e\in T$ such that

    $$
    e\cdot a = a\cdot e = a. \tag{Identity}
    $$

    # Sources

    - [The Functional Programmer's Toolkit -- Scott Wlaschin](https://www.youtube.com/watch?v=Nrp_LZ-XGsY)
  9. kylechui created this gist Mar 12, 2023.
    3 changes: 3 additions & 0 deletions functional_patterns.md
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,3 @@
    > **Note**: While this is public, this is mostly written for my own sake, to better understand these concepts. Comments and suggestions welcome!
    # Functional Design Patterns