Understanding `clojure.core.reducers/rfn`

[Tianxiang Xiong]

In `clojure.core.reducers`, `map` is implemented as:

(defcurried map
  "Applies f to every value in the reduction of coll. Foldable."
  {:added "1.5"}
  [f coll]
  (folder coll
   (fn [f1]
     (rfn [f1 k]
          ([ret k v]
             (f1 ret (f k v)))))))

I don't understand the purpose of `rfn`, and there are others confused about it as well.

From what I can see, `rfn` takes a reducing function `f1` and returns a reducing function with 3 arities. For example, macroexpanding

(rfn [f1 k]
     ([ret k v]
      (f1 ret (f k v))))

gives 

(fn
  ([] (f1))
  ([ret v] (f1 ret (f v)))
  ([ret k v] (f1 ret (f k v))))

When is the 3-arity form used? An example would be helpful.

[Alex Miller]

The 3 arity is used when reducing over a map, like reduce-kv. Reducers do this automatically which varies from the core reduce.

[Tianxiang Xiong]

Would that ever be the case for `r/map`? Or does it only apply to certain other reducers?

[Alex Miller]

Reducers combine functionally, so they all have to support it to create any composite reducer that contains map.

[Tianxiang Xiong]

I think this is one of those cases where I need to see an example to understand.

From what I can tell, the `(fn [f1] (rfn ...))` argument to `folder` is a reducing-function-transformer--i.e. transducer, except there are some differences in things like order of application in composition. I don't see this 3-arity case for the transducer version of `clojure.core/map`.

In my mind, the following are equivalent

(r/reducer [1 2 3] (map f))

(r/map f [1 2 3])

So the following should be equivalent:

;; Reducer

(fn [f1]
  (rfn [f1 k]
       ([ret k v]
        (f1 ret (f k v)))))

;; macroexpands to
(fn [f1]

  (fn
    ([] (f1))
    ([ret v] (f1 ret (f v)))

    ([ret k v] (f1 ret (f k v)))))

;; and should be equivalent to the transducer (map f):
(fn [rf]
  (fn
    ([] (rf))
    ([result] (rf result))
    ([result input]
     (rf result (f input)))
    ([result input & inputs]
     (rf result (apply f input inputs)))))

Yet they are clearly not the same: there is nothing in the transducer about `[ret k v]`. So I must be missing something fundamental about the relationship between reducers and transducers.

[Alex Miller]

This is a place where reducers and transducers diverge. Transducers don't have support for automatic kv reducing (there are some tricky details as to why this was possible in reducers but not as easy in transducers, which I mostly don't remember at this point). That is an area of possible future extension.

[Tianxiang Xiong]

OK, so would you say it's not good practice to do:

(r/reducer [1 2 3] (map f))

instead of 

(r/map f [1 2 3])

because the former doesn't create a reducer that handles kv-reduction? 

If so, it seems that `folder`/`reducer` are not fns intended for public consumption, since `rfn` is private and there's no easy way to create reducing function transformers that work with `folder`/`reducer`. Is this the case?

Creating a reducer from a transducer may not be very useful, given that `reduce`/`transduce` can be used to get sequential reduction either way. Creating a folder from a transducer, however, seems like it'd be useful--the transducer captures the what, while the folder captures the how (parallel via fork/join). So it'd be nice if

(r/folder [1 2 3] xf)

was the way to do it.