23 ms·

Transducers are coming to Clojure

319 points by siavosh 12y ago

dustingetz 12y ago
Not sure I understand - so Clojure is getting first class support for lazy collections and curried combinators? Or am I missing the important part?
- _halgari 12y ago
  Many Clojure abstractions need things like map, filter, concat, etc. Reducers are eager, lazy-seqs are lazy, and core.async channels are lazy and push-based. This is a way to unify all these abstractions so that you can write a single map/filter/concat transform once, and use it in many different ways.
  - smrtinsert 12y ago
    Isn't there some overlap between this and extend-protocol? To my vague understanding this is from the functional composition angle instead of a type, but otherwise don't they accomplish the same thing?
  - dustingetz 12y ago
    > This is a way to unify all these abstractions so that you can write a single map/filter/concat transform once, and use it in many different ways. I don't understand why these things aren't all unified in the first place, it's just function composition we're talking about here right? Edit: I mean it's clearly not just simple function composition, but I don't understand why not (def xform (comp (map inc) (filter even?))) ; xform is a transducer (defn xform [aseq] (->> aseq (map inc) (filter even?))) ; xform is a fn Why do these have to be different things? Why is there a need for machinery to do what fn composition is supposed to do?
    - richhickey 12y ago
      Your typical definition of map, filter etc includes concrete usage of e.g. lists. These don't. Transducers are not just currying or partial application of the map function over lists, they isolate the logic of map, filter etc from lists or any particular context, allowing them to be used in very different (e.g. non-collection) contexts.
      - kazinator 12y ago
        By "map in a non-collection context", what would be an example? Say, mapping a boolean negation function over the bits of an integer, to produce its complement? How does that look with transducers?
        drcode 12y ago
        Well, the most obvious value to me is that you can create algorithms that defer their action- So instead of having a function that operates on a collection, you can have a function that will operate on a collection at a future date, even if the collection does not yet exist. (that's what the clojure reducer library does) (And if you say "deferring an action is just another term for 'functions'" then that's exactly the point, lifting more algorithmic logic into composable functions)
        kazinator 12y ago
        Alan Perlis Epigram #2.
      - dustingetz 12y ago
        > isolate the logic of map, filter etc from lists or any particular context so Functors (fmap)? fmap still uses regular old fns, no machinery. http://clojuredocs.org/clojure_contrib/clojure.contrib.generic.functor/fmap http://clojuredocs.org/clojure_contrib/clojure.contrib.gener... http://learnyouahaskell.com/making-our-own-types-and-typeclasses#the-functor-typeclass http://learnyouahaskell.com/making-our-own-types-and-typecla...
        12y ago
  - drcode 12y ago
    Yeah, when looking at core.async transformers and the reducer library, it seemed clear that there was some generality in there that could be factored out. Glad someone smarter than me figured out what it was.
- jzelinskie 12y ago
  I think this is just announcing that the Clojure core libraries are gaining another arity for many functions specifically for this usage so that you don't have to use (partial) or the short-hand #() syntax to use this pattern. I assume the goal is more community awareness and cleaner syntax for the re-use of this pattern.
  - richhickey 12y ago
    No, (map f) is not curried map. It returns an entirely different thing - a function of reducing function to reducing function, aka a reducing function transformer, aka a transducer.
    - avernet 12y ago
      Providing the signature of this new `map` function (e.g. as in Haskell's fmal http://www.haskell.org/hoogle/?hoogle=fmap http://www.haskell.org/hoogle/?hoogle=fmap), would certainly go a long way towards helping people understand what this `map` does.
      - richhickey 12y ago
        These sigs are for the arities below only. map f: (a->b)->(x->b->x)->(x->a->x) filter pred: (a->bool)->(x->a->x)->(x->a->x) flatmap f: (a->[b])->(x->b->x)->(x->a->x) etc.
        spion 12y ago
        So, a transduceMap implementation would be this I guess? transduceMap :: (b -> a) -> (acc -> a -> acc) -> (acc -> b -> acc) transduceMap f = \reduceFn -> \acc el -> reduceFn acc (f el) lambda added for clarity (no pun intended), however types are easier to match when using this syntax: transduceMap :: (b -> a) -> (acc -> a -> acc) -> acc -> b -> acc transduceMap f reduceFn acc el = reduceFn acc (f el)
        avernet 12y ago
        OK, maybe we're getting somewhere. Let me try to write this `map`, just to see. I'm using Scala, so I can put some types, and have the compiler yell at me if I'm doing something overtly wrong (I need all the help I can get!). For clarity, let's define a type alias for reducers: type Reducer[X, A] = (X, A) ⇒ X Let's define `map` to match the type definition you provided. And with that type definition, I only see one way in which the function can be implemented. So it must be: def map[X, A, B](f: A ⇒ B): (Reducer[X, B] ⇒ Reducer[X, A]) = (redB: Reducer[X, B]) ⇒ (x: X, a: A) ⇒ redB(x, f(a)) How can I use this? Let's try the following: def addup(zero: Int, a: List[Int]) = a.foldLeft(zero)(_ + _) def parseList(a: List[String]) = a.map(_.toInt) map(parseList)(addup)(1, List("7", "8")) This returns 16. OK, parsing the list, and adding up starting from 1. But it doesn't look to me like `map` implements anything like the usual semantic of map. It just converts the data structure, and applies the reducer. What am I missing here?
undershirt 12y ago
I just saw this morning that many functions in core.async are marked "Deprecated - this function will be removed. Use transformer instead." I guess Tranducers will provide a generic replacement for those. Looking forward to seeing some examples.
tel 12y ago
This sort of reminds me of the Church-encoded form of a list. newtype Fold a = Fold (forall r . (a -> r -> r) -> r -> r) fold :: [a] -> Fold a fold xs = Fold (spin xs) where spin [] cons nil = nil spin (a:as) cons nil = cons a (spin as cons nil) refold :: Fold a -> [a] refold (Fold f) = f (:) [] Notably, since `fold` and `refold` are isomorphisms then we can do everything we can do to `[a]` to `Fold a` map :: (a -> b) -> (Fold a -> Fold b) map x (Fold f) = Fold $ \cons nil -> f (cons . x) nil filter :: (a -> Bool) -> Fold a -> Fold a filter p (Fold f) = Fold $ \cons nil -> f (\a r -> if p a then cons a r else r) nil but all of this work is done without concrete reference to `(:)` and `[]`... you instead just use stand-ins I've been calling cons and nil. What's nice about this is that `Fold` can be used to build anything which can be "constructed from the left" foldSet :: Fold a -> Set a foldSet (Fold f) = f Set.insert Set.empty It's sort of dual to the stuff I was exploring in Swift here [0]. It also creates laziness for free because you can't really execute the chain until the end—Church-encoding is really a form of continuation passing. The downside of this idea is that each time you "consume" a Fold you redo work—there's no place to put caching necessarily. Maybe that's what they're solving with the Fold transformers representation. [0] http://tel.github.io/2014/07/30/immutable_enumeration_in_swift/ http://tel.github.io/2014/07/30/immutable_enumeration_in_swi...
- richhickey 12y ago
  Kind of. The idea is to get out of the context of the 'whole job' (the ->r->r bit above) and focus on transformations of the step function (a->r->r) -> (b->r->r) {using your arg order above}. Not talking about the whole job (i.e. the source and result) makes for much more highly reusable components, especially when the jobs don't produce concrete results but, e.g., run indefinitely, like channel transformations.
  - tel 12y ago
    Yeah, I'm less sure about the properties as you go this way. You ought to be able to get an Arrow out of it and it's a pretty natural idea.
- lmm 12y ago
graycat 12y ago
I'm sorry, but from the OP I can't be at all sure I can understand notation such as: ;;reducing function signature whatever, input -> whatever or ;;transducer signature (whatever, input -> whatever) -> (whatever, input -> whatever) Or, in mathematics there is some notation f: A --> B where A and B are sets and f is a function. This notation means that for each element x in set A, function f returns value f(x) in set B. Seems clear enough. Maybe the notation in the OP is related? How I can't be sure I can guess at all correctly.
- richhickey 12y ago
  a la Haskell: ;;reducing fn x->a->x ;;transducer fn (x->a->x)->(x->b->x)
  - mike_ivanov 12y ago
    So there's some common ground between map, filter, flatmap, etc and these transducers allow you to compose those common-ground representations? I mean, you can define `map` as a callable chain of `(key-by #(true)) -> (map-apply fn) -> (filter-trues)` and `filter` as `(key-by predicate) -> (map-apply identity) -> (filter-trues)` where key-by, map-apply and filter-trues are some low-level primitives? Is that correct?
    - richhickey 12y ago
      Precisely the opposite - these functions compose because they are representation-free.
  - zem 12y ago
    or, to steal ashley yakeley's marvellous quip, "every sufficiently well-documented lisp program contains an ML program in its comments" (:
    - xmonkee 12y ago
      lol
unlogic 12y ago
This looks exciting, but I'm confused about the decision to add extra arity to collection-manipulating functions. "filter" that returns a collection or a transducer depending only on arity seems a little counter-intuitive.
- swannodette 12y ago
  It's a pretty well considered tradeoff in my opinion - no existing code breaks while at the same time all the transformation functions now have the same semantic interpretation when used in different contexts. The alternative would be to replicate the notion of `map`, `filter`, etc. again and again as occurred with reducers and higher level core.async operations on channels.
  - unlogic 12y ago
    My argument is why not making it look like: (comp (transducer map inc) (transducer filter even?)) Of course, it's more typing and doesn't look as nice as single-arity map, but it goes along quite well with (partial map inc). I can be wrong but to this date Clojure didn't have a function that produces completely different things based on arity, did it?
    - swannodette 12y ago
      Not sure how what you're suggesting could possibly work unless transducer has a table of fn to transducer - this doesn't sound like a good idea. I recommend looking at the implementations which have landed in Clojure master to see what I'm talking about.
      - malisper 12y ago
        You could just make them transducer-map, transducer-filter, etc. There is no reason the exact same name should be used for two different things. It is a lot harder to tell the difference between (map inc) and (map inc xs) then it is to tell the difference between (transducer-map inc) and (map inc xs).
nohat00 12y ago
> "these transformers were never exposed a la carte, instead being encapsulated by the macrology of reducers." What does 'macrology' mean in this context? Is this a common usage? Or a novel application of a word that ordinarily means "long and tedious talk without much substance"
- prospero 12y ago
  It means that reducers were some macro sugar atop the underlying mechanism described in the post. See https://github.com/clojure/clojure/blob/master/src/clj/clojure/core/reducers.clj#L139 https://github.com/clojure/clojure/blob/master/src/clj/cloju...
  - nohat00 12y ago
    ... so 'macrology' means "use of macros" rather than "long and tedious talk without much substance"? Is this usage specific to Clojure, or to all languages that have macros? It seems like a pretty bizarre repurposing of a word that already has a very different meaning, and I wonder how widespread it is. Are we too late to stop it?
    - mikeash 12y ago
      It applies universally and you're probably decades too late to stop it. http://www.catb.org/jargon/html/M/macrology.html http://www.catb.org/jargon/html/M/macrology.html
    - e12e 12y ago
      Well, it's the use of macros to avoid having to write code that has the characteristics of macrology. If nothing else, it's sort of strangely recursive, like perhaps many "complex macros" are...
vbit 12y ago
I'm not quite sure what this means, so here's my attempt to translate this into Python. A reducer is a function such as `add`: def add(sum, num): return sum + num Of course you can plug `add` directly in `reduce(add, [1, 2, 3], 0)` which gives `6`. A transducer is an object returned by a call such as `map(lambda x: x + 1)`. You can now apply the transducer to a reducer and get another reducer. map_inc = map(lambda x: x + 1) add_inc = map_inc(add) Our first reducer simply added, but the next one increments and then adds. We can use it as `reduce(add_inc, [1, 2, 3], 0)` which gives, I'm guessing, `9`. Since the transducer returns a reducer as well, we can compose transducers: r1 = filter(is_even)(map(increment)(add)) # use r1 in reduce() It seems in clojure, reduce() isn't the only useful function that works with reducers, there are others which makes this all worthwhile. Is my translation accurate?
- dopamean 12y ago
  I'm also hoping for an informative answer to this question. Anyone?
  - spion 12y ago
    I think its just reduce, but in general its possible to write many implementations of reduce. It could be applied to lazy sequences, observables (to get a future or a new observable) and many other reducible things
    - richhickey 12y ago
      Yes, it's not just the 'reduce' function. You can think of many kinds of jobs in terms of seeded left reductions. Here's an example of some of the functions that can apply a transducer to their internal 'step' operation: https://gist.github.com/richhickey/b5aefa622180681e1c81 https://gist.github.com/richhickey/b5aefa622180681e1c81 Note how one transducer stack is created and can be reused in many different contexts.
- bcoates 12y ago
  If I understand right (I may not): In Python, the (complex, generic) iter() protocol is how every container provides a method to iterate itself, and reduce is a trivial application of a reducer (like your add function) to a container by using the iter protocol. In Clojure, it's the opposite: there is a reduce() protocol and every reducible container knows how to reduce itself. the traditional reduce function just takes a reducer and a reducible and performs the reduce protocol on it. As there's a bunch of different kinds of containers with different rules, the best way to implement the reduce protocol on them is different for each, and there might be weird specialized reducers that are parallel or asynchronous or lazy or whatever. Transducers allow you to composibly transform reducers into different reducers, which can then be handed to the reduce protocol. As it turns out, most (all?) normal container->container operations, like map and filter, have corresponding transducers. Here's the good part: if you have a reduce protocol and a complete set of tranducers, containers don't need to be mappable. The map(fn, iterable) function needs to know how to iterate; mapping(fn) doesn't care about containers at all, and is fully general to mapping any reducible for free. So you can write a transducer to produce the effect of any map or filter-like operation without touching iter(). As an added bonus, the code is more efficient: reduce( add, map( lambda x: x + 1, xrange(10**9) ), 0 ) eagerly builds a gigantic mapped list (barring sophisticated laziness or loop-fusion optimizations), but reduce( mapping( lambda x: x + 1 )(add), xrange(10**9), 0 ) is equivalent and trivially runs in O(1) space on one element of xrange at a time. PS: python translation of mapping from http://clojure.com/blog/2012/05/15/anatomy-of-reducer.html http://clojure.com/blog/2012/05/15/anatomy-of-reducer.html converted to named functions to be more pythonic: def mapping( transformation ): def transducer( reducer ): def new_reducer( accum, next ): return reducer(accum, transformation(next) ) return new_reducer return transducer
pron 12y ago
I think that a good way to understand transducers is to look at their implementation (shortened a bit). Here it is for map: ([f] (fn [f1] (fn ([result input] (f1 result (f input))) ([result input & inputs] (f1 result (apply f input inputs)))))) filter: ([pred] (fn [f1] (fn ([result input] (if (pred input) (f1 result input) result))))) And it gets more interesting with take: ([n] (fn [f1] (let [na (atom n)] (fn ([result input] (let [n @na nn (swap! na dec) result (if (pos? n) (f1 result input) result)] (if (not (pos? nn)) (reduced result) ; a terminal value indicating "don't reduce further" result))))))) The transducer is supplied with the reducer next in the chain (f1) and returns a reducer function that gets fed with the reduced value by the preceding reduction (result) and the next element (input). Note how the take transducer maintains internal state with an atom. This could get a little tricky for more elaborate reductions, as how the internal state is maintained might have a significant effect on performance, depending on exactly how the reduction is performed. For example, if the reduction is done in parallel (say, with fork-join), then an internal state that's updated with locks (like refs) might significantly slow down -- or even deadlock -- the reduction. AFAICT mapcat still only returns lazy-seqs.
- richhickey 12y ago
  Because mapcat's signature was not amenable to the additional arity, there's now also flatmap (note you can write the lazy collection version of any transducer fn using sequence as below): (defn flatmap "maps f over coll and concatenates the results. Thus function f should return a collection. Returns a transducer when no collection is provided." ([f] (fn [f1] (fn ([] (f1)) ([result] (f1 result)) ([result input] (reduce (preserving-reduced f1) result (f input)))))) ([f coll] (sequence (flatmap f) coll)))
- tel 12y ago
  Interesting. Continuing to try to analyze these in Haskell, I think this is a direct translation: -- z is just there to not clobber some standard prelude names type Red r a = r -> a -> r zmap :: (b -> a) -> Red r a -> Red r b zmap f f1 result input = f1 result (f input) zfilt :: (a -> Bool) -> Red r a -> Red r a zfilt p f1 result input = if p input then f1 result input else result ztake :: Int -> Red r a -> (r -> a -> Maybe r) ztake n f1 = run n where run n result input = let n' = n - 1 result = if n >= 0 then f1 result input else result in if n' == 0 then Nothing else Just result I wanted to post this mostly to note that `map` is mapping contravariantly here. Is there something I'm missing? I had that occurring when I was playing around with this idea before looking at the source as well... to fix it I had to consider the type `Red r a -> r` so that the `a` was covariant again.
davdar 12y ago
Clojure transducers are exactly signal functions from Haskell FRP literature, for those interested in such a connection.
- richhickey 12y ago
  I'm not yet seeing that, given: Signal a :: Time -> a SF a b :: Signal a -> Signal b thus (Time -> a) -> (Time -> b) not exactly: (x->a->x) -> (x->b->x) Can you point me to a paper that makes the connection clear?
  - davdar 12y ago
    In the non-continuous FRP literature[1], i.e. the kind you actually implement, SF a b = [a] -> [b], which is isomorphic to: Fold a -> Fold b, where Fold a = (exists s. (s, s -> (a, s))), which isomorphic to the type the author writes for transducer: ;;transducer signature (whatever, input -> whatever) -> (whatever, input -> whatever) Signal functions are easy to program in Haskell using arrow syntax, and many libraries already exist for dealing with signal functions. [1]: Nilsson, Courtney and Peterson. Functional Reactive Programming, Continued. Haskell '02. http://haskell.cs.yale.edu/wp-content/uploads/2011/02/workshop-02.pdf http://haskell.cs.yale.edu/wp-content/uploads/2011/02/worksh... (see section 4) edit: formatting
- deleted 12y ago
  [deleted]
fnordsensei 12y ago
Tentative benchmark results have surfaced: https://github.com/thheller/transduce-bench https://github.com/thheller/transduce-bench Add salt according to taste.
- mduerksen 12y ago
  The benchmark is wrong atm, the compared functions do not yield the same result. (comp (map inc) (filter even?)) means filtering first, then incrementing. The opposite for (->> data (map inc) (filter even?) ... - which is not the same. And of course, it also means that the latter has to increment the double amount of numbers. EDIT: It was me who was wrong, thanks for the corrections. Pitfall successfully identified :)
  - pyrtsa 12y ago
    Nope, that's the funny feature of transducers. Like lenses in Haskell, transducers compose in reversed order. (sequence (comp (map inc) (filter even?)) (range 10)) ;;=> (2 4 6 8 10) (->> (range 10) (map inc) (filter even?)) ;;=> (2 4 6 8 10) Both test functions in transduce-bench return 250000500000.
  - richhickey 12y ago
    It seems counterintuitive, but composing transducers yields a reducing function that runs the transformation steps left->right. What you are composing is the reducing function transformations (right to left, ordinary composition), but their result, having been built inside-out, runs the steps outside-in. So (comp tx1 tx2...) runs in same order as (->> xs tx1 tx2...)
oafitupa 12y ago
As someone who tried Clojure and failed, serious question: Does anyone actually use all these crazy features/patterns that keep getting added/discovered and talked about? I ask because even though I can imagine someone smart mastering these things and programming faster, I can't imagine a second person being able to understand his code, maintain it, and generally be productive. I imagine the second person losing a lot of time trying to understand what is going on, or even thinking he understood but in reality he didn't and messing things up. So how do you even form a Clojure team?
- calibraxis 12y ago
  This sentence is important: "There will be more explanations, tutorials and derivations to follow, here and elsewhere." If a team ever adopts transducers, it'll generally be after a lot of explanations exist and has been made easy to understand. Clojure teams can defend themselves against exotic features like any other team: code review, conventions, etc. If I pull in some weird new feature, others had better be ok with it. (Obviously, what I'm saying doesn't apply to every team in the world; presumably there's a spectrum of ways to deal, or fail to deal, with this problem.) In my view, Clojure teams are formed via a political process, like any other programming language adoption.
- JackMorgan 12y ago
  It's a mindset change. Other than macros, which fundamentally alter the flow of code in a very non-standard way, the rest of these "crazy patterns and features" in Clojure are just like the crazy libraries used by typical Java/Ruby/C# developers, only thousands of times simpler. If I came to you and said, "does anyone even use these tens of thousands of libraries in Maven? How do other developers work on this afterwards, they'd have to learn all these new APIs!" I'd likely get a response like, "they'd just be expected to", with a chuckle. The mindset I've seen a lot is that language features are "too hard" to learn and should be avoided, but library complexity is beyond reproach and is rarely questioned. Clojure the language takes the approach that it's better to provide a dozen simple but incredibly composable tools that can easily replace a lot of duplicated boilerplate in other languages. Like these transducers, in Java/C# they'd likely be one of the design patterns that needs a whole set of classes to make what he shows in a few characters. Would you rather learn to write and read maintain a handful of classes, or just learn what those few characters mean? I don't get paid by the line, and any abstraction built into the language like that is a few more classes I don't have to maintain and possibly implement incorrectly in some subtle way. Like I said, it's just a mindset change. I know a company that only uses Clojure, and they hire a lot of entry level developers who haven't yet gotten stuck in a mindset that "languages are too hard; libraries are easy". They have great success with that, and their entry level guys are up to speed much faster than those in my shop, using .NET, where they have to learn a new language AND a mountain of boiler plate code using dozens of libraries and frameworks.
tel 12y ago
This is about as close as I could get in Haskell so far. It uses a slight twist on (x -> a -> x) called a Fold (which has a lot of great properties—it's a profunctor, an applicative, and a comonad). Nicely, this construction lets us write `take` purely! {-# LANGUAGE GADTs #-} {-# LANGUAGE RankNTypes #-} {-# LANGUAGE TypeOperators #-} import Control.Arrow import Control.Category import qualified Prelude import Prelude hiding (id, (.)) data Fold a r where Fold :: (a -> x -> x) -> x -> (x -> r) -> Fold a r data Pair a b = Pair !a !b pfst :: Pair a b -> a pfst (Pair a b) = a psnd :: Pair a b -> b psnd (Pair a b) = b newtype (~>) a b = Arr (forall r . Fold b r -> Fold a r) instance Category (~>) where id = Arr id Arr f . Arr g = Arr (g . f) amap :: (a -> b) -> (a ~> b) amap f = Arr (\(Fold cons nil fin) -> Fold (cons . f) nil fin) afilter :: (a -> Bool) -> (a ~> a) afilter p = Arr $ \(Fold cons nil fin) -> let cons' = \a x -> if p a then cons a x else x in Fold cons' nil fin fold :: Fold a r -> [a] -> r fold (Fold cons nil fin) = fin . spin where spin [] = nil spin (a:as) = cons a (spin as) asequence :: (a ~> b) -> ([a] -> [b]) asequence (Arr f) = fold (f (Fold (:) [] id)) aflatmap :: (a -> [b]) -> (a ~> b) aflatmap f = Arr $ \(Fold cons nil fin) -> Fold (\a x -> foldr cons x (f a)) nil fin atake :: Int -> (a ~> a) atake n = Arr $ \(Fold cons nil fin) -> let cons' = \a x n -> if n > 0 then cons a (x (n-1)) else x n in Fold cons' (const nil) (\x -> fin (x n))
- phobbs 12y ago
  Brilliant, this clears up the usage a lot more than the rest of the prose in the comment thread.

319 points by siavosh 12y ago

Not sure I understand - so Clojure is getting first class support for lazy collections and curried combinators? Or am I missing the important part?

_halgari 12y ago
Many Clojure abstractions need things like map, filter, concat, etc. Reducers are eager, lazy-seqs are lazy, and core.async channels are lazy and push-based. This is a way to unify all these abstractions so that you can write a single map/filter/concat transform once, and use it in many different ways.
- smrtinsert 12y ago
  Isn't there some overlap between this and extend-protocol? To my vague understanding this is from the functional composition angle instead of a type, but otherwise don't they accomplish the same thing?
- dustingetz 12y ago
  > This is a way to unify all these abstractions so that you can write a single map/filter/concat transform once, and use it in many different ways. I don't understand why these things aren't all unified in the first place, it's just function composition we're talking about here right? Edit: I mean it's clearly not just simple function composition, but I don't understand why not (def xform (comp (map inc) (filter even?))) ; xform is a transducer (defn xform [aseq] (->> aseq (map inc) (filter even?))) ; xform is a fn Why do these have to be different things? Why is there a need for machinery to do what fn composition is supposed to do?
  - richhickey 12y ago
    Your typical definition of map, filter etc includes concrete usage of e.g. lists. These don't. Transducers are not just currying or partial application of the map function over lists, they isolate the logic of map, filter etc from lists or any particular context, allowing them to be used in very different (e.g. non-collection) contexts.
    - kazinator 12y ago
      By "map in a non-collection context", what would be an example? Say, mapping a boolean negation function over the bits of an integer, to produce its complement? How does that look with transducers?
      - drcode 12y ago
        Well, the most obvious value to me is that you can create algorithms that defer their action- So instead of having a function that operates on a collection, you can have a function that will operate on a collection at a future date, even if the collection does not yet exist. (that's what the clojure reducer library does) (And if you say "deferring an action is just another term for 'functions'" then that's exactly the point, lifting more algorithmic logic into composable functions)
        kazinator 12y ago
        Alan Perlis Epigram #2.
    - dustingetz 12y ago
      > isolate the logic of map, filter etc from lists or any particular context so Functors (fmap)? fmap still uses regular old fns, no machinery. http://clojuredocs.org/clojure_contrib/clojure.contrib.generic.functor/fmap http://clojuredocs.org/clojure_contrib/clojure.contrib.gener... http://learnyouahaskell.com/making-our-own-types-and-typeclasses#the-functor-typeclass http://learnyouahaskell.com/making-our-own-types-and-typecla...
      - 12y ago
- drcode 12y ago
  Yeah, when looking at core.async transformers and the reducer library, it seemed clear that there was some generality in there that could be factored out. Glad someone smarter than me figured out what it was.
jzelinskie 12y ago
I think this is just announcing that the Clojure core libraries are gaining another arity for many functions specifically for this usage so that you don't have to use (partial) or the short-hand #() syntax to use this pattern. I assume the goal is more community awareness and cleaner syntax for the re-use of this pattern.
- richhickey 12y ago
  No, (map f) is not curried map. It returns an entirely different thing - a function of reducing function to reducing function, aka a reducing function transformer, aka a transducer.
  - avernet 12y ago
    Providing the signature of this new `map` function (e.g. as in Haskell's fmal http://www.haskell.org/hoogle/?hoogle=fmap http://www.haskell.org/hoogle/?hoogle=fmap), would certainly go a long way towards helping people understand what this `map` does.
    - richhickey 12y ago
      These sigs are for the arities below only. map f: (a->b)->(x->b->x)->(x->a->x) filter pred: (a->bool)->(x->a->x)->(x->a->x) flatmap f: (a->[b])->(x->b->x)->(x->a->x) etc.
      - spion 12y ago
        So, a transduceMap implementation would be this I guess? transduceMap :: (b -> a) -> (acc -> a -> acc) -> (acc -> b -> acc) transduceMap f = \reduceFn -> \acc el -> reduceFn acc (f el) lambda added for clarity (no pun intended), however types are easier to match when using this syntax: transduceMap :: (b -> a) -> (acc -> a -> acc) -> acc -> b -> acc transduceMap f reduceFn acc el = reduceFn acc (f el)
      - avernet 12y ago
        OK, maybe we're getting somewhere. Let me try to write this `map`, just to see. I'm using Scala, so I can put some types, and have the compiler yell at me if I'm doing something overtly wrong (I need all the help I can get!). For clarity, let's define a type alias for reducers: type Reducer[X, A] = (X, A) ⇒ X Let's define `map` to match the type definition you provided. And with that type definition, I only see one way in which the function can be implemented. So it must be: def map[X, A, B](f: A ⇒ B): (Reducer[X, B] ⇒ Reducer[X, A]) = (redB: Reducer[X, B]) ⇒ (x: X, a: A) ⇒ redB(x, f(a)) How can I use this? Let's try the following: def addup(zero: Int, a: List[Int]) = a.foldLeft(zero)(_ + _) def parseList(a: List[String]) = a.map(_.toInt) map(parseList)(addup)(1, List("7", "8")) This returns 16. OK, parsing the list, and adding up starting from 1. But it doesn't look to me like `map` implements anything like the usual semantic of map. It just converts the data structure, and applies the reducer. What am I missing here?

undershirt 12y ago

I just saw this morning that many functions in core.async are marked "Deprecated - this function will be removed. Use transformer instead." I guess Tranducers will provide a generic replacement for those. Looking forward to seeing some examples.

tel 12y ago

This sort of reminds me of the Church-encoded form of a list. newtype Fold a = Fold (forall r . (a -> r -> r) -> r -> r) fold :: [a] -> Fold a fold xs = Fold (spin xs) where spin [] cons nil = nil spin (a:as) cons nil = cons a (spin as cons nil) refold :: Fold a -> [a] refold (Fold f) = f (:) [] Notably, since `fold` and `refold` are isomorphisms then we can do everything we can do to `[a]` to `Fold a` map :: (a -> b) -> (Fold a -> Fold b) map x (Fold f) = Fold $ \cons nil -> f (cons . x) nil filter :: (a -> Bool) -> Fold a -> Fold a filter p (Fold f) = Fold $ \cons nil -> f (\a r -> if p a then cons a r else r) nil but all of this work is done without concrete reference to `(:)` and `[]`... you instead just use stand-ins I've been calling cons and nil. What's nice about this is that `Fold` can be used to build anything which can be "constructed from the left" foldSet :: Fold a -> Set a foldSet (Fold f) = f Set.insert Set.empty It's sort of dual to the stuff I was exploring in Swift here [0]. It also creates laziness for free because you can't really execute the chain until the end—Church-encoding is really a form of continuation passing. The downside of this idea is that each time you "consume" a Fold you redo work—there's no place to put caching necessarily. Maybe that's what they're solving with the Fold transformers representation. [0] http://tel.github.io/2014/07/30/immutable_enumeration_in_swift/ http://tel.github.io/2014/07/30/immutable_enumeration_in_swi...

richhickey 12y ago
Kind of. The idea is to get out of the context of the 'whole job' (the ->r->r bit above) and focus on transformations of the step function (a->r->r) -> (b->r->r) {using your arg order above}. Not talking about the whole job (i.e. the source and result) makes for much more highly reusable components, especially when the jobs don't produce concrete results but, e.g., run indefinitely, like channel transformations.
- tel 12y ago
  Yeah, I'm less sure about the properties as you go this way. You ought to be able to get an Arrow out of it and it's a pretty natural idea.
lmm 12y ago

graycat 12y ago

I'm sorry, but from the OP I can't be at all sure I can understand notation such as: ;;reducing function signature whatever, input -> whatever or ;;transducer signature (whatever, input -> whatever) -> (whatever, input -> whatever) Or, in mathematics there is some notation f: A --> B where A and B are sets and f is a function. This notation means that for each element x in set A, function f returns value f(x) in set B. Seems clear enough. Maybe the notation in the OP is related? How I can't be sure I can guess at all correctly.

richhickey 12y ago
a la Haskell: ;;reducing fn x->a->x ;;transducer fn (x->a->x)->(x->b->x)
- mike_ivanov 12y ago
  So there's some common ground between map, filter, flatmap, etc and these transducers allow you to compose those common-ground representations? I mean, you can define `map` as a callable chain of `(key-by #(true)) -> (map-apply fn) -> (filter-trues)` and `filter` as `(key-by predicate) -> (map-apply identity) -> (filter-trues)` where key-by, map-apply and filter-trues are some low-level primitives? Is that correct?
  - richhickey 12y ago
    Precisely the opposite - these functions compose because they are representation-free.
- zem 12y ago
  or, to steal ashley yakeley's marvellous quip, "every sufficiently well-documented lisp program contains an ML program in its comments" (:
  - xmonkee 12y ago
    lol

unlogic 12y ago

This looks exciting, but I'm confused about the decision to add extra arity to collection-manipulating functions. "filter" that returns a collection or a transducer depending only on arity seems a little counter-intuitive.

swannodette 12y ago
It's a pretty well considered tradeoff in my opinion - no existing code breaks while at the same time all the transformation functions now have the same semantic interpretation when used in different contexts. The alternative would be to replicate the notion of `map`, `filter`, etc. again and again as occurred with reducers and higher level core.async operations on channels.
- unlogic 12y ago
  My argument is why not making it look like: (comp (transducer map inc) (transducer filter even?)) Of course, it's more typing and doesn't look as nice as single-arity map, but it goes along quite well with (partial map inc). I can be wrong but to this date Clojure didn't have a function that produces completely different things based on arity, did it?
  - swannodette 12y ago
    Not sure how what you're suggesting could possibly work unless transducer has a table of fn to transducer - this doesn't sound like a good idea. I recommend looking at the implementations which have landed in Clojure master to see what I'm talking about.
    - malisper 12y ago
      You could just make them transducer-map, transducer-filter, etc. There is no reason the exact same name should be used for two different things. It is a lot harder to tell the difference between (map inc) and (map inc xs) then it is to tell the difference between (transducer-map inc) and (map inc xs).

nohat00 12y ago

> "these transformers were never exposed a la carte, instead being encapsulated by the macrology of reducers." What does 'macrology' mean in this context? Is this a common usage? Or a novel application of a word that ordinarily means "long and tedious talk without much substance"

prospero 12y ago
It means that reducers were some macro sugar atop the underlying mechanism described in the post. See https://github.com/clojure/clojure/blob/master/src/clj/clojure/core/reducers.clj#L139 https://github.com/clojure/clojure/blob/master/src/clj/cloju...
- nohat00 12y ago
  ... so 'macrology' means "use of macros" rather than "long and tedious talk without much substance"? Is this usage specific to Clojure, or to all languages that have macros? It seems like a pretty bizarre repurposing of a word that already has a very different meaning, and I wonder how widespread it is. Are we too late to stop it?
  - mikeash 12y ago
    It applies universally and you're probably decades too late to stop it. http://www.catb.org/jargon/html/M/macrology.html http://www.catb.org/jargon/html/M/macrology.html
  - e12e 12y ago
    Well, it's the use of macros to avoid having to write code that has the characteristics of macrology. If nothing else, it's sort of strangely recursive, like perhaps many "complex macros" are...

vbit 12y ago

I'm not quite sure what this means, so here's my attempt to translate this into Python. A reducer is a function such as `add`: def add(sum, num): return sum + num Of course you can plug `add` directly in `reduce(add, [1, 2, 3], 0)` which gives `6`. A transducer is an object returned by a call such as `map(lambda x: x + 1)`. You can now apply the transducer to a reducer and get another reducer. map_inc = map(lambda x: x + 1) add_inc = map_inc(add) Our first reducer simply added, but the next one increments and then adds. We can use it as `reduce(add_inc, [1, 2, 3], 0)` which gives, I'm guessing, `9`. Since the transducer returns a reducer as well, we can compose transducers: r1 = filter(is_even)(map(increment)(add)) # use r1 in reduce() It seems in clojure, reduce() isn't the only useful function that works with reducers, there are others which makes this all worthwhile. Is my translation accurate?

dopamean 12y ago
I'm also hoping for an informative answer to this question. Anyone?
- spion 12y ago
  I think its just reduce, but in general its possible to write many implementations of reduce. It could be applied to lazy sequences, observables (to get a future or a new observable) and many other reducible things
  - richhickey 12y ago
    Yes, it's not just the 'reduce' function. You can think of many kinds of jobs in terms of seeded left reductions. Here's an example of some of the functions that can apply a transducer to their internal 'step' operation: https://gist.github.com/richhickey/b5aefa622180681e1c81 https://gist.github.com/richhickey/b5aefa622180681e1c81 Note how one transducer stack is created and can be reused in many different contexts.
bcoates 12y ago
If I understand right (I may not): In Python, the (complex, generic) iter() protocol is how every container provides a method to iterate itself, and reduce is a trivial application of a reducer (like your add function) to a container by using the iter protocol. In Clojure, it's the opposite: there is a reduce() protocol and every reducible container knows how to reduce itself. the traditional reduce function just takes a reducer and a reducible and performs the reduce protocol on it. As there's a bunch of different kinds of containers with different rules, the best way to implement the reduce protocol on them is different for each, and there might be weird specialized reducers that are parallel or asynchronous or lazy or whatever. Transducers allow you to composibly transform reducers into different reducers, which can then be handed to the reduce protocol. As it turns out, most (all?) normal container->container operations, like map and filter, have corresponding transducers. Here's the good part: if you have a reduce protocol and a complete set of tranducers, containers don't need to be mappable. The map(fn, iterable) function needs to know how to iterate; mapping(fn) doesn't care about containers at all, and is fully general to mapping any reducible for free. So you can write a transducer to produce the effect of any map or filter-like operation without touching iter(). As an added bonus, the code is more efficient: reduce( add, map( lambda x: x + 1, xrange(10**9) ), 0 ) eagerly builds a gigantic mapped list (barring sophisticated laziness or loop-fusion optimizations), but reduce( mapping( lambda x: x + 1 )(add), xrange(10**9), 0 ) is equivalent and trivially runs in O(1) space on one element of xrange at a time. PS: python translation of mapping from http://clojure.com/blog/2012/05/15/anatomy-of-reducer.html http://clojure.com/blog/2012/05/15/anatomy-of-reducer.html converted to named functions to be more pythonic: def mapping( transformation ): def transducer( reducer ): def new_reducer( accum, next ): return reducer(accum, transformation(next) ) return new_reducer return transducer

pron 12y ago

I think that a good way to understand transducers is to look at their implementation (shortened a bit). Here it is for map: ([f] (fn [f1] (fn ([result input] (f1 result (f input))) ([result input & inputs] (f1 result (apply f input inputs)))))) filter: ([pred] (fn [f1] (fn ([result input] (if (pred input) (f1 result input) result))))) And it gets more interesting with take: ([n] (fn [f1] (let [na (atom n)] (fn ([result input] (let [n @na nn (swap! na dec) result (if (pos? n) (f1 result input) result)] (if (not (pos? nn)) (reduced result) ; a terminal value indicating "don't reduce further" result))))))) The transducer is supplied with the reducer next in the chain (f1) and returns a reducer function that gets fed with the reduced value by the preceding reduction (result) and the next element (input). Note how the take transducer maintains internal state with an atom. This could get a little tricky for more elaborate reductions, as how the internal state is maintained might have a significant effect on performance, depending on exactly how the reduction is performed. For example, if the reduction is done in parallel (say, with fork-join), then an internal state that's updated with locks (like refs) might significantly slow down -- or even deadlock -- the reduction. AFAICT mapcat still only returns lazy-seqs.

richhickey 12y ago
Because mapcat's signature was not amenable to the additional arity, there's now also flatmap (note you can write the lazy collection version of any transducer fn using sequence as below): (defn flatmap "maps f over coll and concatenates the results. Thus function f should return a collection. Returns a transducer when no collection is provided." ([f] (fn [f1] (fn ([] (f1)) ([result] (f1 result)) ([result input] (reduce (preserving-reduced f1) result (f input)))))) ([f coll] (sequence (flatmap f) coll)))
tel 12y ago
Interesting. Continuing to try to analyze these in Haskell, I think this is a direct translation: -- z is just there to not clobber some standard prelude names type Red r a = r -> a -> r zmap :: (b -> a) -> Red r a -> Red r b zmap f f1 result input = f1 result (f input) zfilt :: (a -> Bool) -> Red r a -> Red r a zfilt p f1 result input = if p input then f1 result input else result ztake :: Int -> Red r a -> (r -> a -> Maybe r) ztake n f1 = run n where run n result input = let n' = n - 1 result = if n >= 0 then f1 result input else result in if n' == 0 then Nothing else Just result I wanted to post this mostly to note that `map` is mapping contravariantly here. Is there something I'm missing? I had that occurring when I was playing around with this idea before looking at the source as well... to fix it I had to consider the type `Red r a -> r` so that the `a` was covariant again.

davdar 12y ago

Clojure transducers are exactly signal functions from Haskell FRP literature, for those interested in such a connection.

richhickey 12y ago
I'm not yet seeing that, given: Signal a :: Time -> a SF a b :: Signal a -> Signal b thus (Time -> a) -> (Time -> b) not exactly: (x->a->x) -> (x->b->x) Can you point me to a paper that makes the connection clear?
- davdar 12y ago
  In the non-continuous FRP literature[1], i.e. the kind you actually implement, SF a b = [a] -> [b], which is isomorphic to: Fold a -> Fold b, where Fold a = (exists s. (s, s -> (a, s))), which isomorphic to the type the author writes for transducer: ;;transducer signature (whatever, input -> whatever) -> (whatever, input -> whatever) Signal functions are easy to program in Haskell using arrow syntax, and many libraries already exist for dealing with signal functions. [1]: Nilsson, Courtney and Peterson. Functional Reactive Programming, Continued. Haskell '02. http://haskell.cs.yale.edu/wp-content/uploads/2011/02/workshop-02.pdf http://haskell.cs.yale.edu/wp-content/uploads/2011/02/worksh... (see section 4) edit: formatting
deleted 12y ago
[deleted]

fnordsensei 12y ago

Tentative benchmark results have surfaced: https://github.com/thheller/transduce-bench https://github.com/thheller/transduce-bench Add salt according to taste.

mduerksen 12y ago
The benchmark is wrong atm, the compared functions do not yield the same result. (comp (map inc) (filter even?)) means filtering first, then incrementing. The opposite for (->> data (map inc) (filter even?) ... - which is not the same. And of course, it also means that the latter has to increment the double amount of numbers. EDIT: It was me who was wrong, thanks for the corrections. Pitfall successfully identified :)
- pyrtsa 12y ago
  Nope, that's the funny feature of transducers. Like lenses in Haskell, transducers compose in reversed order. (sequence (comp (map inc) (filter even?)) (range 10)) ;;=> (2 4 6 8 10) (->> (range 10) (map inc) (filter even?)) ;;=> (2 4 6 8 10) Both test functions in transduce-bench return 250000500000.
- richhickey 12y ago
  It seems counterintuitive, but composing transducers yields a reducing function that runs the transformation steps left->right. What you are composing is the reducing function transformations (right to left, ordinary composition), but their result, having been built inside-out, runs the steps outside-in. So (comp tx1 tx2...) runs in same order as (->> xs tx1 tx2...)

oafitupa 12y ago

As someone who tried Clojure and failed, serious question: Does anyone actually use all these crazy features/patterns that keep getting added/discovered and talked about? I ask because even though I can imagine someone smart mastering these things and programming faster, I can't imagine a second person being able to understand his code, maintain it, and generally be productive. I imagine the second person losing a lot of time trying to understand what is going on, or even thinking he understood but in reality he didn't and messing things up. So how do you even form a Clojure team?

calibraxis 12y ago
This sentence is important: "There will be more explanations, tutorials and derivations to follow, here and elsewhere." If a team ever adopts transducers, it'll generally be after a lot of explanations exist and has been made easy to understand. Clojure teams can defend themselves against exotic features like any other team: code review, conventions, etc. If I pull in some weird new feature, others had better be ok with it. (Obviously, what I'm saying doesn't apply to every team in the world; presumably there's a spectrum of ways to deal, or fail to deal, with this problem.) In my view, Clojure teams are formed via a political process, like any other programming language adoption.
JackMorgan 12y ago
It's a mindset change. Other than macros, which fundamentally alter the flow of code in a very non-standard way, the rest of these "crazy patterns and features" in Clojure are just like the crazy libraries used by typical Java/Ruby/C# developers, only thousands of times simpler. If I came to you and said, "does anyone even use these tens of thousands of libraries in Maven? How do other developers work on this afterwards, they'd have to learn all these new APIs!" I'd likely get a response like, "they'd just be expected to", with a chuckle. The mindset I've seen a lot is that language features are "too hard" to learn and should be avoided, but library complexity is beyond reproach and is rarely questioned. Clojure the language takes the approach that it's better to provide a dozen simple but incredibly composable tools that can easily replace a lot of duplicated boilerplate in other languages. Like these transducers, in Java/C# they'd likely be one of the design patterns that needs a whole set of classes to make what he shows in a few characters. Would you rather learn to write and read maintain a handful of classes, or just learn what those few characters mean? I don't get paid by the line, and any abstraction built into the language like that is a few more classes I don't have to maintain and possibly implement incorrectly in some subtle way. Like I said, it's just a mindset change. I know a company that only uses Clojure, and they hire a lot of entry level developers who haven't yet gotten stuck in a mindset that "languages are too hard; libraries are easy". They have great success with that, and their entry level guys are up to speed much faster than those in my shop, using .NET, where they have to learn a new language AND a mountain of boiler plate code using dozens of libraries and frameworks.

tel 12y ago

This is about as close as I could get in Haskell so far. It uses a slight twist on (x -> a -> x) called a Fold (which has a lot of great properties—it's a profunctor, an applicative, and a comonad). Nicely, this construction lets us write `take` purely! {-# LANGUAGE GADTs #-} {-# LANGUAGE RankNTypes #-} {-# LANGUAGE TypeOperators #-} import Control.Arrow import Control.Category import qualified Prelude import Prelude hiding (id, (.)) data Fold a r where Fold :: (a -> x -> x) -> x -> (x -> r) -> Fold a r data Pair a b = Pair !a !b pfst :: Pair a b -> a pfst (Pair a b) = a psnd :: Pair a b -> b psnd (Pair a b) = b newtype (~>) a b = Arr (forall r . Fold b r -> Fold a r) instance Category (~>) where id = Arr id Arr f . Arr g = Arr (g . f) amap :: (a -> b) -> (a ~> b) amap f = Arr (\(Fold cons nil fin) -> Fold (cons . f) nil fin) afilter :: (a -> Bool) -> (a ~> a) afilter p = Arr $ \(Fold cons nil fin) -> let cons' = \a x -> if p a then cons a x else x in Fold cons' nil fin fold :: Fold a r -> [a] -> r fold (Fold cons nil fin) = fin . spin where spin [] = nil spin (a:as) = cons a (spin as) asequence :: (a ~> b) -> ([a] -> [b]) asequence (Arr f) = fold (f (Fold (:) [] id)) aflatmap :: (a -> [b]) -> (a ~> b) aflatmap f = Arr $ \(Fold cons nil fin) -> Fold (\a x -> foldr cons x (f a)) nil fin atake :: Int -> (a ~> a) atake n = Arr $ \(Fold cons nil fin) -> let cons' = \a x n -> if n > 0 then cons a (x (n-1)) else x n in Fold cons' (const nil) (\x -> fin (x n))

phobbs 12y ago
Brilliant, this clears up the usage a lot more than the rest of the prose in the comment thread.