6 ms·
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
by 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 agoBecause 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 agoInteresting. 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.
- tel 12y agoAlso, you can get rid of the sentinel value by packing along a termination continuation value as well: type Red r a = (r -> a -> r, r) zmap :: (b -> a) -> Red r a -> Red r b zmap f (f1, z1) = (\result input -> f1 result (f input), z1) zfilt :: (a -> Bool) -> Red r a -> Red r a zfilt p (f1, z1) = (\result input -> if p input then f1 result input else result, z1) ztake :: Int -> Red r a -> Red r a ztake n (f1, z1) = (run n, z1) where run n result input = let n' = n - 1 result = if n >= 0 then f1 result input else result in if n' == 0 then z1 else result This has the theoretical niceness of having `Red r a` just be the signature functor for linked lists.
- tel 12y agoI'm also assuming transduce and sequence are something like this type RT r a b = Red r a -> Red r b sequence :: RT [a] a b -> [b] -> [a] sequence xform bs = transduce xform (flip (:)) [] bs transduce :: RT r a b -> (r -> a -> r) -> r -> [b] -> r transduce xform cons nil = let (cons', nil') = xform (cons, nil) in foldr (flip cons') nil' but I can't find the actual source yet. Again, there's a weird flipping going on induced by the contravariance. It makes me want to define RT-composition backwards.
- 12y ago