Instantly share code, notes, and snippets.

Created July 15, 2024 12:22
Show Gist options
• Save Chubek/9da744ccc10df8a359123e0c5d2f5d49 to your computer and use it in GitHub Desktop.
The 'map' function is the same as Kleene star (regex *)!

### The `map` function and Kleene Star (regex `*`) are the same! (homomorphic)

In functional languages, and most modern imperative languages which implement functional features, we often have a `map` function. In `λ->` (simply-typed `λ-calc`) we could describe the type of this function as:

``````Γ ⊢ λfλmα.m(α) : (A -> B) -> [A] -> Unit
``````

Let me explain what this notation means.

. `Γ` -> This is our context; . `λmλfα` -> These are 'arguments' of our function in Alonzo Church's `λ-calc` notation. These are all terms: .. Term `λf` denotes our function; .. Term `λm` denotes our map function; .. Term `α` dnotes our list; . `m(α)` -> This is 'body' of our function, you can guess what happens. WARNING This notation is a bit non-standard! . `(A -> B) -> [A] -> Unit` -> This is the curried type of our function in Alonzo Church's typed lambda calculus; `λ->`. .. `(A -> B)` denotes type of `λm`; .. `[A]` denotes type of `α`; .. `Unit` denotes that function returns nothing (I borrowed this from Standard ML; this is imperative; again, my notation is just a tad non-standard);

This is typing a la Church, or explicit typing. In Haskell, we use this kind of typing. However, in ML languages (quite ironically!) we use typing a la Curry; our typing could be implicit but also explicit a la Church.

Here's an example in OCaml (a la Curry):

```let bar = ref 0
let foo baz_list = List.map (fun n -> bar := !bar + n) baz_list```

Here's an example in Haskell (again, quite ironically, a la Church):

``````import Data.IORef

bar :: IORef Int
bar = newIORef 0

foo :: [Int] -> IO [Int]
foo baz_list = mapM (\n -> do
modifyIORef' bar (+ n)
) baz_list
``````

Since Haskell is a pure functional language, it uses Monads to achieve imperative side effects. But OCaml is impure and it does it built-in. The way both languages handle references is quite similar though.

Now the main matter at hand: `map` function is formally the same as the regular expression `*` operator; that is, Kleene (pronounced KLEEN-ay) star. Kleene was one of Church's students and he, along with some other key figures in early CS, helped him develop `λ-Calc`. Kleene later went on to formalize regular expressions. When I say regular expressions I don't mean the language we use today for pattern matching. This language has a lot of operators! The OG regex only has 3 operators (concat, alternate and closure aka star) and in fact, when Ken Thompson implemented a program to use mathematical notion of regex for pattern matching, he just used those threee operators!

Kleene closure or Kleene star is the `*` operator in regular expressions; and it is a homomorphism of monoids; but what are monoids? In category theory monoinds can be thought of as, basically, binary expressions! Homomorphism basically means "there's a direct relationship". But wait, you may ask, is Kleene star not a unary operator?

Truth is, Kleene star is what makes a language a LANGUAGE. That is, a regular language. Some languages are tightly bound, such as regular languages which regular expressions represent. Some languages are context-free and some languages are less bound. These are the 4 types of grammars as classified by Chomsky. Programming languages are Type 2, or context-free. Regular expressions are Type 3, or regular.

A Kleene star represents a closure, a free monoid. `{0, 1}*` could be `{0, 1}*{0, 1}*{0,1}` --- this is what we call the pumping lemma; so Kleene star IS BOTH UNARY AND BINARY!

Now, what is `map` function?

This is a homomorphism on the map function:

``````f* : A* -> B*
``````

This is a function whose domain (A*) and codomain (B*) are both closures, both are pumping.

And `f*`, my dear friends, is the `map` function.

This text may contain factual errors. Please let me know what they are. I am `.chubak` on Discord.