3 ms·

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

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

> 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.