Hacker News Reader

A transducer transforms a reducing function. Its signature is rfn->rfn. The resulting rfn can then be used to reduce/fold from any collection/stream type into any other collection/stream type.

I don't see what your functions have to do with that.

(HN is going to collapse this comment because the code makes it too long).

My functions are exactly equivalent to transducers.

My link in the original comment goes over it at a more theoretical level.

But if you want runnable code, I've included Clojure below that translates between the two representations (there's some annoying multi-arity stuff I haven't handled very rigorously, but that's mainly an artifact of the complection in the traditional Clojure representation of transducers and goes away when you think of them as just `a -> List<b>`).

There's a line in the original article that the author doesn't go far enough on. "Everything is a fold." Yes more than that, folding is not just a function over a list, a fold is a list and vice versa (this holds for any algebraic datatype). Transducers are just one example of this, where Clojure has decided to turn a concrete data structure into a higher order function (wrongly I believe; although I haven't gone to the effort of truly specializing all my functions to verify my suspicions that you can actually get even better performance with the concrete data representation as long as you use specialized data containers with specialized behavior for the zero and one element cases).

  (defn tmap
    "Map transducer"
    [f]
    (fn [x] [(f x)]))

  (defn tfilter
    "Filter transducer"
    [f]
    (fn [x] (if (f x) [x] [])))

  (defn ttake
    "Take n elements"
    [n]
    (let [n-state (volatile! n)]
      (fn 
        [x]
        (let [current-n @n-state]
          (if (pos? current-n) 
            (do (vswap! n-state dec) [x]) 
            [])))))

  (defn simple-transducer->core-transducer
    [simple-transducer]
    (fn 
      [rf]
      (fn 
        ([] (rf))
        ([result] (rf result))
        ([result input] 
          (reduce rf result (simple-transducer input))))))

  (defn core-transducer->simple-transducer
    [core-transducer]
    (fn
      [x]
      ((core-transducer #(cons %2 %1)) [] x)))

  (defn catcomp
    ([f g]
      (fn [x] (mapcat g (f x))))
    ([f g & fs]
      (reduce catcomp (catcomp f g) fs)))

  (def example-simple-transducer
    (catcomp 
      (tmap inc) 
      (tfilter even?)
      (tmap inc)
      (ttake 2)))

  (defn example-simple-transducer-manual
    [x]
    (->> ((tmap inc) x)
         (mapcat (tfilter even?))
         (mapcat (tmap inc))
         ;; Stateful transducers are hard to work with manually
         ;; You have to define it outside of the function to maintain the state
         ;; This is true for traditional transducers as well
         ;; (mapcat (ttake 2))
         ))


  (def example-core-transducer
    (comp
      (map inc)
      (filter even?)
      (map inc)
      (take 2)))

  ;; Yields [3 5]
  (into [] (simple-transducer->core-transducer example-simple-transducer) [1 2 3 4 5])

  ;; Also yields [3 5]
  (into [] example-core-transducer [1 2 3 4 5])

  ;; Yields [3]
  (simple-transducer 1)

  ;; Also yields [3]
  ((core-transducer->simple-transducer example-core-transducer) 1)

Did you mean list<a> -> b? To my mind a transducer is a tranform + reducer

No I meant `a -> List<b>`. This is because a list is itself a fold (which is a reducer with an additional base case).

Nicely done.