Clojure transducers are exactly signal functions from Haskell FRP literature, for those interested in such a connection.
Transducers are coming to Clojure
61–70 of 103 posts
Re: Transducers are coming to Clojure
#62I'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:…
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 )
reduce( mapping( lambda x: x + 1 )(add), xrange(10**9), 0 )
PS: python translation of mapping from 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 transducerRe: Transducers are coming to Clojure
#63Earlier quoted context omitted.
Thanks. I just looked up "map/reduce" on Wikipedia. Gee, I've been speaking 'prose' (an old joke) all along! So, I was procrastinating from working on my code, and there I have some data base data split, for some positive integer n, into n 'partitions'. The intention, later, is to use n servers, one server for one partition. Then I have some data X to be 'applied' to all the data in all the partitions, and from each…
Actually "transducer" can be done with straight function composition. It would work in any language supporting high order function, a fancy way of saying passing function around as argument or return value. e.g. in Javascript (I'll be overly verbose for illustration) function mySumReducer(sum, value1) { return sum + value1; } function myTimesReducer(product, value1) { return product * value1; } [1, 2, 3, 4].reduce(my…
Actually this doesn't really capture the idea properly - you need a "reducerComposer" function that can compose any functions that look like mySumReducer / myTimesReducer (take a memo and a value). You've just manually composed them in myDoublingTransducer, which indeed is just straight function composition. Your reducerComposer needs to function if the first reducer returns nothing (e.g. filter) or multiple values (e.g. flattening a list of lists). One way to think of it is that you are "pushing" values through a chain of reducers, and at any step you might produce 0, 1, or multiple values for the next step.
Re: Transducers are coming to Clojure
#64Clojure transducers are exactly signal functions from Haskell FRP literature, for those interested in such a connection.
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?
Re: Transducers are coming to Clojure
#65Clojure transducers are exactly signal functions from Haskell FRP literature, for those interested in such a connection.
[deleted]
Re: Transducers are coming to Clojure
#66Earlier quoted context omitted.
Actually "transducer" can be done with straight function composition. It would work in any language supporting high order function, a fancy way of saying passing function around as argument or return value. e.g. in Javascript (I'll be overly verbose for illustration) function mySumReducer(sum, value1) { return sum + value1; } function myTimesReducer(product, value1) { return product * value1; } [1, 2, 3, 4].reduce(my…
Actually this doesn't really capture the idea properly - you need a "reducerComposer" function that can compose any functions that look like mySumReducer / myTimesReducer (take a memo and a value). You've just manually composed them in myDoublingTransducer, which indeed is just straight function composition. Your reducerComposer needs to function if the first reducer returns nothing (e.g. filter) or multiple values (…
Sorry I was editing before I saw your comment. Note: There was a myDoublingTransducer before.
On a separate note, a reducer returns nothing doesn't make sense. A reducer might not add the current value to the memo (filter) but it always returns some memo for the next step. Also a reducer would not return multiple values. It returns just one value, the memo. If there are multiple values produced at a step, they would have been added to the memo. The function signature of a reducer is (s,v)->s, that means it always returns one thing.
Re: Transducers are coming to Clojure
#67Earlier quoted context omitted.
Comparing transducers to stream fusion is far narrower than the scope of their applicability.
They are more comparable to Oleg's Enumerators ( http://okmij.org/ftp/Haskell/Iteratee/describe.pdf ), in that you compose a series of computations and then push data through them. The type signature is similar: type Iteratee el m a -- a processor of 'els' in the monad 'm' returning a type 'a' type Enumerator el m a = Iteratee el m a -> m (Iteratee el m a) The Enumerators library is complicated by the presence of mon…
While not mentioned in the blog post, the transducers implementation supports both early termination and result completion/flushing/cleanup.
Re: Transducers are coming to Clojure
#68Earlier quoted context omitted.
Actually this doesn't really capture the idea properly - you need a "reducerComposer" function that can compose any functions that look like mySumReducer / myTimesReducer (take a memo and a value). You've just manually composed them in myDoublingTransducer, which indeed is just straight function composition. Your reducerComposer needs to function if the first reducer returns nothing (e.g. filter) or multiple values (…
Sorry I was editing before I saw your comment. Note: There was a myDoublingTransducer before. On a separate note, a reducer returns nothing doesn't make sense. A reducer might not add the current value to the memo (filter) but it always returns some memo for the next step. Also a reducer would not return multiple values. It returns just one value, the memo. If there are multiple values produced at a step, they would…
> A reducer might not add the current value to the memo (filter) but it always returns some memo for the next step.
I think the idea is that your reducer function shouldn't have to care about steps or memos. e.g. I should be able to do
filter(function(x) { return x Re: Transducers are coming to Clojure
#69Earlier quoted context omitted.
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/cloju...
... 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?
It applies universally and you're probably decades too late to stop it. http://www.catb.org/jargon/html/M/macrology.html
Re: Transducers are coming to Clojure
#70I 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 ([resu…
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