4 ms·

The power it has on top of map is it can skip items and change the shape of the container: that is, it’s a decomposition of a fold and not just a composable map

The power it has on top of map is it can skip items and change the shape of the container: that is, it’s a decomposition of a fold and not just a composable map. So, you can consume a vector and produce a subset of the vector as a map. Finally, transducers separate the element-wise processing from both the construction of the final sequence and the details of iterating over the input.

nextaccountic 3y ago
A map that can skip itens is normally called a filter_map But can it produce more than one item as well? So it's like, for each item of the iterator/stream/sequence, it can produce 0, 1, or any number of items? Then it's like Haskell's bind (the >>= of the Monad instance) for lists, or Rust's flat_map for iterators, and flatMap in javascript as well
- fiddlerwoaroof 3y ago
  It’s more than bind, because a monad requires that the input monad be the same as the output one (if you consume a list, you can only produce a list). Clojure’s Transducers are as powerful as foldr because the output type can be different. E.g.: (into {} (map (fn [k] [(/ k 2) k])) [1 2 3 4]) ;; {1 2, 2 4} (A difference between fold and transducers is that transducers can work in infinite input types like core.async channels) Here’s a bit of code I put together to show the relation to fold: https://github.com/fiddlerwoaroof/lisp-sandbox/blob/580980236bc55441af7d821c1f81b8c351a5474f/transduce-steps.lisp#L26 https://github.com/fiddlerwoaroof/lisp-sandbox/blob/58098023... The other way I think of this is “explicit stream fusion”: transducers work by passing an explicit continuation around and you call that continuation to add results to the output: but, crucially, you don’t have to know what the output type is, you just say “add this to it”.
  - nextaccountic 3y ago
    > the output type can be different That's interesting. But every such type must have the same "shape" - a sequence of things. So it's the same as bind, plus an optional conversion at the end. Which is the same as Rust's flat_map, because in Rust when you operate with iterators you can end up collecting into another type, like, myvec.into_iter().flat_map(|x| ..).collect() converts from a Vec<T> into SomeType<U>, where SomeType is any type that represents a sequence, and T to U is the type conversion from the map > (A difference between fold and transducers is that transducers can work in infinite input types like core.async channels) Ok so transducers are just lazy folds (I mean folds can work with infinite data in Haskell as well)
    - fiddlerwoaroof 3y ago
      > it's the same as bind, plus an optional conversion at the end. The mapcat transducer (flatMap in other languages) is equivalent to bind. The “optional conversion at the end” would defeat the whole point of transducers because it would force you to materialize an intermediate sequence before building up the result. The result type is a superset of monads, I’m fairly sure: it’s anything that can be the result of a two argument function with the signature `a -> b -> a`: there’s nothing in theory preventing using a transducer to sum up a list of integers.

nextaccountic 3y ago

A map that can skip itens is normally called a filter_map But can it produce more than one item as well? So it's like, for each item of the iterator/stream/sequence, it can produce 0, 1, or any number of items? Then it's like Haskell's bind (the >>= of the Monad instance) for lists, or Rust's flat_map for iterators, and flatMap in javascript as well

fiddlerwoaroof 3y ago
It’s more than bind, because a monad requires that the input monad be the same as the output one (if you consume a list, you can only produce a list). Clojure’s Transducers are as powerful as foldr because the output type can be different. E.g.: (into {} (map (fn [k] [(/ k 2) k])) [1 2 3 4]) ;; {1 2, 2 4} (A difference between fold and transducers is that transducers can work in infinite input types like core.async channels) Here’s a bit of code I put together to show the relation to fold: https://github.com/fiddlerwoaroof/lisp-sandbox/blob/580980236bc55441af7d821c1f81b8c351a5474f/transduce-steps.lisp#L26 https://github.com/fiddlerwoaroof/lisp-sandbox/blob/58098023... The other way I think of this is “explicit stream fusion”: transducers work by passing an explicit continuation around and you call that continuation to add results to the output: but, crucially, you don’t have to know what the output type is, you just say “add this to it”.
- nextaccountic 3y ago
  > the output type can be different That's interesting. But every such type must have the same "shape" - a sequence of things. So it's the same as bind, plus an optional conversion at the end. Which is the same as Rust's flat_map, because in Rust when you operate with iterators you can end up collecting into another type, like, myvec.into_iter().flat_map(|x| ..).collect() converts from a Vec<T> into SomeType<U>, where SomeType is any type that represents a sequence, and T to U is the type conversion from the map > (A difference between fold and transducers is that transducers can work in infinite input types like core.async channels) Ok so transducers are just lazy folds (I mean folds can work with infinite data in Haskell as well)
  - fiddlerwoaroof 3y ago
    > it's the same as bind, plus an optional conversion at the end. The mapcat transducer (flatMap in other languages) is equivalent to bind. The “optional conversion at the end” would defeat the whole point of transducers because it would force you to materialize an intermediate sequence before building up the result. The result type is a superset of monads, I’m fairly sure: it’s anything that can be the result of a two argument function with the signature `a -> b -> a`: there’s nothing in theory preventing using a transducer to sum up a list of integers.