Lambda calculus is the main idea behind functional programming, a complete model for computation. There are a lot of documents and courses about lambda calculus on the Internet, so in this post, I'll not focus on lambda calculus in theory. I'll take a more practical approach - use specific languages to represent lambda expressions. Clojure and Elixir have been chosen due to their coherence and elegance of design.
The λ-calculus is a language with three expression forms:
All functions of the lambda calculus are anonymous and only take one parameter. For example:
λx.e function accepts an argument x and returns the value of e.
In Clojure, we'd write this as:
(fn [x] e)
(f e) is the applied function f to e. Function application in Clojure is the same form as a lambda expression:
The table below shows some basic lambda terms and equivalent code in Clojure and Elixir:
|(λ f. λ x. f x)||
pair = λx. λy. λf. f xy
The pair function takes two arguments x and y and returns a function that contains x and y in its body.
In Clojure, this term is equivalent to:
(def pair (fn [a b] (fn [func] (func a b))))
pair = fn (a, b) -> (fn func -> func.(a, b) end) end
Given a pair, we can extract the first and second item using selection functions:
fst = λx. λy. x snd = λx. λy. y
These functions take two variables and simply return one of them.
(def fst (fn [a b] a)) (def snd (fn [a b] b)) ((pair 3 5) fst)) ;; => 3 ((pair 3 5) snd)) ;; => 5
Similar code in Elixir
fst = fn (a, b) -> a end snd = fn (a, b) -> b end pair.(3, 5).(fst) # => 3 pair.(3, 5).(snd) # => 5
This function takes 2 arguments and returns a function that is the composition of those.
comp = λg. λf. λx. g (f x)
Now we'll write real code to represent
comp function and define 2 functions
subtract for testing. In Clojure:
(def comp (fn [f g] (fn [x] (f (g x))))) (def add (fn [n] (+ n 2))) (def subtract (fn [n] (- n 4))) ((comp add subtract) 8) ;; => 6
The equivalent in Elixir:
comp = fn(g, f) -> (fn x -> f.(g.(x)) end) end add = fn a -> a + 2 end subtract = fn a -> a - 4 end comp.(add, subtract).(8) # => 6