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_listHere'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.