Partials & Patterns

2019-July-10

In functional programming, a function can be applied to only some of the parameters. This operation will result in a new function that can be applied to the rest of the arguments to produce the final result. Partial application is an important function-building technique.

Clojure provides the partial function for this purpose. An example of using partial is given below:


(def f (partial list 1 2))
(f 10 20)
;;=> (1 2 10 20)
      

The partial function assumes that the arguments are always applied in sequence. What if some of the arguments in-between are unknown at the time of calling partial? It should be possible to specify the unknown values as "empty-slots", which can be filled-in later at the time of the final function application.

Let's assume that we have an operator that can construct such non-sequential partials for us. We shall call this abstraction as cut because it knows how to deal with segmented argument lists. The slot for a missing argument will be represented by the pattern <>.

First we shall look at a few examples of using cut, then we will look at its actual implementation.

Some Examples

The following program shows that, at the basic level, cut behaves exactly like partial:


(def f (cut list 1 2))
(f 10 20)
;;=> (1 2 10 20)
      

The next program shows cut with a single slot between two arguments. This means, the resulting function has to be called with exactly one value, just enough to fill-in the slot.


(def f (cut list 1 <> 2))
(f 10)
;;=> (1 10 2)
      

The following examples show that slots can appear anywhere in the partial argument list:


(def f (cut list 1 <> 2 <> <> 3))
(f 10 20 30)
;;=> (1 10 2 20 30 3)

(def f (cut list <> 1 <> 2 <> <> 3))
(f 10 20 30 40)
;;=> (10 1 20 2 30 40 3)
      

Finally, we introduce the rest pattern (...) that will allow the partial function to accept an arbitrary number of arguments at the tail of the argument-list:


(def f (cut list <> 1 <> 2 <> <> 3 ...))
(f 10 20 30 40 50 60 70 80)
;;=> (10 1 20 2 30 40 3 50 60 70 80)
      

Implementation

The cut operator is defined as a macro that walks down the partial argument list looking for slots. It constructs a parameter list that contain entries for each slot. An argument list is also prepared with the partial arguments and variables from the parameter list inserted in proper order. As the last step, a new function is created which will call the partially-applied function with the fully-constructed argument list.


(defmacro cut [f arg & args]
  (let [arg-templ? (= arg '<>)
        a1 (if arg-templ?
             (gensym)
             arg)]
     ;; collect paremeter and argument lists in a single pass over `args`
     (loop [args args
            params (if arg-templ? [a1] [])
            final-args [a1]]
      (if (seq args)
        (let [a (first args)]
          (cond
            (= a '<>)
            (let [p (gensym)]
              (recur (rest args)
                     (conj params p)
                     (conj final-args p)))
            
            (= a '...) ; ignore rest of `args`
            (let [xs (gensym)
                  params (conj params '& xs)]
              `(fn ~params (apply ~f ~@final-args ~xs)))
            
            :else
            (recur (rest args)
                   params
                   (conj final-args a))))
        (if (seq params)
          `(fn ~params (~f ~@final-args))
          `(fn [& ~(symbol "xs")] (apply ~f ~@final-args ~(symbol "xs"))))))))
      

References

The cut operator was inspired by a similar abstraction in Kawa-Scheme.