The 'map' function is the same as Kleene star (regex *)!

README.md

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)
                        readIORef bar
                    ) 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.