Clojure: how is map different from comp?

Question

map takes a function and a list and applies the function to every element of the list. e.g.,

(map f [x1 x2 x3])
;= [(f x1) (f x2) (f x3)]

Mathematically, a list is a partial function from the natural numbers ℕ. If x : ℕ → X is some list, and f : X → Y is some function, then map takes the pair (f, x) to the list f○x : ℕ → Y. Therefore, map and comp return the same value, at least in the simple case.

However, when we apply map with more than one argument, there's something more complex going on. Consider the example:

(map f [x1 x2 x3] [y1 y2 y3])
;= [(f x1 y1) (f x2 y2) (f x3 y3)]

Here, we have two lists x : ℕ → X and y : ℕ → Y with the same domain, and a function of type f : X → (Y → Z). In order to evaluate on the tuple (f, x, y), map has to do some more work behind the scenes.

First, map constructs the diagonal product list diag(x, y) : ℕ → X × Y, which is defined by diag(x, y)(n) = (x(n), y(n)).

Second, map uncurries the function to curry^-1(f) : X × Y → Z. Finally, map composes these operations to get curry^-1(f) ○ diag(x, y) : ℕ → Z.

My question is: does this pattern generalize? Namely, suppose that we have three lists x : ℕ → X, y : ℕ → Y and z : ℕ → Z, and a function f : X → (Y → (Z → W))). Does map send the tuple (f, x, y, z) to the list curry^-2(f) ○ diag(x, y, z) : ℕ → W?

Answer 1

It seems that the question title has little to do with the question actually asked in the body; I'll try to address both issues.

The Clojure side

As evidenced by examples like (map inc [1 2 3]) and (comp inc [1 2 3]) -- both of which, incidentally, make perfect sense in Clojure -- the Clojure functions map and comp operate completely differently even in the one sequence case. map simply does not treat its sequence arguments as functions in the software sense of callable objects, whereas comp treats all of its arguments in this way; map returns a compound datum, whereas comp does not; the value returned by comp is callable as a function, whereas map's returns values are not; etc.

(Other functional languages similarly have separate "map" and "compose" higher-order functions; in Haskell, these are map (and the more general fmap) and (.).)

Notably, map performs no actual in-memory tupling-up of arguments to its input function and does not apply any deschönfinkelizing / uncurrying transformation to the input function.

The mathematical side

The pattern does of course generalize fine, though it's worth keeping in mind that what's a function of what etc. -- under the hood of the model, as it were -- depends on the choice of representation which tends to be arbitrary. Finite sequences can be represented perfectly well as (total) functions with finite ordinals as domains, or as Kuratowski tuples, or in the way which you describe where you don't care about your lists not necessarily being "gapless" etc. Depending on the representational choices, the concept of natural numbers might not enter the picture at all, the objects representing lists may or may not look like functions whose codomain is a superset of the set of the list's entries etc.