Functional programming axioms

Question

I'm learning functional programming with Clojure, and want to deepen my theoretical understanding of functional paradigm (not just the syntax of Clojure).

I'm looking for axioms or formulas how each functional techniques like recursion, map, reduce, cons, first ans rest relates to each other, which is derivable/composable from which, and which is the ultimate axiom behind everything.

For example, I realized map could be implemented only using recur, first, rest and cons functions, and of course the mapping function itself passed to map.

After that, I also realized map could be also implemented using reduce, and again reduce could be implemented using recur, first and rest. Also filter could be implemented with reduce.

I feel like I start to wrap my head around functional programming, but it is still hard to see which are the most ultimate building blocks, i.e. which is the minimum set of abstractions or keywords to compose arbitrary function. With the map example, the second method uses one less abstraction to target the same goal. So, what are some ultimate axioms of functional paradigm to help me see the big picture?

Answer 1

From lambda (called fn in clojure), you can derive anything else. For example, let's do the classic exercise of deriving cons, first, and rest with fn:

(defn cons [x y]
  (fn [f]
    (f x y)))

(defn first [coll]
  (coll (fn [x y] x)))

(defn rest [coll]
  (coll (fn [x y] y)))

So if you want a set of axioms for functional programming, there's just one: lambda the ultimate axiom. For details on how derivations of other features can be done, see such articles as:

• The classic Lambda the Ultimate papers.
• Programming with Nothing, a more recent approach. This uses Ruby syntax, but it doesn't really matter because the only language feature it uses is lambda.
• SICP also has a section on deriving car/cdr/cons from lambda, as part of explaining the value of abstraction barriers: the implementation doesn't matter, as long as it satisfies the contracts you've established. And of course SICP is a good read in general if you're interested in the foundations of programming in general.

---

It seems from the comments like there is a lot of confusion about this answer; my fault for not explaining it for people who haven't seen it before.

The idea is not to reimplement all of clojure's built-in first/rest functionality, which are advanced polymorphic things that work on all sorts of sequences. Rather, we implement three cons/first/rest functions that work together to allow you to build collections, by satisfying the contract that

(= x (first (cons x y)))
(= y (rest (cons x y)))

You can build more complicated things like clojure's actual first/rest with just lambda, but you have to invent a whole type system first so it's a lot more involved.

Here's an example repl session describing what this exercise intended to demonstrate:

(defn cons [x y]
  (fn [f]
    (f x y)))

(defn first [coll]
  (coll (fn [x y] x)))

(defn rest [coll]
  (coll (fn [x y] y)))
user> (def integers (cons 0 (cons 1 (cons 2 (cons 3 nil)))))
#'user/integers
user> integers
#object[user$cons$fn__2108 0x3fb178bd "user$cons$fn__2108@3fb178bd"]
user> (first integers)
0
user> (first (rest (rest integers)))
2